DIRECTIONS:

• Closed book, closed notes.
• Answer the problems on the exam paper.
• Each problem starts on a new page.
• If you need extra space use the back of a page

1. (25 points) Prove by induction that when n>=2 is a power of 2, the recurrence T(n)=2T(n/2)+2 with the initial condition T(2)=1 has the precise solution T(n)=3n/2 -2.

2. (25 points) Recall the Quicksort algorithm discussed in class and assume that we are running it on distinct elements.

   1. What it the worst-case running time of Quicksort on an array of length n if the pivot is always chosen to be the first element of the array?

   2. What is the average-case running time of Quicksort on an array of length n if the pivot is always chosen to be the first element of the array?

   3. The median of a set is the middle element of the set in sorted order. There is an algorithm that computes the median of a set of size n in worst-case O(n) time. Suppose that in Quicksort, instead of using the first element of the array as a pivot, we computed the median element of the array and used it as the pivot.
      Write a recurrence describing the worst-case running time of this modified Quicksort algorithm on an array of length n.

   4. Solve the recurrence for part (c).

3. (25 points) Suppose you are given a directed acyclic graph G=(V,E) which has an integer reward r(v) associated with each vertex v in V. For every node v in V, we'd like to compute best-reward(v) which is the largest value of r(w) among all nodes w reachable from v in G. Describe an algorithm running in O(|V|+|E|) time that computes best-reward(v) for all nodes v in V and argue that it is both correct and has the desired running time.
   (Hint: use topological sort and consider the vertices in the reverse of this order.)

4. (25 points) Consider the following recursive function designed for integers m, n>=1 (don't worry about its meaning).

   Function Best-Match(m,n)
        if (m=1 or n=1) then
              return(1)
        else
              if (n is odd) then
                   k <- (n+1)/2
              else
                   k <- n/2
              endif
                   return(max{Best-Match(m,k)+Best-Match(m-1,n), Best-Match(n,m-1))
    
        endif
   end
   

   1. Use Dynamic Programming to rewrite this function to be much more efficient.

   2. What is the Time and Storage Space