M LCOMP3121/9101
Algorithm Design and Analysis
J K
Tutorial 2
Divide and Conquer
Announcements
 Attached at the end of the tutorial sheet is an appendix with further information
about recurrences. If you are struggling with understanding recurrences, you may
wish to refer to the appendix.
COMP3121/9101: Algorithm Design and Analysis 2024, Term 2
1 This Week, in summary...
 The divide and conquer paradigm breaks a problem down into multiple subproblems and then com-
bines solutions to these subproblems to solve the original problem. We need to specify three steps.
– Divide. Splits the current problem instance into (two or more) problems of strictly smaller size.
– Conquer. Recursively splits the problem instances until the splitting stage can no longer be
performed. Once we reach the base cases, we can solve those individually.
– Combine. Uses solutions to smaller subproblems and merges them to obtain the solution to
the current problem instance.
See section 4 for a more detailed description of the process.
 The Master Theorem is a general framework for computing the asymptotic solution of a recurrence.
Let T (n) = aT (n/b) + f(n), where a ≥ 1 and b > 1. The theorem says that:
– if there exist a constant ? > 0 such that f(n) = O (nlogb a??), then T (n) = Θ (nlogb a).
– if f(n) = Θ (nlogb a), then T (n) = Θ (nlogb a log n).
– if there exist a constant ? > 0 such that f(n) = ? (nlogb a+?) and if af(n/b) ≤ cf(n) for some
constant c < 1 for all sufficiently large n, then T (n) = Θ (f(n)).
– if the recurrence does not fit into any of the above cases, then the theorem cannot be applied
and other techniques must be used.
Lecture Problems, Key Takeaways
 Maximum Median.
– If target t is achievable, then smaller targets are also achievable; if target t is not achievable, then
larger targets are also not achievable. Therefore, the problem of deciding is target t achievable?
is monotonic.
– Binary search for t between interval [A[n], A[n] + k].
– Time complexity. Deciding if target t is achievable takes O(n) time; binary search over a space
of length k; therefore, overall time complexity is O(n log k).
 Merge Sort.
– Divide. Splits the array into two halves.
– Conquer. Sort each half recursively.
– Combine. Merge two halves together in O(n) time.
– Time complexity. Recurrence is given by T (n) = 2T (n/2)+O(n), which is T (n) = O(n log n).
 Counting inversions.
– Divide. Splits the array into two halves.
– Conquer. Computes the number of inversions in each half recursively.
– Combine. Count the number of inversions that cross the dividing line in O(n) time.
– Time complexity. Recurrence is given by T (n) = 2T (n/2)+O(n), which is T (n) = O(n log n).
? Quick Sort.
– Divide. Choose pivot and partition array around it in O(n) time.
– Conquer. Sort both sides of the pivot recursively.
1
COMP3121/9101: Algorithm Design and Analysis 2024, Term 2
– Combine. Pass answer up the recursion tree.
– Time complexity. T (n) = O(n log n) in the average case; T (n) = O(n2) in the worst case,
depending on pivot choice.
 Karatsuba. Split the two input integers into
A = A1 · 2n/2 +A0, B = B1 · 2n/2 +B0.
We now compute AB with the expression
AB = A1B1 · 2n + [(A1 +A0)(B1 +B0)?A1B1 ?A0B0] 2n/2 +A0B0.
– Time complexity. Recurrence is given by T (n) = 3T (n/2) + c · n, which is T (n) = Θ (nlog2 3).
2
COMP3121/9101: Algorithm Design and Analysis 2024, Term 2
2 Binary Search
When we wanted to decide if an element x exists in an array A, we required n queries in the worst-case!
If we know further information about the properties of our input, we can make further improvements to
reduce the running time or memory usage. Binary search is an optimisation technique that reduces the
number of queries from n down to ?log2 n?. However, for binary search to be effective, we require two
properties to hold.
 Well-defined interval. If we want to query the middle element, we need a well-defined interval to begin
