Design and Analysis of Algorithms

CS 302 Spring 2019

Assigned: 14th March 2019 Due: 2nd April 2019

Each problem has 10 marks.

Greedy Algorithms
Q1) Consider the problem of making change from n cents using the fewest coins when the available
coins are quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent). Does the
greedy strategy of outputting the largest coin that does not exceed the amount of change that must
still be returned yield an optimal solution? Prove your answer is correct

Solution:
Yes, this strategy does yield an optimal solution. It is easily seen that this greedy algorithm can be
implemented in O(n) time.

Greedy Choice Property: We show that there exists an optimal solution for making n cents that
begins with the largest coin whose value is ≤ n cents. Let S be the set of coins given as change by
some optimal solution to the problem of making change for n cents. Suppose that the largest
denomination among the coins in S is k ∈ {Q, D, N, P}. Let i be the first coin chosen by the greedy
algorithm. If k = i then the solution begins with a greedy choice. If k ≠ i then we must show that
there is another optimal solution S’ that begins with coin i. Observe that since the greedy algorithm
picks the largest denomination that can be used, it follows that k < i. Thus i ≠ P. We now consider
each of the remaining cases.

Case 1: i = N. Thus the solution S must have value of 5 cents or more. Since the largest coin in S
must be less than a nickel, S uses only pennies, and hence must have at least 5 pennies. Create S’
from S by replacing 5 pennies by a nickel. |S’| < |S| contradicting the optimality of S.

Case 2: i = D. Thus the solution S must have value of 10 cents or more. Since the largest coin in S
must be less than a dime, S uses only pennies and nickels. The only way to create 10 cents or more
with pennies and nickels must use either 2 nickels, 1 nickel and 5 pennies, or 10 pennies. In all
three cases we can create S’ from S by replacing this subset of coins that equals 10 cents by a dime.
Again, |S’| < |S| contradicting the optimality of S.

Case 3: i = Q. First suppose, that there is some combination of coins in S that sum to 25 cents.
Then let S’ = S – {coins that sum to 25}∪ {Q} and observe |S’| < |S|. Next we consider the case
when no subset of coins in S sums to 25. This can only occur if there are at least 3 dimes in S since
that is required to obtain 30 cents or more without using a nickel or at least 5 pennies (in which
case some subset of coins would add to 25 cents). So in this case let S’ = S – {D + D + D}∪ {Q +
N}. Again |S’| < |S| contradicting the optimality of S. Hence in all three cases we proved not only
that there exist some optimal solution that picks the same first coin as the greedy algorithm, but in
fact, every optimal solution must pick this largest coin.

Optimal Substructure Property: Let P be the original problem of making n. Suppose the greedy
solution starts with k cent coin. Then we have the subproblem P’ of making change for n - k cents.
Let S be an optimal solution to P and let S’ be an optimal solution to P’. Then clearly cost(S) =
cost(S’) + 1, and thus the optimal substructure property clearly follows.

Q2) You are given a sequence of n songs where the ith song is li minutes long. You want to place
all of the songs on an ordered series of CDs. (e.g. CD 1, CD 2, CD 3, ….., CD k) where each CD
can hold m minutes. Furthermore,
1. The songs must be recorded in the given order, song 1, song 2, ... song n
2. All songs must be included
3. No song maybe split across CDs.
Your goal is to determine how to place them on the CDs as to minimize the number of CDs needed.
Give the most efficient algorithm you can to find an optimal solution for this problem, prove your
algorithms is correct and analyze the time complexity.

Solution:
Here is the algorithm. Put as many songs (from song 1 to song g) on the _rst CD as possible without
exceeding the m minute limit. Then recursively repeat this procedure for the remaining CDs. Since
this just requires keeping a running sum in which each of the n song lengths are included once,
clearly the above is an O(n) algorithm. We now prove it is correct.

Greedy Choice Property:

Let S be an optimal solution in which the first CD holds songs 1 to k. The greedy algorithm puts
songs 1 to g on the first CD. We now prove there is an optimal solution which puts the first g songs
on the first CD. If k = g then S is such a solution. Now suppose that k ≠ g. Since the greedy
algorithm puts as many songs on the first CD as possible, it follows that k < g. We construct a
solution S’ by modifying S to move all songs from k + 1 to g onto the first CD. We now argue that
S’ is a legal solution which is optimal. First note that the number of CDs used by S’ is at most the
number of CDs used by S. All that remains is to argue that S’ is legal (i.e. no CD holds more than
m minutes of songs). By definition of the greedy choice the first CD can hold songs 1 to g. Since
S is a legal solution all of the CDs in it hold at most m minutes. For all but CD 1 the number of
songs is only reduced and hence must still hold at most m minutes. Hence S’ is legal.

