LCOMP3121/9101 Algorithm Design and Analysis
Algorithm Design and Analysis
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
LCOMP3121/9101
Algorithm Design and Analysis
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 =
[−3,−2,−1, 0, 1, 2, 3]. 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?