with so that the middle element is defined.
 Monotonicity. If we remove a set of elements, we should ensure that we never have to query any of the
elements that we previously tossed out.
A monotonic array looks like a sorted or reverse sorted array. For example, consider the array A =
. If we want to check if A consists of the element 2, then we can first query 0. Since A
is sorted (monotonic), we know that any element to the left of 0 will never be larger than 0 and so, we can
safely remove all such elements to the left. This drastically improves the running time of our first algorithm
where we check all of the elements of the array, especially when the number of elements becomes large!
In the following problems, be sure to check that the two above properties hold before simply applying
binary search!
2.1 Identity Element
Let A[1..n] be a sorted array of n distinct integers. Some of these integers may be positive, negative,
or zero. Design an O(log n) algorithm to decide if there exist some index i such that A[i] = i.
Hint. Consider constructing a new array B such that B[i] = A[i]? i.
Exercise. Further, suppose we now know that A[1] > 0. Answer the same problem in O(1) time.
2.2 Search in Rotated Sorted Array (#33)
Let A[1..n] be an array of n integers. We are given an additional integer x, and our goal is to decide
whether x appears somewhere in A.
(a) Without any additional information aboutA, design a linear-time algorithm that decides whether
x appears somewhere in A.
(b) Now, suppose you know that A is a sorted array. Design an O(log n) algorithm that decides
whether x appears somewhere in A.
(c) Now, suppose you know that A is a sorted array but it has been shifted by k units to the right.
For example, if k = 4 and the sorted array was [1, 2, 3, 5, 6, 7], then A = [5, 6, 7, 1, 2, 3]. In this
scenario, suppose we are given k in advance. Design anO(log n) algorithm that decides whether
x appears somewhere in A.
Note. You are given, as input, an array that is promised to be shifted by k units to the right, where
k is known.
(d) Finally, suppose that we do not know what k is. Design an O(log n) algorithm that decides
whether x appears somewhere in A.
Hint. If we can find k in O(log n) time, then we can just use the previous algorithm.
3
COMP3121/9101: Algorithm Design and Analysis 2024, Term 2
2.3 Order Statistic of Two Sorted Arrays
Let A[1..n] and B[1..n] be two sorted arrays. For simplicity, assume that A and B share no common
elements and all elements in each array are distinct. We construct a new array C[1..2n] by merging
A and B together.
Given an integer k, where 1 ≤ k ≤ 2n, we want to design an algorithm to find the kth smallest
element in C.
(a) Design an O(n log n) algorithm that finds the kth smallest element in C.
Hint. This is really easy...
(b) Design an O(k) algorithm that finds the kth smallest element in C.
(c) Design an O(log n) algorithm that finds the kth smallest element in C.
Hint. How does this problem relate to median finding? Do we obtain further information by
comparing an element of A with an element of B?
4
COMP3121/9101: Algorithm Design and Analysis 2024, Term 2
3 Applications of Binary Search
3.1 Unbounded Binary Search
To directly apply binary search, we needed a well-defined interval. However, what happens when we are
not given the interval directly? We will need to artificially construct the interval.
Let A be a sorted array of distinct elements. However, you are not given the size of A. Your task is to
find the smallest index i so that A[i] > 0, or report that no such index exists. Of course, we can just
check each element one by one. Aim to design a more efficient algorithm.
Hint. Try to artificially construct an interval to binary search over.
3.2 Discrete Binary Search
Binary search works well when the array we want to binary search over is monotonic. Discrete binary
search directly toys with this idea. Instead of an array of integers where the monotonicity is clear, we can
additionally construct a boolean array.
 What does monotonicity mean here?
Definitions.
 Subsequence. A subsequence of a string S is a string T that can be formed by deleting some
or no characters from S without changing the relative order of the remaining elements. For
example, if S = Comp3121AndComp9101, then we can form the subsequence T = 3121n9101.
 Substring. A substring of a string S is a contiguous string T that forms a subsequence of S.
 Supersequence. A supersequence of a string T is a string S that contains T as a subsequence
of S.
 Superstring. A superstring of a string T is a string S that contains T as a substring of S.
You are given a string S of n characters and another string T of m characters such that m ≤ n. You
want to find the length of the longest subsequence of S that appears as a prefix of T . For example, if
S = abcdefgh and T = bcdghf, then your algorithm should return 5.
(a) Let T ′ be a prefix of T . Show that:
 If T ′ is a subsequence of S, then any substring of T ′ is also a subsequence of S.
 If T ′ is not a subsequence of S, then any superstring of T ′ is not a subsequence of S.
(b) For a given string A of n characters and another string B ofm characters (withm ≤ n), assume
that there is an O(f(n)) algorithm that decides if B is a subsequence of A. Using this algorithm,
describe an O(f(n) logm)-time algorithm to compute the length of the longest subsequence of
S that appears as a prefix of T .
5
COMP3121/9101: Algorithm Design and Analysis 2024, Term 2
4 Solving problems with Divide and Conquer
4.1 Designing the algorithm
To solve a problem with divide and conquer, we need to describe two steps in our algorithm: how we
divide our problem instance into multiple (usually two or more) subproblems, and how we combine the
solutions to the subproblems to solve the original problem. However, the process by which we do this
comes in three steps.
4.1.1 Dividing the instance
The first step is to find a suitable method of dividing the problem instance. We need to ensure that the
subproblems constructed are of the same type; after all, we will be calling the magical recursion wizard to
do the work for us. But for the wizard to do its work, we need to ensure that the problem instance mirrors
the original problem we wanted to solve (see the tiling problem).
There are usually many ways of appropriate dividing the problem instance; however, the intended division
lends itself nicely to a clean combine step (see merge sort).
4.1.2 Conquering each subproblem
We can loosely describe the conquer step as follows:
 If the current problem instance is easy, we solve it directly ourselves.
 Otherwise, we simplify the problem instance by transforming it into (usually two or more) smaller
instances of the same problem.
If the self-referential description is confusing, we can imagine asking a recursion wizard to solve our
smaller problem instances. However, there is one catch here:
 If you ask the wizard to solve the current problem, it will be able to solve all subproblem instances
that are strictly smaller.
 The wizard can only solve the problem when the input is in the appropriate format.
 The wizard will send you the solution to all subproblems and will ask you to use those solutions to
solve the original problem.
4.1.3 Combining solutions
Once we have solutions to the smaller subproblems from the recursion wizard, we need a way to merge
them together to answer the original problem. The combine step may be as simple as taking the maxi-
mum/minimum of either two sides, or as complicated as requiring extra work to consider elements from
either side of the partition.
 Example. Merge sort requires us to merge the two sorted arrays together to form a new sorted array;
this is done with two pointers initially at the head of the arrays and then sweeping left to right.
 Example. Counting inversions requires us to count inversions between pairs of elements that are on
both halves of the split (i.e. one element from the pair is on one half and the other element is on the
other half).
 Example. Computing the pair of points that are closest in distance requires us to consider pairs of
points that are on both halves of the split.
6
COMP3121/9101: Algorithm Design and Analysis 2024, Term 2
4.2 Analysing the algorithm
4.2.1 Proving correctness
When proving the correctness of divide-and-conquer algorithms, we typically prove it by induction. There-
fore, we follow the induction structure:
 The base cases are typically easy to argue because, by the nature of how you have handled the base
cases, the problem is solved.
 Assume, now, that the problem has been solved for each of the recursive steps. We now need to
argue that if our algorithm retrieves the correct solution in our recursive stages, then it also retrieves
the correct solution in the current step.
4.2.2 Analysing the time complexity
To analyse the running time of your algorithm, we need to analyse the work taken at each recursive step,
including the time taken to combine all previous solutions. This typically requires setting up a recurrence
and solve the recurrence for the asymptotic behaviour. To this end, we can use the Master Theorem stated
below. See the appendix for the extension of theMaster Theorem that may be applicable in some situations.
Let T (n) = aT (n/b) + f(n), where a ≥ 1 and b > 1. The Master Theorem says that:
 if there exist a constant ? > 0 such that f(n) = O (nlogb a??), then T (n) = Θ (nlogb a).
 if f(n) = Θ (nlogb a), then T (n) = Θ (nlogb a log n).
 if there exist a constant ? > 0 such that f(n) = ? (nlogb a+?) and if af(n/b) ≤ cf(n) for some
constant c < 1 for all sufficiently large n, then T (n) = Θ (f(n)).
If the recurrence does not fit any of these cases, then we need to unroll the recurrence.
7
COMP3121/9101: Algorithm Design and Analysis 2024, Term 2
5 Applications of Divide and Conquer
5.1 Tiling Problems
Let n be a power of two. An equilateral triangle is partitioned into smaller equilateral triangles by
parallel lines dividing each of its sides into n > 1 equal segments. The topmost equilateral triangle
is chopped off. We want to tile the remaining equilateral triangles with trapezoids, each of which is
composed of three equilateral triangles.
Design a divide and conquer algorithm to tile the equilateral triangles with trapzedoids. Justify the
correctness of the algorithm and analyse its time complexity.
 Every equilateral triangle must be covered by at least one trapezoid.
 No equilateral triangle may be tiled by more than one trapezoid.
Note. A tiling always exists.
5.2 Line Segment Intersections
You are given two lists of n points, one list P = [p1, . . . , pn] lies on the line y = 0 and the other list
Q = [q1, . . . , qn] lies on the line y = 1. We construct n line segments by connecting pi to qi for each
i = 1, . . . , n. You may assume that the numbers in P are distinct and the numbers in Q are also
distinct. Design an O(n log n) algorithm to return the number of intersections between every pair of
distinct line segments.
For example, the following instance
p1 p2 p3p4
q1q2q3 q4
should return 5 since there are five intersections.
8
COMP3121/9101: Algorithm Design and Analysis 2024, Term 2
5.3 Geometric Applications of Divide and Conquer
Alice is planting n1 flowers f1, . . . , fn1 among n2 rectangular gardens g1, . . . , gn2 . Bob’s task is to
determine which flowers belong to which gardens (possibly none). Alice informs Bob that no two
gardens overlap; therefore, if a flower belongs to a garden, then it belongs to exactly one garden.
Moreover, a garden can contain multiple flowers. If a flower does not belong to any garden, then Bob
returns undefined for that flower. Finally, let n = n1 + n2.
Figure 1: A collection of n1 = 5 flowers and n2 = 4 gardens.
We can define the location of a rectangular garden by identifying its bottom-left and top-right corners.
Additionally, flower fi is represented by a point F [i]. Formally, we are given three arrays:
 B = [(x1, y1), . . . , (xn2 , yn2)], where B[i] represents the bottom-left point of garden gi.
 T = [(x1, y1), . . . , (xn2 , yn2)], where T [i] represents the top-right point of garden gi.
 F = [(x1, y1), . . . , (xn1 , yn1)], where F [i] represents the location of flower fi.
For each flower fi, your task is to identify which garden (if any) contains fi. If a flower is not contained
inside any garden, then we return undefined.
(a) We first solve the special case where all of the gardens intersect with a horizontal line. Design
an O(n log n) algorithm to determine which flowers belong to which gardens (if such a garden
exists).
Figure 2: A collection of n1 = 6 flowers and n2 = 4 gardens that intersect with a horizontal line.
Hint. What do you know about two adjacent gardens if they have to intersect with a horizontal
line?
(b) We now remove the assumption that every garden intersects with a horizontal line. Design an
O(n log2 n) algorithm to determine which flowers belong to which gardens (if such a garden
exists).
Hint. If T (n) = 2T (n/2) +O(n log n), then T (n) = O(n log2 n).
Exercise. Reduce the time complexity to O(n log n).
9
COMP3121/9101: Algorithm Design and Analysis 2024, Term 2
Further practice exercises
In addition to your lab exercises, here is a curated list of further practice problems in preparation for your
exam. The problems are (approximately) ordered by difficulty. No solutions will be released for these
exercises; therefore, you may want to post on the forum if you have any queries.
1. Let A be an array of n integers. Further, suppose that A[1] ≥ A[2] and A[n? 1] ≤ A[n]. An element
A[i] is a local minimum if it satisfies the inequalities
A[i] ≤ A[i? 1], A[i] ≥ A[i+ 1].
Design an O(log n) algorithm that returns the index of a local minimum. For example, if A =
[1,3, 4, 3, 6, 8], then one possible answer is A[2] = ?3. Another possible answer is A[4] = 3.
2. You are handed n bottles from a genie, and the genie exclaims that exactly one of these bottles
contain the secret to eternal happiness. In order to play the game, the genie has a few rules:
 You pick up a set of bottles and can only ask the genie if any of these bottles contain the secret.
You are not allowed to peek inside any of the bottles; otherwise, you will banished forever!
? You can query any bottle an infinite number of times.
Since the genie knows you are an algorithm enthusiast, they will grant you only O(log n) queries. If
you need to use more thanO(log n) queries, then you will not receive the secret to eternal happiness.
Design an algorithm to win the game and unlock the secret to eternal happiness!
3. Let G = (V,E) be a connected and acyclic graph on n vertices. On this graph, you are guaranteed
that exactly one of these vertices contains a prize; however, you do not know which vertex it is. You
are allowed to query vertices and each query will tell you which edge you must travel on in order to
reach the prize, or “yes” if the current vertex you are querying on contains the prize.
Your task is to determine which vertex contains the prize using at most O(log n) queries.
Note. The time complexity of your algorithm might be slower than log n, but your algorithm can only
use at most O(log n) many queries.
(a) If G is a path (or line graph), design an O(n)-time algorithm that finds the prized vertex using
at most O(log n) many queries.
(b) For the remaining two parts, assume thatG is an arbitrary connected and acyclic graph. Design
an O(n2 log n)-time algorithm that finds the prized vertex using at most O(log n)many queries.
(c) Reduce the time complexity to O(n log n).
Note. Since G is connected and acyclic, |E| ≤ |V |.
4. Let A be an array of n objects. These objects may not necessarily be comparable and so, we cannot
test for inequality. Instead, we can only ask queries of the form: is A[i] = A[j]?. An element x is the
majority element whether x appears more than n/2 times. Design an O(n log n) algorithm to find
the majority element, or report that no such element exists.
Hint. Firstly, if a majority exists, then convince yourself that there is only one majority element. Yes...
there is an O(n) algorithm for this problem.
5. You have just landed at a sporting arena with n students, either from UNSW or USYD. Each student
is either from UNSW or USYD, and not both or neither. From their outward appearance, you cannot
tell which person is from which school and you cannot ask any student what school they are from;
otherwise, you will receive many stares. Instead, you devise a plan.
 You pick two arbitrary students and introduce them to one another. Two students from the same
school knows each other and will greet each other with a smile. Two students from opposing
schools will stare blankly at each other.
10
COMP3121/9101: Algorithm Design and Analysis 2024, Term 2
Suppose you know that more than half of the students belong to a particular school. Design an
O(n log n) algorithm to identify all students in the majority school.
Hint. Try to first find a student in the majority school. Maybe something similar to the previous problem
might help. Yes... this means that there is an O(n) algorithm for this problem too.
6. Let I = {I1, . . . , In} be a set of n intervals. Each interval Ii is specified by its two end points: ai and
bi with ai ≤ bi. Two intervals Ii and Ij overlap if there exist a point x such that x = Ii and x = Ij .
In other words, x = [ai, bi] and x = [aj , bj ]. Finally, the length of the overlap is given by the longest
interval that is shared between Ii and Ij . Formally, we can express this length as
L(i, j) = max{0,min{bi, bj} ?max{ai, aj}}.
Given n intervals, design an O(n log n) algorithm that returns the pair of intervals Ii and Ij that
maximises L(i, j). Your input is two arrays A[1..n] and B[1..n] such that A[i] specifies the beginning
of interval Ii and B[i] specifies the end of interval Ii.
7. Let L = {?1, . . . , ?n} be a set of n non-vertical lines, where line ?i is specified by the equation
y = aix + bi. Further, we will assume that no three lines intersect at a point. A line ?i is uppermost
at a point x0 if aix0 + bi > ajx0 + bj for all i ?= j. A line ?i is visible if there exist some x-coordinate
for which ?i is uppermost. In other words, if we look down from the line y =∞, then we can see a
portion of the line.
Design an O(n log n) algorithm that returns all of the visible lines.
Hint. Sort in increasing order of slope. Which two lines are always visible? When we combine two
subproblems, consider each intersection point. It might help to draw out a picture.
11
COMP3121/9101: Algorithm Design and Analysis 2024, Term 2
Appendix: Understanding Recurrences
A recurrence is a succinct description of a system that depends on itself, usually by calling itself multiple
times. For divide and conquer algorithms, we often split the problem instance into multiple smaller in-
stances of the same problem. To quickly analyse the running time of the algorithm, we usually write it as
a recurrence.
Let T (n) denote the running time of the algorithm on a problem of size n. Then, if we divide the problem
instance into a copies of itself, each of size n/b, then we can succinctly write T (n) in terms of T (n/b);
specifically,
T (n) = aT (n/b) + f(n),
where f(n) is the amount of overhead work used to combine all a subproblems. Pictorially, this recurrence
can be viewed exactly as a recursion tree.
Figure 3: Courtesy: Jeff Erickson’s Algorithms.
The total amount of work required of an algorithm with recurrence T (n) = aT (n/b) + f(n) is the sum of
the amount of work at each level; in other words, the amount of work is given by
T (n) = f(n) + af(n/b) + a2f(n/b2) + · · ·+ aLf(n/bL),
where L = logb n. The Master Theorem gives conditions on f(n), and the asymptotic complexity can be
resolved depending on which term dominates.
? If af(n/b) > cf(n) for some constant c > 1, then the series form an ascending geometric series. The
largest term in the series, therefore, is the last term and so, T (n) = Θ(nlogb a). To see why this is the
12
COMP3121/9101: Algorithm Design and Analysis 2024, Term 2
case, note that.
 If af(n/b) < cf(n) for some constant c > 1, then the series form a descending geometric series. The
largest term in the series, therefore, is the first term and so, T (n) = Θ(f(n)).
 If af(n/b) = f(n), then each term in the series contributes to the overall work required. Thus, in
this case, we have that
T (n) = Θ (f(n)L) = Θ (f(n) log n)
 Otherwise, this analysis is not applicable and we need to resort to other methods such as unrolling
the recurrence.
A.1 The Akra-Bazzi Method
The Akra-Bazzi method generalises the above discussion and provides a much more powerful result. In
doing this, we actually recover the Master Theorem in its stated form. To do this, we will firstly consider
a general divide and conquer recurrence:
T (n) =
L∑
i=1
aiT (n/bi) + f(n),
where L is a constant. Further, assume that ai > 0 and bi > 1 are constants for each i. These do not have
to be the same constants throughout; see exercise for an example. Finally, we will assume that f grows
polynomially; that is, we make the assumption that
f(n) = ?(nc), f(n) = O(nd),
with 0 < c ≤ d. Akra and Bazzi proved that the closed form solution to the recurrence is
T (n) = Θ
請加QQ：99515681  郵箱：99515681@qq.com   WX：codinghelp