Optimal Substructure Property:

Let P be the original problem with an optimal solution S. Then after putting songs 1 to g on CD 1,
let P’ be the subproblem of songs (g +1) to n. Let S’ be an optimal solution to P’. Since, cost(S) =
cost(S’)+1, clearly an optimal solution to P includes within it an optimal solution to P’.
Q3) The input consists of n skiers with heights p1, ..., pn, and n skies with heights s1, ..., sn. The
problem is to assign each skier a ski to minimize the AVERAGE DIFFERENCE between the
height of a skier and his/her assigned ski. That is, if the skier i is given the ski ai, then you want to
minimize:
𝑛
|𝑝𝑖 − 𝑠𝑎𝑖 |
∑
𝑛
𝑖=1

(a) Consider the following greedy algorithm. Find the skier and ski whose height difference is
minimized. Assign this skier this ski. Repeat the process until every skier has a ski. Prove of
disprove that this algorithm is correct.
(b) Consider another greedy algorithm. Give the shortest skier the shortest ski, give the second
shortest skier the second shortest ski, give the third shortest skier the third shortest ski, etc. Prove
of disprove that this algorithm is correct.
HINT: One of the above greedy algorithms is correct and one is incorrect for the other.

Solution:
(a)This algorithm is INCORRECT for the problem of minimizing the average difference between
the heights of skiers and their skis. Consider an instance with the following values:
p1 = 5; p2 = 10; and s1 = 9; s2 = 14. The algorithm would pair p1 with s2 and p2 with s1 for a
total cost of 1=2(1 + 9) = 5. Pairing p1 with s1 and p2 with s2 yields a total cost of 1=2(4 + 4) =
4.

(b) This algorithm is CORRECT. The proof is by contradiction. Assume the people and skis are
numbered in increasing order by height. If the greedy algorithm is not optimal, then there is some
input p1…., pn; s1, …., sn for which it does not produce an optimal solution. Let the optimal
solution be T = {(p1, sj(1)),…., (pn, sj(n))}, and let the output of the greedy algorithm be G = {( p1,
s1),…, (pn , sn)}. Beginning with p1, compare T and G. Let pi be the first person who is assigned
different skis in G than in T . Let sj be the pair of skis assigned to pi in T Create solution T’ by
switching the ski assignments of pi and pj . By the definition of the greedy algorithm, si ≤ sj : The
total cost of T’ is given by

Cost (T’) = Cost (T) – 1/n (|pi – sj | + |pj – si | - |pi – si | - |pj – sj | )

There are six cases to be considered. For each case, one needs to show that

(|pi – sj | + |pj – si | - |pi – si | - |pj – sj | ) ≥ 0

Case 1: pi <= pj <= si <= sj

(|pi – sj | + |pj – si | - |pi – si | - |pj – sj | ) = (sj – pi ) + (si – pj ) - (si – pi ) - (sj – pj ) = 0

Case 2: pi <= si <= pj <= sj

Case 3: pi <= si <= sj <= pj

Case 4: si <= sj <= pj <= pj

Case 5: si <= pi <= sj <= pj

Case 6: si <= pi <= pj <= sj

Dynamic Programming Questions

Q4) You are traveling by a canoe down a river and there are n trading posts along the way.
Before starting your journey, you are given for each 1 ≤ 𝑖 < 𝑗 ≤ 𝑛 the fee fi,j for renting a
canoe from post i to post j. These fees are arbitrary. For example it is possible that f1,3 = 10 and
f1,4 = 5. You begin at trading post 1 and must end at trading post n (using rented canoes). Your
goal is to minimize the rental cost. Give the most efficient algorithm you can for this problem.
Be sure to prove that your algorithm yields an optimal solution and analyze the time complexity.

Solution:

Let m[i] be the rental cost for the best solution to go from post i to post n for 1 ≤ 𝑖 ≤ n. The
final answer is m[1]. We can recursively define m[i] as follows:

