Fundamental AlgorithmsCSCI-GA.1170-001/Summer 2016 Solution to Homework 1 Problem 1. (2 points) Give an algorithm to compute the index of the maximum element in an array. Prove correctness of your algorithm using a loop invariant (refer to pages 19-20 in section 2.1 of CLRS for an example), state the running time. Solution: • Algorithm pseudocode: def find_max (a ): if len (a) == 0: return -1 max = 0 for i in range (1 , len (a )): if a[i] > a[ max ]: max = i return max • We prove the algorithm correct using the following loop invariant: At the start of each iteration of the for loop on lines 5-7, a[max] is the largest element in subarray a[0..i-1]. Initialization: Before the first loop iteration, max = 0, i = 1 and therefore a[max] is correctly the largest (and only) element in a[0..0]. Note that the array is guaranteed to have at least one element by the guard condition on lines 2-3. Maintenance: Assuming that a[max] is correctly the largest element in a[0..i-1] at the start of iteration for i = k, let us show that this property holds at the start of iteration for i = k+1. There are two possible executions of the iteration for i = k: 1. a[k] > a[max]. Given that a[max] is the largest element in a[0..k-1], a[k] is the new largest element in a[0..k]. After line 7 updates max and i is incremented to k+1 in line 5, a[max] is correctly the largest element in a[0..k] and the invariant holds. 2. a[k] <= a[max]. a[k] is no greater that the largest element in a[0..k-1] and thus cannot be the largest element in a[0..k]. max is not updated, so after i is incremented to k+1 in line 5, a[max] is still correctly the largest element in a[0..k] and the invariant holds. Termination: By maintenance, at the beginning of iteration for i = len(a), a[max] is the largest element in subarray a[0..len(a)-1]. i = len(a) causes the loop to terminate without executing the body, max is not changed, and the invariant holds. 1 1 2 3 4 5 6 7 8 L1 = ϕ 1 + (1 − ϕ)1 = 1. L0 = ϕ 0 + (1 − ϕ)0 = 2.1) .Observing that a[0. We assume that for some n and n + 1: L n = ϕ n + (1 − ϕ)n . so we need to show that the statement holds for two base cases: for n = 0. 2 (IS. for n = 1. For the inductive step let us show that: L n+2 = ϕ n+2 + (1 − ϕ)n+2 . lines 5-6 are always executed a linear in len(a) number of times. • Passing in an empty array will execute a constant number of operations on lines 2-3. we can provide a tight bound of Θ(len(a)) for both average and worst cases.len(a)-1] is the entire array and a[max] is thus the largest element in the entire array. L n+1 = ϕ n+1 + (1 − ϕ)n+1 . so the algorithm runs in Θ(1) time in best case. (2 points) The Lucas numbers are defined as follows: if n = 0 2 Ln = 1 if n = 1 L n−1 + L n−2 if n > 1 Prove by induction the closed-form expression for the n-th Lucas number: L n = ϕ n + (1 − ϕ)n Where ϕ is the golden ratio: p 1+ 5 ϕ= 2 Solution: The inductive step for L n+1 will have to rely on L n and L n−1 . the inductive hypothesis needs to include two cases. Note that while line 7 is executed conditionally. Therefore. Problem 2. • In all other cases.. Similarly. we conclude that the algorithm is correct. and at most linear in len(a) number of operations on lines 5-7. a constant number of operations will be executed on lines 4 and 8. By definition of L n and the inductive hypothesis: L n+2 = L n+1 + L n = ϕ n+1 + (1 − ϕ)n+1 + ϕ n + (1 − ϕ)n . By definition of Θ: 0 ≤ c10 g(n) ≤ f (n) ≤ c20 g(n) for all n ≥ n00 and some positive (S. (c) Sum of two functions is in Θ of their maximum. Observe that: 0 ≤ c1 f (n) ≤ f (n) ≤ c2 f (n) for c1 = c2 = 1 and any n0 > 0. ϕ k+2 = ϕ k+1 + ϕ k . Dividing (S. c10 c10 (S.1) c10 . Let us show that: If f (n) = Θ(g(n)) then g(n) = Θ( f (n)). we conclude that the statement holds for all natural numbers n. With both the base case and the inductive step in place. (b) Maximum of two functions is in Θ of their sum. then prove or disprove the following conjectures: (a) Being in Θ is an equivalence relation.1) by c10 gives: 0 ≤ g(n) ≤ c20 1 f (n) ≤ g(n). symmetric.1) as: L n+2 = ϕ n+1 + ϕ n + (1 − ϕ)n+1 + (1 − ϕ)n = ϕ n+2 + (1 − ϕ)n+2 .Observing that: ϕ 2 = ϕ + 1. Solution: (a) To show that binary relation "is in Θ of" is an equivalence relation we need to show that it is reflexive.1) by c20 gives: 0≤ c10 c20 g(n) ≤ 3 . • Reflexivity: f (n) = Θ( f (n)).2) 1 f (n) ≤ g(n). Problem 3. • Symmetry: f (n) = Θ(g(n)) if and only if g(n) = Θ( f (n)). c20 (S. (3 points) State formally. n00 . We can complete the inductive step by rewriting (IS. and transitive. ϕ k ϕ 2 = ϕ k (ϕ + 1). c20 .3) Dividing (S. n0 = max(n00 . Combining the above with (T. Or. Combining the above with (T.2) by c10 gives: 0 ≤ c10 c100 h(n) ≤ c10 g(n) ≤ c10 c200 h(n). c10 c100 h(n) ≤ f (n).3) Multiplying (T.1) gives: f (n) ≤ c20 g(n) ≤ c20 c200 h(n).3) and (T.3) gives: 0≤ 1 1 f (n) ≤ g(n) ≤ 0 f (n).4) . in canonical form: 0 ≤ c1 f (n) ≤ g(n) ≤ c2 f (n) 1 1 for all n ≥ n0 and c1 = 0 . f (n) ≤ c20 c200 h(n).4) gives: 0 ≤ c10 c100 h(n) ≤ f (n) ≤ c20 c200 h(n). n000 . c2 = c20 c200 . Combining (T. n00 .1) gives: c10 c100 h(n) ≤ c10 g(n) ≤ f (n).1) c10 . c2 c1 The proof for converse is analogous. 4 (T. (T. c200 .2) by c20 gives: 0 ≤ c20 c100 h(n) ≤ c20 g(n) ≤ c20 c200 h(n).2) c100 .Combining (S. n000 ). 0 c2 c1 Or. c2 = 0 . c20 . • Transitivity: If f (n) = Θ(g(n)) and g(n) = Θ(h(n)) then f (n) = Θ(h(n)). Multiplying (T. (T.2) and (S. By definition of Θ: 0 ≤ c10 g(n) ≤ f (n) ≤ c20 g(n) for all n ≥ n00 and some positive 0 ≤ c100 h(n) ≤ g(n) ≤ c200 h(n) for all n ≥ n000 and some positive (T. n0 = n00 . in canonical form: 0 ≤ c1 h(n) ≤ f (n) ≤ c2 h(n) for all n ≥ n0 and c1 = c10 c100 . n→∞ c lim 5 . n000 ).(b) Let us show that max( f (n). • Proof of the formal statement. Problem 4. g(n) LR (= indicates application of L’Hopital’s rule. exponential. (4 points) Rank the following function forms by order of growth: constant. g(n)) ≤ c2 ( f (n) + g(n)) 1 for c1 = . 2 (c) The symmetry of relation "is in Θ of" established in (a): max( f (n). we can write: 0 ≤ c1 ( f (n) + g(n)) ≤ max( f (n).) • Logarithmic functions grow asymptotically faster than constant functions. g(n)) = Θ( f (n) + g(n)) if and only if f (n) + g(n) = Θ(max( f (n). Formulate your answer as five comparisons of the form: • Informal statement about relation between orders of growth of two function forms. Solution: We rank the function forms using ω-notation and the equivalent limit definition: f (n) = ω(g(n)) if and only if lim n→∞ f (n) = ∞. and all n ≥ max(n00 . g(n)) ≤ f (n) + g(n). g(n))). c2 = 1. Taken with (b) implies: f (n) + g(n) = Θ(max( f (n). Assuming f (n) ≥ 0 for all n ≥ n00 and g(n) ≥ 0 for all n ≥ n000 . 0 ≤ max( f (n). g(n)) = Θ( f (n) + g(n)): Observe that for non-negative f (n) and g(n): 0 ≤ f (n) + g(n) ≤ 2 max( f (n). polynomial. log n = ω(c) for all c > 0: log n = ∞. linear. g(n))). g(n)). linearithmic. • Formal statement in terms of limits or asymptotic notation (feel free to switch between the two if it makes your proofs easier). logarithmic. n→∞ n→∞ n lim • Polynomial functions grow asymptotically faster than linearithmic functions. lim = lim = lim 1 n→∞ n→∞ n log n n→∞ log n n→∞ n • Exponential functions grow asymptotically faster than polynomial functions. n→∞ nk k n→∞ nk−1 k(k − 1) n→∞ nk−2 k! n→∞ lim 6 . n log n = ω(n): n log n = lim log n = ∞. k = dde: k a n LR ln a a n LR ln2 a a n LR LR ln a = lim = lim = · · · = lim a n = ∞. nd = ω(n log n) for all d > 1: nd nd−1 LR (d − 1)nd−2 = (d − 1) lim nd−1 = ∞. n→∞ n→∞ log n n→∞ n lim • Linearithmic functions grow asymptotically faster than linear functions.• Linear functions grow asymptotically faster than logarithmic functions. a n = ω(nd ) for all a > 1 and d > 0. n = ω(log n): n LR 1 = lim 1 = lim n = ∞.