Algorithms and Computational Complexity

Sample Midterm

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

- (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**. - (25 points) Recall the
**Quicksort**algorithm discussed in class and assume that we are running it on**distinct**elements.- 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? - 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? - 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**. - Solve the recurrence for part (c).

- What it the
- (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.) - (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

- Use
**Dynamic Programming**to rewrite this function to be much more efficient. - What is the
**Time**and**Storage Space**

- Use