=========================================================================== CSC 236 Homework Assignment 2 -- Sample Solutions Winter 2008 =========================================================================== 1. First, we prove that T(n) is increasing. Formally, we prove the statement \-/ n, \-/ m < n, T(m) < T(n), by complete induction on n. BC: \-/ m < 0, T(m) < T(0) is vacuously true. \-/ m < 1, T(m) < T(1) is equivalent to T(0) < T(1), which is true (T(0) = 0 < 1 = T(1)). \-/ m < 2, T(m) < T(2) is true because T(1) = 1 < 13 = T(2) and T(0) < T(1) < T(2). IH: Suppose n > 2 and \-/ k < n, \-/ m < k, T(m) < T(k). IS: Since n > 2, 1 < n-1 < n so by the IH, \-/ m < n-1, T(m) < T(n-1). If we prove T(n-1) < T(n), we can conclude \-/ m < n, T(m) < T(n). Since n > 2, T(n) = 2 T(|_n/4_|) + 3 T(|^n/6^|) + 5 n and T(n-1) = 2 T(|_(n-1)/4_|) + 3 T(|^(n-1)/6^|) + 5 (n-1). By the IH, T(|_(n-1)/4_|) <= T(|_n/4_|) (because |_(n-1)/4_| <= |_n/4_| < n) and T(|^(n-1)/6^|) <= T(|^n/6^|) (because |^(n-1)/6^| <= |^n/6^| < n). Hence, T(n-1) = 2 T(|_(n-1)/4_|) + 3 T(|^(n-1)/6^|) + 5 (n-1) <= 2 T(|_n/4_|) + 3 T(|^n/6^|) + 5 n - 5 <= T(n) - 5 < T(n). By induction, \-/ n, \-/ m < n, T(m) < T(n), i.e., T(n) is increasing. Now, perform repeated substitution, ignoring floors and ceilings and using the facts that n/4 >= n/6 and T(n) is increasing. T(n) = 2 T(n/4) + 3 T(n/6) + 5 n >= 2 T(n/6) + 3 T(n/6) + 5 n = 5 T(n/6) + 5 n = 5 (2 T(n/24) + 3 T(n/36) + 5 n/6) + 5 n >= 25 T(n/36) + 25 n/6 + 5 n = 25 T(n/36) + 5n (1 + 5/6) >= 5^2 (5 T(n/6^3) + 5 n/36) + 5 n (1 + 5/6) = 5^3 T(n/6^3) + 5n (1 + 5/6 + 5^2/6^2) after i substitutions: >= 5^i T(n/6^i) + 5n (1 - (5/6)^i) / (1 - 5/6) = 5^i T(n/6^i) + 30 n (1 - 5^i/6^i) base case reached roughly when n/6^i = 1, i.e., i = log_6 n: >= 5^{log_6 n} T(n/6^{log_6 n}) + 30 n (1 - 5^{log_6 n}/6^{log_6 n}) = n^{log_6 5} T(1) + 30 n - 30 n^{log_6 5} = 30 n - 29 n^{log_6 5} so we expect T(n) (- \Omega(n). We could also have obtained this guess through the Master Theorem, since T(n) >= 5 T(n/6) + 5 n (approximately). T(n) = 2 T(n/4) + 3 T(n/6) + 5 n <= 2 T(n/4) + 3 T(n/4) + 5 n = 5 T(n/4) + 5 n = 5 (2 T(n/16) + 3 T(n/24) + 5 n/4) + 5 n <= 25 T(n/16) + 25 n/4 + 5 n = 25 T(n/16) + 5n (1 + 5/4) <= 5^2 (5 T(n/4^3) + 5 n/16) + 5 n (1 + 5/4) = 5^3 T(n/4^3) + 5n (1 + 5/4 + 5^2/4^2) after i substitutions: <= 5^i T(n/4^i) + 5n ((5/4)^i - 1) / (5/4 - 1) = 5^i T(n/4^i) + 20 n (5^i/4^i - 1) base case reached roughly when n/4^i = 1, i.e., i = log_4 n: <= 5^{log_4 n} T(n/4^{log_4 n}) + 20 n (5^{log_4 n}/4^{log_4 n} - 1) = n^{log_4 5} T(1) + 20 n^{log_4 5} - 20 n <= 21 n^{log_4 5} - 20 n so we expect T(n) (- O(n^{log_4 5}). We could also have obtained this guess through the Master Theorem, since T(n) <= 5 T(n/4) + 5 n (approximately). Lower bound: Proof that \-/ n, T(n) >= n, by complete induction on n. Base Cases: T(0) = 0 >= 0 and T(1) = 1 >= 1. Ind. Hyp.: Suppose n >= 2 and \-/ j (- {0,1,...,n-1}, T(j) >= j Ind. Step: T(n) = 2 T(|_n/4_|) + 3 T(|^n/6^|) + 5 n (by definition of T(n), since n >= 2) >= 2 |_n/4_| + 3 |^n/6^| + 5 n (by the IH, since 0 <= |_n/4_|, |^n/6^| < n for n >= 2) > n. Conclusion: By induction, T(n) >= n for all n. So T(n) (- \Omega(n). Upper bound: Proof that T(n) <= 33 n^{log_4 5} - 20 n - 19, by complete induction on n >= 2. Base Cases: The following table shows the claim for n = 2, 3, 4, 5, 6, 7. n | T(n) | 33 n^{log_4 5} - 20 n - 19 --------------------------------------- 2 | 13 | 14.79024325749304... 3 | 18 | 39.15022768201075... 4 | 25 | 66 5 | 30 | 94.79275568170197... 6 | 35 | 125.19194065405338... 7 | 76 | 156.96747594825649... Ind. Hyp.: Suppose n >= 8 and \-/ j (- {2,3,...,n-1}, T(j) <= 33 j^{log_4 5} - 20 j - 19. Ind. Step: T(n) = 2 T(|_n/4_|) + 3 T(|^n/6^|) + 5 n (by definition of T(n), since n >= 8 > 1) <= 5 T(|_n/4_|) + 5 n (since T is increasing and |^n/6^| <= |_n/4_| for n >= 8) <= 5 (33 |_n/4_|^{log_4 5} - 20 |_n/4_| - 19) + 5 n (by the IH, since 2 <= |_n/4_| < n for n >= 8) <= 5 (33) (n/4)^{log_4 5} - 5 (20) (n-3)/4 - 5 (19) + 5 n (since (n-3)/4 <= |_n/4_| <= n/4, so -|_n/4_| <= -(n-3)/4) <= 5 (33) n^{log_4 5}/4^{log_4 5} - 25 n + 5 n + 75 - 95 <= 33 n^{log_4 5} - 20 n - 20 < 33 n^{log_4 5} - 20 n - 19 Conclusion: By induction, T(n) <= 33 n^{log_4 5} - 20 n - 19 for all n >= 2. So T(n) (- O(n^{log_4 5}). Note: This depends on fact that T(n) is increasing. I didn't realize this until it was too late to announce it -- students will NOT be penalized for making this assumption without proof. 2. (a) Suppose h (- N and T is a height-balanced binary tree with height h+1 that contains s(h+1) nodes. By definition, there is a path from the root of T to one of its leaves that contains exactly h+1 edges. Without loss of generality, suppose this path starts with an edge to the left child of the root. The subtree T_L rooted at the left child is a height-balanced binary tree (because T is height-balanced) and it has height h (because it contains the portion of the path with h+1 edges in T, without its first edge). Hence, the number of nodes in T_L is >= s(h) -- it may be greater because we don't know that T_L contains the smallest number of nodes in all height-balanced binary trees of height h. But then, s(h+1) (the number of nodes in T) is greater than size(T_L) (since T contains all of T_L plus at least one root), which is greater than or equal to s(h), i.e., s(h+1) > s(h). By universal generalization, \-/ h, s(h+1) > s(h). (b) By convention, the height of the empty tree is -1 so s(-1) = 0. The singleton tree (with exactly one node) is the only one with height 0, so s(0) = 1. For all h >= 1, consider a height-balanced binary tree T of height h, and let's think about how to make sure T contains the smallest possible number of nodes. Since T has height h, one of its subtrees must have height h-1, and the smallest number of nodes this can contain is, by definition, s(h-1). Since T is height-balanced, the other subtree has height at least h-2, so to keep T as small as possible, the other subtree must have height h-2 and contain at least s(h-2) nodes. Overall, then, T must contain at least 1 (for the root) + s(h-1) (for one subtree) + s(h-2) (for the other subtree) nodes. Overall, this gives the following recurrrence: s(-1) = 0, s(0) = 1, s(h) = 1 + s(h-1) + s(h-2) \-/ h >= 1. (c) By induction on h. Base Cases: - s(0) = 1 >= 1 = \phi^0 - s(1) = 1 + s(0) + s(-1) = 2 >= \phi = \phi^1. Ind. Hyp.: Suppose h > 1 and s(j) >= \phi^j for 0 <= j < h. Ind. Step: Since h > 1, 0 <= h-2 < h-1 < h and s(h) = 1 + s(h-1) + s(h-2) [by recurrence] >= 1 + \phi^{h-1} + \phi^{h-2} [by IH] = 1 + \phi^{h-2} (\phi + 1) = 1 + \phi^{h-2} \phi^2 [by property of \phi] = 1 + \phi^h > \phi^h Conclusion: By induction, \-/ h, s(h) >= \phi^h. (In fact, \-/ h >= 1, s(h) > \phi^h -- s(h) = \phi^h only for h=0.) (d) Suppose T is a height-balanced binary tree with n nodes, and height h. By definition of s(h), n >= s(h). By part (c), s(h) >= \phi^h. Hence, n >= \phi^h, i.e., \phi^h <= n and taking logs on both sides, we get h <= log_{\phi} n. Since T was arbitrary, this holds for all height-balanced binary trees. 3. (a) Proof that Fib1(n) returns F_n, \-/ n (- N. Base Case: - Fib1(0) returns 0 = F_0. - Fib1(1) returns 1 = F_1. Ind. Hyp.: Suppose n > 1 and Fib1(j) returns F_j for 0 <= j < n. Ind. Step: Consider the call Fib1(n). Since n > 1, 0 <= n-2 < n-1 < n so by the IH, the value returned is Fib1(n-1) + Fib1(n-2) = F_{n-1} + F_{n-2} = F_n. Conclusion: \-/ n, Fib1(n) returns F_n. (b) Proof that Fib2(n) returns [F_{n-1}, F_n], \-/ n (- N. Base Case: - Fib2(0) returns [1, 0] = [F_{-1}, F_0]. - Fib2(1) returns [0, 1] = [F_0, F_1]. Ind. Hyp.: Suppose n > 1 and Fib2(j) returns [F_{j-1}, F_j] for 0 <= j < n. Ind. Step: Consider the call Fib2(n). Since n > 1, 0 <= n-2 < n-1 < n so by the IH, F = [F_{n-2}, F_{n-1}] after the recursive call. The value returned is [F_{n-1}, F_{n-2} + F_{n-1}] = [F_{n-1}, F_n]. Conclusion: \-/ n, Fib2(n) returns [F_{n-1}, F_n]. (c) Proof that Fib3(n) returns [F_{n-1}, F_n], \-/ n (- N. Base Case: - Fib3(0) returns [1, 0] = [F_{-1}, F_0]. - Fib3(1) returns [0, 1] = [F_0, F_1]. Ind. Hyp.: Suppose n > 1 and Fib3(j) returns [F_{j-1}, F_j] for 0 <= j < n. Ind. Step: Consider the call Fib3(n). Case 1: If n is even, then n >= 2, so 0 <= n/2 < n and by the IH, F = [F_{n/2-1}, F_{n/2}] after the recursive call. The value returned is [F_{n/2-1}^2 + F_{n/2}^2, 2 F_{n/2-1} F_{n/2} + F_{n/2}^2] = [F_{n-1}, F_n] (by the properties given in the question). Case 2: If n is odd, then n >= 3, so 0 <= (n-1)/2 < n and by the IH, F = [F_{(n-1)/2-1}, F_{(n-1)/2}] after the recursive call. The value returned is [2 F_{(n-1)/2-1} F_{(n-1)/2} + F_{(n-1)/2}^2, F_{(n-1)/2}^2 + (F_{(n-1)/2-1} + F_{(n-1)/2})^2] = [F_{n-1}, F_{(n+1)/2-1}^2 + F_{(n+1)/2}^2] = [F_{n-1}, F_n] (by the properties given in the question). Conclusion: \-/ n, Fib3(n) returns [F_{n-1}, F_n]. BONUS! (a) T_3(n) satisfies the recurrence: T_3(0) = T_3(1) = 6, T_3(n) = T_3(|_n/2_|) + 25 \-/ n > 1. Repeated substitution yields T_3(n) = 25 lg n + 6. Proof by induction on n >= 1 that T_3(n) = 25 |_lg n_| + 6. BC: T_3(1) = 6 = 25 |_lg(1)_| + 6. IH: Suppose n > 1 and T_3(j) = 25 |_lg(j)_| + 6 for 1 <= j < n. IS: Since n > 1, 1 <= |_n/2_| < n and T_3(n) = T_3(|_n/2_|) + 25 [by definition of T_3] = 25 |_lg(|_n/2_|)_| + 6 + 25 [by IH] Case 1: n is even, so |_n/2_| = n/2 = 25 |_lg(n) - lg(2)_| + 25 + 6 = 25 |_lg n_| - 25 + 25 + 6 = 25 |_lg n_| + 6; Case 2: n is odd, so |_n/2_| = (n-1)/2 = 25 |_lg(n-1) - lg(2)_| + 25 + 6 = 25 |_lg(n-1)_| - 25 + 25 + 6 = 25 |_lg n_| + 6 since |_lg(n-1)_| = |_lg(n)_| for all odd n (property given in lecture summary for week 5). In all cases, T_3(n) = 25 |_lg n_| + 6, as desired. T_2(n) satisfies the recurrence: T_2(0) = T_2(1) = 6, T_2(n) = T_2(n-1) + 11 \-/ n > 1. This has solution T_2(n) = 11 n - 5, \-/ n >= 1: BC: T_2(1) = 6 = 11 - 5. IH: Suppose n > 1 and T_2(j) = 11 j - 5 for 1 <= j < n. IS: Since n > 1, T_2(n) = T_2(n-1) + 11 [by definition of T_2] = 11(n-1) - 5 + 11 [by IH] = 11 n - 5. T_1(n) satisfies the recurrence: T_1(0) = T_1(1) = 5, T_1(n) = T_1(n-1) + T_1(n-2) + 8 \-/ n > 1. As mentioned in class, T_3(n) is proportional to \phi^n. Proof by induction that 8 \phi^n - 8 <= T_1(n) <= 13 \phi^n - 8. BC: - T_3(0) = 5 >= 0 = 8 \phi^0 - 8, T_3(0) = 5 <= 5 = 13 \phi^0 - 8. - T_3(1) = 5 >= 4.944... = 8 \phi^1 - 8, T_3(1) = 5 <= 13.034... = 13 \phi^1 - 8. IH: Suppose n > 1 and 8 \phi^j - 8 <= T_1(j) <= 13 \phi^j - 8 for 0 <= j < n. IS: Since n > 1, T_1(n) = T_1(n-1) + T_1(n-2) + 8 [by definition of T_1] >= 8\phi^{n-1} - 8 + 8\phi^{n-2} - 8 + 8 [by IH] = 8 \phi^{n-2} (\phi + 1) - 8 - 8 + 8 = 8 \phi^{n-2} \phi^2 - 8 = 8 \phi^n - 8; T_1(n) = T_1(n-1) + T_1(n-2) + 8 [by definition of T_1] <= 13\phi^{n-1} - 8 + 13\phi^{n-2} - 8 + 8 [by IH] = 13 \phi^{n-2} (\phi + 1) - 8 - 8 + 8 = 13 \phi^{n-2} \phi^2 - 8 = 13 \phi^n - 8. (b) Operations per second = 10^9 operations per minute = 6 * 10^10 operations per hour = 36 * 10^11 operations per day = 864 * 10^11 For Fib1, we want T_1(n) <= 864 * 10^11, and we know T_1(n) >= 8 \phi^n - 8, so we get 8 \phi^n - 8 <= T_1(n) <= 864 * 10^11 \phi^n <= (864 * 10^11 - 8) / 8 n <= log_{\phi}((864 * 10^11 - 8) / 8) = 62.36... i.e., the largest input size is n = 62. For Fib2, we want T_2(n) <= 864 * 10^11, and we know T_2(n) = 11 n - 5, so we get 11 n - 5 <= 864 * 10^11 n <= (864 * 10^11 + 5) / 11 = 7.854545454545 * 10^12 i.e., the largest input size is about n = 7,854,545,454,545. For Fib3, we want T_3(n) <= 864 * 10^11, and we know T_3(n) = 25 |_lg n_| + 6, so we get 25 |_lg n_| + 6 <= 864 * 10^11 |_lg n_| <= (864 * 10^11 - 6) / 25 n <= 2^{(864 * 10^11 - 6) / 25} (roughly) i.e., n ~= 2^{3455999999999} ~= 10^{1,040,359,665,014}.