Introduction to Algorithms (SMA 5503), Problem Set 1 Solutions

Introduction to Algorithms Massachusetts Institute of Technology Professors Erik D. Demaine and Charles E. Leiserson September 30, 2005 6.046J/18.410J Handout 8 Problem Set 1 Solutions Problem 1-1. Asymptotic Notation For each of the following statements, decide whether it is always true, never true, or sometimes true for asymptotically nonnegative functions f and g. If it is always true or never true, explain why. If it is sometimes true, give one example for which it is true, and one for which it is false. (a) f (n) = O(f (n)2 ) Solution: Sometimes true: For f (n) = n it is true, while for f (n) = 1/n it is not true. (The statement is always true for f (n) = Ω(1), and hence for most functions with which we will be working in this course, and in particular all time and space complexity functions). (b) f (n) + g(n) = Θ (max (f (n), g(n))) Solution: Always true: max(f (n), g(n)) ≤ f (n) + g(n) ≤ 2 max(f (n), g(n)). (c) f (n) + O(f (n)) = Θ(f (n)) Solution: Always true: Consider f (n) + g(n) where g(n) = O(f (n)) and let c be a constant such that 0 ≤ g(n) < cf (n) for large enough n. Then f (n) ≤ f (n) + g(n) ≤ (1 + c)f (n) for large enough n. (d) f (n) = Ω(g(n)) and f (n) = o(g(n)) (note the little-o) Solution: Never true: If f (n) = Ω(g(n)) then there exists positive constant cΩ and nΩ such that for all n > nΩ , cg(n) ≤ f (n). But if f (n) = o(g(n)), then for any positive constant c, there exists no (c) such that for all n > no (c), f (n) < cg(n). If f (n) = Ω(g(n)) and f (n) = o(g(n)), we would have that for n > max(nΩ , no (cΩ )) it should be that f (n) < cΩ g(n) ≤ f (n) which cannot be. (e) f (n) 6= O(g(n)) and g(n) 6= O(f (n)) Solution: Sometimes true: For f (n) = 1 and g(n) = kn ∗ sin(n)k it is true, while for any f (n) = O(g(n)), e.g. f (n) = g(n) = 1, it is not true. Handout 8: Problem Set 1 Solutions 2 Problem 1-2. Recurrences Give asymptotic upper and lower bounds for T (n) in each of the following recurrences. Assume that T (n) is constant for n ≤ 3. Make your bounds as tight as possible, and justify your answers. (a) T (n) = 2T (n/3) + n lg n Solution: By Case 3 of the Master Method, we have T (n) = Θ(n lg n). (b) T (n) = 3T (n/5) + lg2 n Solution: By Case 1 of the Master Method, we have T (n) = Θ(nlog5 (3) ). (c) T (n) = T (n/2) + 2n Solution: Case 3 of master’s theorem, (check that the regularity condition holds), Θ(2n ). √ (d) T (n) = T ( n) + Θ(lg lg n) Solution: Change of variables: let m = lg n. Recurrence becomes S(m) = S(m/2) + Θ(lg m). Case 2 of master’s theorem applies, so T (n) = Θ((lg lg n)2 ). (e) T (n) = 10T (n/3) + 17n1.2 Solution: Since log3 9 = 2, so log3 10 > 2 > 1.2. Case 1 of master’s theorem applies, Θ(nlog3 10 ). (f) T (n) = 7T (n/2) + n3 Solution: By Case 3 of the Master Method, we have T (n) = Θ(n3 ). (g) T (n) = T (n/2 + √ n) + √ 6046 Solution: By induction, T (n) √ is a monotonically increasing function. Thus, for large enough n, T (n/2) ≤ T (n/2 + n) ≤ T (3n/4). At each stage, we incur constant cost √ 6046, but we decrease the problem size to atleast one half and at most three-quarters. Therefore T (n) = Θ(lg n). Handout 8: Problem Set 1 Solutions 3 (h) T (n) = T (n − 2) + lg n Pn/2 Pn/2 Solution: T (n) = Θ(n log n). This is T (n) = i=1 lg 2i ≥ i=1 lg i ≥ (n/4)(lg n/4) = Ω(n lg n). For the upper bound, note that T (n) ≤ S(n), where S(n) = S(n−1)+lg n, which is clearly O(n lg n). (i) T (n) = T (n/5) + T (4n/5) + Θ(n) Solution: Master’s theorem doesn’t apply here. Draw recursion tree. At each level, do Θ(n) work. Number of levels is log5/4 n = Θ(lg n), so guess T (n) = Θ(n lg n) and use the substitution method to verify guess. In the f (n) = Θ(n) term, let the constants for Ω(n) and O(n) be n0 , c0 and c1 , respectively. In other words, let for all n ≥ n0 , we have c0 n ≤ f (n) ≤ c1 n. • First, we show T (n) = O(n). For the base case, we can choose a sufficiently large constant d1 such that T (n) < d1 n lg n. For the inductive step, assume for all k < n, that T (k) < d1 n lg n. Then for k = n, we have T (n) ≤ ≤ = = 4n n T +T + c1 n 5 5     n 4n n 4n d1 lg + d1 lg + c1 n 5 5 5 5   4d1n 5 d1 n + c1 n lg 5 − lg d1 n lg n − 5 5 4! ! lg 5 + 4 lg(5/4) d1 n lg n − n d 1 − c1 . 5     The residual is negative as long as we pick d1 > 5c1 /(lg 5+4 lg(5/4)). Therefore, by induction, T (n) = O(n lg n). • To show that T (n) = Ω(n), we can use almost the exact same math. For the base case, we choose a sufficiently small constant d0 such that T (n) > d0 n lg n. For the inductive step, assume for all k < n, that T (k) > d0 n lg n. Then, for k = n, we have n 4n T (n) ≥ T +T + c0 n 5 5     4n n 4n n + d0 lg + c0 n ≥ d0 lg 5 5 5 5 ! ! lg 5 + 4 lg(5/4) d0 . = d0 n lg n + n c0 − 5     Handout 8: Problem Set 1 Solutions 4 The residual is positive as long as d0 < 5c0 /(lg 5 + 4 lg(5/4)). Thus, T (n) = Ω(n lg n). (j) T (n) = √ √ n T ( n) + 100n Solution: Master’s theorem doesn’t √ apply here directly. Pick S(n) = T (n)/n. The recurrence becomes S(n) = S( n) + 100. The solution of this recurrece is S(n) = Θ(lg lg n). (You can do this by a recursion tree, or by substituting m = lg n again.) Therefore, T (n) = Θ(n lg lg n). Problem 1-3. Unimodal Search An array A[1 . . n] is unimodal if it consists of an increasing sequence followed by a decreasing sequence, or more precisely, if there is an index m ∈ {1, 2, . . . , n} such that • A[i] < A[i + 1] for all 1 ≤ i < m, and • A[i] > A[i + 1] for all m ≤ i < n. In particular, A[m] is the maximum element, and it is the unique “locally maximum” element surrounded by smaller elements (A[m − 1] and A[m + 1]). (a) Give an algorithm to compute the maximum element of a unimodal input array A[1 . . n] in O(lg n) time. Prove the correctness of your algorithm, and prove the bound on its running time. Solution: Notice that by the definition of unimodal arrays, for each 1 ≤ i < n either A[i] < A[i + 1] or A[i] > A[i + 1]. The main idea is to distinguish these two cases: 1. By the definition of unimodal arrays, if A[i] < A[i + 1], then the maximum element of A[1..n] occurs in A[i + 1..n]. 2. In a similar way, if A[i] > A[i + 1], then the maximum element of A[1..n] occurs in A[1..i]. This leads to the following divide and conquer solution (note its resemblance to binary search): 1 a, b ← 1, n 2 while a < b 3 do mid ← ⌊(a + b)/2⌋ 4 if A[mid] < A[mid + 1] 5 then a ← mid + 1 6 if A[mid] > A[mid + 1] 7 then b ← mid 8 return A[a] Handout 8: Problem Set 1 Solutions 5 The precondition is that we are given a unimodal array A[1..n]. The postcondition is that A[a] is the maximum element of A[1..n]. For the loop we propose the invariant “The maximum element of A[1..n] is in A[a..b] and a ≤ b”. When the loop completes, a ≥ b (since the loop condition failed) and a ≤ b (by the loop invariant). Therefore a = b, and by the first part of the loop invariant the maximum element of A[1..n] is equal to A[a]. We use induction to prove the correctness of the invariant. Initially, a = 1 and b = n, so, the invariant trivially holds. Suppose that the invariant holds at the start of the loop. Then, we know that the maximum element of A[1..n] is in A[a..b]. Notice that A[a..b] is unimodal as well. If A[mid] < A[mid + 1], then the maximum element of A[a..b] occurs in A[mid + 1..b] by case 1. Hence, after a ← mid + 1 and b remains unchanged in line 4, the maximum element is again in A[a..b]. The other case is symmetric. To complete the proof, we need to show that the second part of the invariant a ≤ b is also true. At the start of the loop a < b. Therefore, a ≤ ⌊(a + b)/2⌋ < b. This means that a ≤ mid < b such that after line 4 or line 5 in which a and b get updated a ≤ b holds once more. The divide and conquer approach leads to a running time of T (n) = T (n/2) + Θ(1) = Θ(lg n). A polygon is convex if all of its internal angles are less than 180◦ (and none of the edges cross each other). Figure 1 shows an example. We represent a convex polygon as an array V [1 . . n] where each element of the array represents a vertex of the polygon in the form of a coordinate pair (x, y). We are told that V [1] is the vertex with the minimum x coordinate and that the vertices V [1 . . n] are ordered counterclockwise, as in the figure. You may also assume that the x coordinates of the vertices are all distinct, as are the y coordinates of the vertices. (b) Give an algorithm to find the vertex with the maximum x coordinate in O(lg n) time. Solution: Notice that the x-coordinates of the vertices form a unimodal array and we can use part (a) to find the vertex with the maximum x-coordinate in Θ(lg n) time. (c) Give an algorithm to find the vertex with the maximum y coordinate in O(lg n) time. Solution: After finding the vertex V [max] with the maximum x-coordinate, notice that the y-coordinates in V [max], V [max + 1], . . . , V [n − 1], V [n], V [1] form a unimodal array and the maximum y-coordinate of V [1..n] lies in this array. Again part (a) can be used to find the vertex with the maximum y-coordinate. The total running time is Θ(lg n). Handout 8: Problem Set 1 Solutions 6 V [8] V [7] V [9] V [6] V [1] V [5] V [2] V [3] V [4] Figure 1: An example of a convex polygon represented by the array V [1 . . 9]. V [1] is the vertex with the minimum x-coordinate, and V [1 . . 9] are ordered counterclockwise.