Transcript
Fundamental Algorithms CSCI-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. array. Prove correctne correctness ss of your algorithm algorithm using a loop invariant invariant (refer to pages pages 19-20 in section 2.1 of CLRS for an example), state the running time. Solution:
• Algorithm Algorithm pseudoco pseudocode: de: d ef e f f i nd n d _ ma ma x ( a ) : i f l en en ( a) a) = = 0 : r e tu tu r n - 1 max = 0 f or or i i n r an a n ge g e ( 1 , l en e n ( a )) )) : i f a [i [ i ] > a [ ma ma x ]: ]: max = i r e tu t u r n m ax ax
• We prove the algorithm correct 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 a[0..i-1]. 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 array is guaranteed 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 There are two possible possible executions executions of the iteration iteration for i = k: a[k] > a[ma a[max] x]. Given that a[max] is the largest element in a[0..k-1], a[k] is the 1. a[k] 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. a[k] <= a[ma a[max] x]. a[k] is no greater that the largest element in a[0..k-1] and 2. a[k] 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 maintenance, at the beginning of iteration for i = len(a), a[max] is the a[0..len(a)-1]. i = len( len(a) a) causes the loop to terminate largest element in subarray a[0..len(a)-1] without executing the t he body, body, max is not changed, and the invariant holds.
1
1 2 3 4 5 6 7 8
Observing that a[0..len(a)-1] is the entire array and a[max] is thus the largest element in the entire array, we conclude that the algorithm is correct. • Passing in an empty array will execute a constant number of operations on lines 2-3, so the algorithm runs in Θ (1) time in best case. • In all other cases, a constant number of operations will be executed on lines 4 and 8, and at most linear in len(a) number of operations on lines 5-7. Note that while line 7 is executed conditionally, lines 5-6 are always executed a linear in len(a) number of times. Therefore, we can provide a tight bound of Θ(len(a)) for both average and worst cases. Problem 2. (2
points) The Lucas numbers are defined as follows:
2 L = 1 L − + L −
if n = 0 if n = 1
n
n 1
if n > 1
n 2
Prove by induction the closed-form expression for the n -th Lucas number: L n = ϕ n + (1
− ϕ)
n
Where ϕ is the golden ratio:
1+ 5 ϕ= 2 Solution:
The inductive step for L n+1 will have to rely on L n and L n−1 , so we need to show that the statement holds for two base cases: for n = 0, L 0 = ϕ 0 + (1
0
= 2,
for n = 1, L 1 = ϕ 1
1
= 1.
− ϕ) + (1 − ϕ )
Similarly, the inductive hypothesis needs to include two cases. We assume that for some n and n + 1: L n = ϕ n + (1 L n+1 = ϕ n+1
n
− ϕ) , + (1 − ϕ )
n+1
.
n+2
.
For the inductive step let us show that: L n+2 = ϕ n+2 + (1
− ϕ)
(IS.1)
By definition of L n and the inductive hypothesis: L n+2 = L n+1 + L n = ϕ n+1 + (1
− ϕ) 2
n+1
+ ϕ n + (1
n
− ϕ) .
Observing that: 2
ϕ = ϕ + 1, 2
k
k
ϕ ϕ = ϕ (ϕ + 1), ϕ
k+2
= ϕ k+1 + ϕ k .
We can complete the inductive step by rewriting (IS.1) as: L n+2 = ϕ n+1 + ϕ n + (1 = ϕ n+2 + (1
− ϕ)
− ϕ)
n+2
n+1
+ (1
.
− ϕ)
n
With both the base case and the inductive step in place, we conclude that the statement holds for all natural numbers n . Problem 3. (3
points) State formally, then prove or disprove the following conjectures:
(a) Being in Θ is an equivalence relation. (b) Maximum of two functions is in Θ of their sum. (c) Sum of two functions is in Θ of their maximum. Solution:
(a) To show that binary relation "is in Θ of" is an equivalence relation we need to show that it is reflexive, symmetric, and transitive. • Reflexivity: f (n) = Θ ( f (n)). Observe that: 0
≤ c f (n) ≤ f (n) ≤ c f (n) 1
2
for c 1 = c 2 = 1 and any n 0 > 0. • Symmetry: f (n) = Θ( g(n)) if and only if g(n) = Θ ( f (n)). Let us show that: If f (n) = Θ( g(n)) then g(n) = Θ( f (n)). By definition of Θ :
≤ c g(n) ≤ f (n) ≤ c g(n) for all n ≥ n and some positive c , c , n . 0
1
2
0
1
2
(S.1)
0
Dividing (S.1) by c 1 gives: 0
≤ g (n) ≤
1 f (n) c1
c2
≤ c g(n).
(S.2)
≤ c g(n) ≤ c1 f (n) ≤ g (n).
(S.3)
1
Dividing (S.1) by c 2 gives: 0
c1 2
2
3
Combining (S.2) and (S.3) gives: 0
≤ c1 f (n) ≤ g (n) ≤ c1 f (n). 2
1
Or, in canonical form:
≤ c f (n) ≤ g(n) ≤ c f (n) 1 1 for all n ≥ n and c = , c = , n = n . c c 0
1
2
0
1
2
0
2
0
1
The proof for converse is analogous. • Transitivity: If f (n) = Θ ( g(n)) and g(n) = Θ(h(n)) then f (n) = Θ(h(n)). By definition of Θ:
≤ c g(n) ≤ f (n) ≤ c g(n) for all n ≥ n and some positive c , c , n .
(T.1)
≤ ch(n) ≤ g(n) ≤ c h(n) for all n ≥ n and some positive c , c , n .
(T.2)
0
1
2
0
0
1
1
2
0
2
0
1
2
0
Multiplying (T.2) by c 2 gives: 0
≤ c ch(n) ≤ c g(n) ≤ c c h(n). 2 1
2
2 2
Combining the above with (T.1) gives:
≤ c g(n) ≤ c c h(n), f (n) ≤ c c h(n).
f (n)
2
2 2
2 2
(T.3)
Multiplying (T.2) by c 1 gives: 0
≤ c ch(n) ≤ c g(n) ≤ c c h(n). 1 1
1
1 2
Combining the above with (T.1) gives: c1 c1 h(n)
≤ c g(n) ≤ f (n), c c h(n) ≤ f (n). 1
1 1
Combining (T.3) and (T.4) gives: 0
≤ c ch(n) ≤ f (n) ≤ c c h(n). 1 1
2 2
Or, in canonical form: 0
≤ c h(n) ≤ f (n) ≤ c h(n) 1
2
for all n ≥ n0 and c 1 = c 1 c1 , c2 = c 2 c2 , n0 = max(n0 , n0 ). 4
(T.4)
(b) Let us show that max( f (n), g(n)) = Θ( f (n) + g (n)): Observe that for non-negative f (n) and g(n):
≤ f (n) + g (n) ≤ 2max( f (n), g(n)), 0 ≤ max( f (n), g(n)) ≤ f (n) + g (n).
0
Assuming f (n)
≥ 0 for all n ≥ n and g(n) ≥ 0 for all n ≥ n, we can write: 0 ≤ c ( f (n) + g (n)) ≤ max( f (n), g(n)) ≤ c ( f (n) + g (n)) 1 for c = , c = 1, and all n ≥ max(n , n ). 2 0
0
1
2
1
(c) The symmetry of relation "is in
2
Θ of"
0
0
established in (a):
max( f (n), g(n)) = Θ( f (n) + g (n)) if and only if f (n) + g (n) = Θ(max( f (n), g(n))).
Taken with (b) implies: f (n) + g (n) = Θ(max( f (n), g(n))). Problem 4. (4
points) Rank the following function forms by order of growth: constant, exponential, linear, linearithmic, logarithmic, polynomial. Formulate your answer as five comparisons of the form: • Informal statement about relation between orders of growth of two function forms. • Formal statement in terms of limits or asymptotic notation (feel free to switch between the two if it makes your proofs easier). • Proof of the formal statement. Solution: We
rank the function forms using ω-notation and the equivalent limit definition: f (n) = ω( g(n)) if and only if lim
f (n)
→∞ g(n)
n
=
∞.
LR
(= indicates application of L’Hopital’s rule.) • Logarithmic functions grow asymptotically faster than constant functions. log n = ω(c) for all c > 0: log n = n→∞ c lim
5
∞.
• Linear functions grow asymptotically faster than logarithmic functions. n = ω(log n): lim
n
n
→∞ log n
1
LR
= lim
→∞
n
1 n
= lim n =
→∞
n
∞.
• Linearithmic functions grow asymptotically faster than linear functions. n log n = ω(n): lim
n
n log n
= lim log n =
n
→∞
n
→∞
∞.
• Polynomial functions grow asymptotically faster than linearithmic functions. nd = ω(n log n) for all d > 1: lim
nd
→∞ n log n
n
= lim
nd −1
→∞ log n
n
(d
LR
= lim n
→∞
d 2
− 1)n − 1 n
= (d
d 1
− 1) lim n − = ∞. →∞ n
• Exponential functions grow asymptotically faster than polynomial functions. a n = ω(nd ) for all a > 1 and d > 0, k = d :
a n LR ln2 a a n LR ln a = = = lim lim lim n→∞ nk k n→∞ nk−1 k(k 1) n→∞ nk−2 an
LR
−
6
···
lnk a = lim a n = n k! →∞
LR
∞.
