Description
Problem 1 (20pts)
There are alternatives to CLRS3’s greedy choice of the earliest finishing time
the activity selection problem in section 16.1. For each of the following alternatives, prove or disprove that it constructs an optimal schedule (assume
ties are broken arbitrarily):
1. Choose the job that starts last.
2. Choose the job that conflicts with the fewest other jobs.
3. Choose the job of longest duration.
1
Problem 2 (20pts)
A country has n different types of coins with denominations 1 = c1 < c2 <
· · · < cn. You want to give change using the fewest number of coins. The
greedy algorithm for giving change for an amount d subtracts the largest
denomination coin from d and repeats recursively on the amount still needed.
1. We have c1 = 1, c2 = 5, c3 = 10, c4 = 25, c5 = 50, and c6 = 100. Does
the greedy algorithm always give the change with the fewest coins?
Either prove that it does, or provide a counterexample.
2. Suppose the denominations are consecutive powers of an integer b ≥ 2;
that is c1 = 1, c2 = b, c3 = b2, and so on. Does the greedy algorithm
always give the change with the fewest coins? Either prove that it
does, or provide a counterexample.
Problem 3 (20pts)
Consider the following directed, weighted graph:
1. Show your steps of using Dijkstra’s algorithm for finding the shortest
path in the table below. Cross out old values and write in new ones,
from left to right within each cell, as the algorithm proceeds. Also list
the vertices in the order which you marked them known.
2. Dijkstra’s algorithm found the wrong path to some of the vertices. For
just the vertices where the wrong path was computed, indicate both
the path that was computed and the correct path.
2
Vertex Known Distance Path
A
B
C
D
E
F
G
Problem 4 (20pts)
Consider a flow network with non-negative edge capacities. Show that there
always exists a maximum flow f in which either f(u, v) = 0 or f(v, u) = 0
for any pair of vertices.
3