Name: SUBSETSUM

Input: V = {vi}n

, T (a set of positive integers and a target)

Goal: Find the subset of V with the largest sum which does not exceed T .
Sample Instance 1: V = {23, 12, 8, 5, 2}, T = 33
Optimal Solution to Sample Instance 1: 23 + 8 + 2 = 33
Sample Instance 2: V = {23, 12, 8, 5, 2}, T = 29
Optimal Solution to Sample Instance 2: 23 + 5 = 28


Name: CIRCULARSHIFT
Input: A sorted integer array X which has been circularly shifted by an amount 0 ≤ d < X.length (circularly shifted means that each item has been moved to a position d cells later, but if this causes the item to move beyond the end of the array then it wraps around to the front).
Goal: Find the value of d (the amount it was shifted).
Sample Instance 1: X = Solution to Sample instance 1: 4 Sample Instance 2: X =
Solution to Sample Instance 2: 1


Name: LONGESTINCREASINGSUBSEQUENCE
Input: An integer array X
Goal: Find the length of the longest (not necessarily consecutive) increasing subsequence contained in X.
Sample Instance 1: X =
Optimal Solution to Sample Instance 1: 4 (4,5,6,8)
Sample Instance 2: X =
Optimal Solution to Sample Instance 2: 6 (2,3,5,7,8,9)

Name: MINCOINS
Input: A sorted integer array of coin values V and a target T .
Goal: Find the minimum number of coins necessary to exactly reach target T .
Sample Instance 1: V = T = 177
Optimal Solution to Sample Instance 1: 7 (1,1,5,10,10,50,100)
Sample Instance 2: V = T = 26
Optimal Solution to Sample Instance 2: 3 (7,7,12)


Problem 1. (10 points) State the definition of f (n) = O(g(n)).
Let f (n) = (3n2 + 2n − 7)(6n + 1) lg(n2 − 2n + 6), g(n) = n3 lg(n), and show that f (n) = O(g(n)) for these functions.

Problem 2. (10 points) The following greedy algorithm has been suggested for the SUBSETSUM problem. Sort the items in set V from largest to smallest. Start with an empty subset. Go through the items one by one adding each value to the subset if it does not cause the sum to exceed the target.
If this algorithm finds the optimal solution to every instance, explain why it does.
If this algorithm finds a non-optimal solution to some instance, give such an instance.

Problem 3. (10 points) The following greedy algorithm has been suggested for the MINCOINS problem. While the target T > 0, add one coin with the largest value no greater than T and reduce T by that amount.
This algorithm is not always optimal (see the second example on the cover page). Prove that it is optimal for any T when V = {1, 5, 10, 25, 50, 100}.
Problem 4. (10 points) Imagine that you are the only “network person” at a company with many buildings. Currently building A is connected to the internet, but the rest are not. Assume that the cost to connect two buildings together (digging a trench and laying fiber optic cable) is given by the weight on the edge between the buildings. Describe a greedy algorithm which connects all buildings to building A (and thus the internet) with minimum cost. Then run your algorithm on the instance below.


Problem 5. (10 points) Describe a Θ(lg n) time, divide and conquer method to solve the CIRCULARSHIFT
problem. (Note that using a linear search is neither Θ(lg n) nor divide and conquer.)

Problem 6. (10 points) As part of designing a Dynamic Programming algorithm for LONGESTINCREASINGSUB- SEQUENCE, define LIS[i] ≡ the length of the longest increasing subsequence ending at (and using) position i. Give the base case and the general recurrence.
LIS[0] = LIS[i] =

Problem 7. (10 points) Design a Dynamic Programming algorithm for MINCOINS problem. In other words, define a table which can hold solutions to the nested subproblems and give the base cases and the general recurrence.

Problem 8. (10 points) The diagrams below represent instances of the NETWORKFLOW problem and proposed solutions. Each instance is a weighted, directed graph (weights being the second number on each edge) with a source and sink (S and T). The proposed solution (which should be a flow that maximizes the water sent from S to T) is given by the first number on each edge. For both:
If the proposed solution is incorrect explain how/why it is incorrect and fix it. If it is correct then give a convincing argument for why it is a maximum flow.