1. For each recurrence relation below, indicate show and justify its theta class:
a. T(1) = 1; T(n) = 2T(n/2)+5
b. T(1) = 1; T(n) = 2T(n/2) + 2n
c. T(1) = 1; T(n) = T(3n/4) + T(n/6) + 5n
d. Solve the following recurrence T(1) = 1; T(n) = 3T(n/3) + 3
e. Let a and b be real numbers such that 0
f. Explain why the best case running time of Insertion Sort is O(n) .
Dynamic Programming
2. Assume k is odd and let O(n,k) be the number of ways to write n as the sum of odd positive integers each at most k but not necessarily distinct. Find a recurrence for O(n,k) and explain it.
3. Consider the following recurrence (given a sequence pi) :
with C[i,i] = 0
a. Draw the table dynamic programming would use to implement this.
b. Write the dynamic programming code to compute C.
Greedy Algorithms
4. In the bin-packing problem, you are given a set of objects with sizes s1, s2, ... ,sn where 0
a.Give a greedy strategy for this problem.
b. (What order would you have to process the items in order for your solution to be optimal?
5. Consider the following algorithm. T is a binary tree.
fred(T)
{
if (T is null)
return 0
else return (fred(left child of T) + fred(right child of T)
}
a. Give the recurrence relation for the fred function. You do not need to solve the equation, but remember the basis.
b. What does the function fred do?
Mergeable Heaps
6. Why did Binomial heaps NOT require the mark bits and the rules about losing two children?
7. The H be a fibonacci heap with a B4 and a B5 with the min at the root of the B5. Show the structure that would result from ExtractMin(H).
Applying what we have learned
8. Find the most efficient solution for each of the problems below and analyze its running time. In each case, you are given n points in the plane,
Hint, the distance from the origin to the ith point is
a. Find the smallest circle, centered at the origin, containing all of the points in its interior.
b. Determine whether it is possible to draw a circle centered at the origin containing two or more of the points on its boundary.
c. Given k satisfying 0<=k<=n, find a circle, centered at the origin, such that at most k of the points are in the interior of the circle and at most n-k of the points are in the exterior of the circle.
9. Graph Algorithm Details
a. Define the three types of shortest path problems.
b. Give an example where the shortest path tree from Dijkstra's algorithm is not a minimum spanning tree.
c. Show the DFS forest resulting from running DFS on the graph described by this adjacency list. Label each node with its start and finish times.
1: 2, 5,
2: 1, 3, 5
3: 1, 2, 5
4: 2, 3, 6
5: 1, 2, 3
6: 2, 3, 4
Running Shortest Path Algorithms
10. Show the execution of Prim's algorithm starting at node A on the following graph. Redraw the diagram for each edge that is added (yes, you can write neatly on this entire page)
NP-Completeness
11. Prove that this problem is in NP: Given n, a number of dice, there are at least k ways of rolling a given value, y.
12. Explain exactly what you have to do to prove that a problem is NP-Complete
13. Which of the following statements is true for all problems X and Y in NP such that X is reducible to Y in polynomial time? (T or F after each one - yes, that can be outside of a box)
a. If Y is NP-complete, then X is NP-complete
b. If Y is in P, then X is in P
c. If X is NP-complete, then Y is in P
d. If Y is not in P, then X is not in P
14.We said that if we had a polynomial time solution to an NP-complete problem X, we would have a polynomial-time solution to every problem in NP. Explain the polynomial-time solution for an arbitrary problem Y in NP.
15.If you have to solve a problem that is NP-Complete, what options do you have?