0 𝑖𝑓 𝑖 = 𝑛
𝑚[𝑖] = {
𝑚𝑖𝑛𝑖<𝑗 ≤𝑛 ( 𝑚 [𝑗] + 𝑓𝑖,𝑗 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

We now prove this is correct. The canoe must be rented starting at post i and then finally be
returned next at a station i+1 ……. n. For a canoe returned at post i, we try all possibilities with
j being the station where the canoe is next returned. Furthermore, since fi,j is independent from
how the subproblem of going from j to n is solved, we have the optimal substructure property.

For the time complexity there are n subproblems to be solved for each post, each of which
takes O(n) time. These subproblems can be computed in the order m[n], m[n-1], …..,
m[1].Thus, the overall time complexity is O(n2).

Q5) For bit strings X = x1....... xm, Y = y1 ...... yn and Z = z1 ...... zm+n, we say that Z is an
interleaving of X and Y if it can be obtained by interleaving the bits in X and Y in a way that
maintains the left-to-right order of the bits in X and Y . For example if X = 101 and Y = 01 then
x1x2y1x3y2 = 10011 is an interleaving of X and Y , whereas 11010 is not. Give the most efficient
algorithm you can to determine if Z is an interleaving of X and Y . Prove your algorithm is
correct and analyze its time complexity as a function m = |X| and n = |Y|.
Solution:
The general form of the subproblem we solve will be: determine if z1 ,……, zi+j is an interleaving
of x1 ,……, xi and y1 ,……, yj for 0 ≤ i ≤ m and 0 ≤ j ≤ n. Let c[i, j] be true if and only if z1 ,……,
zi+j is an interleaving of x1 ,……, xi and y1 ,……, yj. We use the convention that if i = 0 then xi =
𝜆 (the empty string) and if j = 0 then yj = 𝜆. The subproblem c[i, j] can be recursively defined as
shown (where c[m, n] gives the answer to the original problem):

𝑡𝑟𝑢𝑒 𝑖𝑓 𝑖 = 𝑗 = 0
𝑓𝑙𝑎𝑠𝑒 𝑖𝑓 𝑥𝑖 ≠ 𝑧𝑖+𝑗 𝑎𝑛𝑑 𝑦 ≠ 𝑧𝑖+𝑗
𝑐[𝑖, 𝑗] = 𝑐[𝑖 − 1, 𝑗] 𝑖𝑓 𝑥𝑖 = 𝑧𝑖+𝑗 𝑎𝑛𝑑 𝑦 ≠ 𝑧𝑖+𝑗
𝑐[𝑖, 𝑗 − 1] 𝑖𝑓 𝑥𝑖 ≠ 𝑧𝑖+𝑗 𝑎𝑛𝑑 𝑦 = 𝑧𝑖+𝑗
{ 𝑐[𝑖, 𝑗 − 1] ∨ 𝑐[𝑖 − 1, 𝑗] 𝑖𝑓 𝑥𝑖 = 𝑧𝑖+𝑗 𝑎𝑛𝑑 𝑦 = 𝑧𝑖+𝑗

We now argue this recursive definition is correct. First the case where i = j = 0 is when both X and
Y are empty and then by definition Z (which is also empty) is a valid interleaving of X and Y . If
xi = zi+j and yj ≠ zi+j then there could only be a valid interleaving in which xi appears last in the
interleaving, and hence c[i, j] is true exactly when z1 ,….., zi+j-1 is a valid interleaving of x1 ,……,
xi-1 and y1 ,…, yj which is given by c[i – 1, j]. Similarly, when xi ≠ zi+j and yj = zi+j then c[i, j] =
c[i, j-1]. Finally, consider when xi = yj = zi+j. In this case the interleaving (if it exists) must either
end with xi (in which case c[i – 1, j] is true) or must end with yi (in which case c[i, j - 1] is true).
Thus returning c[i – 1, j] ⋁ 𝑐 [𝑖, 𝑗 − 1] gives the correct answer. Finally, since in all cases the value
of c[i, j] comes directly from the answer to one of the subproblems, we have the optimal
substructure property. The time complexity is clearly O(nm) since there are n *m subproblems
each of which is solved in constant time. Finally, the c[i, j] matrix can be computed in row major
order.

Q6) You are given n integers in the range [1, m] and a target T. Find a subset of the n integers
whose sum is as close to T as possible without exceeding it. Give an efficient dynamic
programming algorithm for this problem. Be sure to prove that your algorithm yields an optimal
solution and analyze the time complexity.

Solution:
This problem reduces to 0-1 knapsack without repetition. Assume the integers you are given are
a1, …… an. The capacity of the knapsack is T and there are n items; item i has value ai and weight
ai. The running time is O(nT), and the dynamic programming algorithm is the same as the
algorithm for 0-1 knapsack without repetition.