Order questions   For each part, answer True or False, and justify. All logarithms are base 2.

(a)  ^n ∈ O(n).

True.  A smaller exponent such as n1/2  grows slower than a larger one, and O means that the growth is at most that of the function in the O .

(b)  ^n ∈ Θ(n)

False. A smaller exponent is strictly slower scaling than a larger one, and Θ says that the growths are within constant factors of each other, almost the same.

(c)  10n2 + 7 ∈ Θ(4n2 + 2n + nlog n).

True. The maximum term for both sides is Θ(n2 ).

(d) If f ∈ Θ(g) then f + g ∈ Θ(g) for any non-negative functions f,g .

True. If f ∈ Θ(g), then there are k,c1 ,c2  > 0 so that c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ k . Then adding g(n) to all of the above, (c1 +1)g(n) ≤ f(n)+g(n) ≤ (c2 +1)(g(n) for n ≥ k, so f +g ∈ Θ(g).

Solving recurrences  For each of the following recurrences, give a closed form and justify your answer either by an induction argument or unravelling.

1.  A(1) = 1,A[n] = 5A[n − 1] for n ≥ 2

A(n)  =  5A(n − 1)  =  5 * (5A(n − 2))  =  53 A[n − 3]  =  ...  =  5  A[nk  − k].   Letting  k  =  n − 1,

Looking at a few values, B(1) = 2,B(2) = 3/2B(1) = 3, B(3) = 4/3B(2) = 4.  So we conjecture B(n) = n+1. This is true for n = 1. Assume B(n) = n+1. Then B(n+1) = (1+(1/(n+1)))B(n) = ((n+2)/(n+1))B(n) = ((n+2)/(n+1)) * (n+1) = n+2. So by induction, B(n) = n+1 for all n.

3.  C[1] = C[2] = C[3] = C[4] = 1,C[n] = 2C[n − 4] for n ≥ 5.

C(n) = 2C(n − 4) = 4C(n − 8) = 8C(n − 12) = ...2k C(n − 3k).  Using this with k =「(n + 1)/3⌋,

D(1) = 1 = 2 − 1,D(2) = 1 + 1/2 = 2 − 1/2,D(3) = 1 + 1/2 + 1/4 = 2 − 1/4 so we conjecture that

5. E[1] = 2,E[n] = (E[n − 1])2  for n ≥ 2.

Iterative Algorithms and Loop Invariants   In an array, A[1...n], we’ll say a  rise  is a pair of indices

MaxRise(A[1..n]: array of n integers

1. min = A[1], maxrise = 0

2. FOR I = 2 to n do:

3.      min = minimum(A[I],min)

4.      IF A[I] − min > maxrise THEN maxrise = A[I] − min

(a) State two loop invariants that together can be used to show the algorithm MaxRise is correct. (b) Prove your loop invariants from part (a).

(c) Conclude from the loop invariant that the algorithm MaxRise is correct.

We do the above three steps together. We first show that after the iteration when I = T, min is the smallest value in A[1..T]. Before the loop we consider T = 1, and min = A[1] is the only element in A[1..T].  Assume that after I = T, min is the smallest element in A[1..T].  If A[T + 1] is the smallest value in A[1...T + 1], then it will be no larger than the minimum value in A[1..T], which we are assuming is min.  Then when we assign min = minumum(A[T + 1],min) in this loop, we will have min = A[T + 1].  If A[T + 1] is not the smallest value, then it is larger than the actual smallest value, which will be in A[1...T] and will be equal to min. So the value of min will not be changed, and it will still be the overall smallest in A[1..T + 1]. Thus, by induction, min is always the smallest value in A[1..T].

Then we show that after iteration when I = T, maxrise is the largest rise within A[1..T].  There is no rise within A[1] so the definition says to define the maximum rise to be 0, which is what we initialize maxrise to. So this claim is true before the loop starts. Assume after I = T, maxrise is

the largest rise within A[1..T].  Any rise whose second element is T + 1 has value A[T + 1] − A[J]

for some J in 1..T .  The largest such value is A[T + 1] − min1≤J≤TA[J] = A[T + 1] − min, by the

A[1..T], and our algorithm does not change the value for maxrise.  In either case, maxrise stays the maximum value of a rise within A[1..T + 1].

So by induction, maxrise is always the maximum rise in A[1..T], and at the end of the loop, T = n, so maxrise is the maximum rise in the entire array.

(d) Describe the running time of this algorithm in Θ notation, assuming that comparisons and arith- metic operations take constant time. Justify your answer.

Within the main FOR loop, we perform only a fixed number of constant time operations. The FOR

loop is executed n − 1 times, and the rest of the algorithm is constant time. Thus, T(n) ∈ Θ(n).

Recursive Algorithms and Recurrences  In an array, A[1...n], we’ll say a rise is a pair of indices 1 ≤ I <

J ≤ n with A[I] < A[J], and the maximum rise is the maximum value of A[J] − A[I] for all such rises.

MaxRise(A[1..n] : array of n integers

1. IF n = 1 THEN return (A[1], 0)

2.  (oldmin,oldmaxrise) == MaxRise(A[1..n − 1)

3. newmin = minimum(oldmin,A[n])

4. newmaxrise = maximum(oldmaxrise,A[n] − oldmin)

5.  Return (newmin,newmaxrise).

(a) Prove by induction on n that for any input array, the algorithm MaxRise returns the pair with

the minimum value in the array and the maxrise of the array.

If n = 1, the only element, and hence the minimum element, is A[1], and there are no rises, so the problem says to define the maxrise as 0.  Since these values are what we return in this case, the algorithm is correct when n = 1.

Assume the algorithm correctly finds the minimum value and maximum rise for arrays of size n. Let A[1..n + 1] be an array of size n + 1.  Then by induction, oldmin is the minimum value of an element in A[1..n] and oldmaxrise is the maximum value of a rise within A[1..n].  If A[n + 1] is smaller than oldmin, therefore, it is the smallest in the entire array, and newmin is assigned A[n + 1], the overall minimum element in the array. Otherwise, newmin = oldmin and oldmin is still the smallest element in the array.  As in the iterative case, the maximum rise in A[1..n + 1] is either the maximum rise in A[1..n] or has second element n + 1, in which case it has value