Your textbook usually assumes that arrays are indexed starting at 1. Java/C++ have arrays indexed starting at 0.
If your answer to one of the quiz questions depends upon how an array is indexed, tell me what you are assuming.
Name: SubsetSum
Input: V = fvigni
=1; 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 = f23; 12; 8; 5; 2g; T = 33
Optimal Solution to Sample Instance 1: 23 + 8 + 2 = 33
Sample Instance 2: V = f23; 12; 8; 5; 2g; 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 = 12 15 24 25 2 3 5 8 9 11
Solution to Sample instance 1: 4
Sample Instance 2: X = 95 1 4 5 9 13 43 48 59 71
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 = 7 9 4 5 2 6 3 8 0 1
Optimal Solution to Sample Instance 1: 4 (4,5,6,8)
Sample Instance 2: X = 2 1 3 0 5 4 7 6 8 9
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 = 1 5 10 25 50 100 T = 177
Optimal Solution to Sample Instance 1: 7 (1,1,5,10,10,50,100)
Sample Instance 2: V = 1 7 8 12 20 47 T = 26
Optimal Solution to Sample Instance 2: 3 (7,7,12)
Problem 1. (10 points) State the de nition 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 nds the optimal solution to every instance, explain why it does.
If this algorithm nds 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 = f1; 5; 10; 25; 50; 100g.
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 ber 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.
H
D
J
F
B
I
E
A
G
C
10
4
14
5
16 11
19
3
5
8
15
2
13
21
7
12
6
9
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, de ne 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, de ne
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
ow that maximizes the water sent from S
to T) is given by the rst number on each edge. For both:
If the proposed solution is incorrect explain how/why it is incorrect and x it.
If it is correct then give a convincing argument for why it is a maximum
ow.
T
E
B
C
D
A
S
19/20
10/10
8/8
11/15
0/13
10/20
5/5
6/6
13/15
16/28
T
E
B
C
D
A
S
10/20
7/7
15/19
9/9
6/10
12/15
6/6 3/3
