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

(a)pn 2 O(n).

(b)pn 2 Θ(n)

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

(d) If f 2 Θ(g) then f + g 2 Θ(g) for any non-negative functions f, 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

2.  B[1] = 2, B[n] = (1 + (1/n))B[n - 1] for n ≥ 2.

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

4.  D[1] = 1, D[n] = D[n - 1] + 1/2n- 1  for n ≥ 2.

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

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.  (If the array is in decreasing order, we deine the max rise to be 0.)  Consider the following interative algorithm to compute the maximum rise in an array:

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

Iterative Algorithms and Loop Invariants      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

(Skip one or two parts below on midterm)

(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.

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

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. (If the array is in decreasing order, we deine the max rise to be 0.)  Consider the following recursive algorithm that computes both the minimum value and the maximum rise in an array:

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).