Introduction to Algorithms Prelim 1

CS 4820, Fall 2019 Solutions

1. (20 points) Short answer. Each of these questions asks for a true/false answer or a short answer to a
question. Follow the instructions at the parts for what is required in this section.

a. (4 points) True or false? Consider an instance of the stable matching problem with n men and n
women, and n ≥ 2. Consider a man m and a woman w who is ranked first on the preference list of m.
Then, in every stable matching S for this instance, the woman w is matched to man m or someone she
ranks higher than m.
If false, give a counter-example. If true, give a short (one phrase or one sentence) explanation of why.

Solution: True: if w were to matched to a lower ranked man, (m, w) would form an instability.

Common mistake: Some students argued that w will be matched to m or a man she prefers by the
Gale-Shalpey algorithm, and not in all stable matchings.

b. (4 points) True or false? Consider an instance of the stable matching problem with n men and n
women, and n ≥ 2. Consider a man m and a woman w so that
• m is ranked last on w’s preference list
• w is ranked last on m’s preference list
Then, there is no stable matching S for this instance, with (m, w) as a pair in S.
If false, give a counter-example. If true, give a short (one phrase or one sentence) explanation of why.

Solution: False: a simplest example: two men two women, and they all order the other sex by
preferring person 1 to person 2. Then w2 and m2 rank last on each-other’s list yet they get matched in
the unique stable matching.

c. (4 points) Find the min-cost spanning tree (MST) on the graph below. Circle the weights or shade the
edges that belong to the MST, and list the costs of the edges belonging to the MST in the order
those edges are added using Prim’s algorithm starting from node R. (We give two copies in case
you make a mistake on one of them; please indicate which has your solution.)

2 2
A D A D

5 1 3 7 5 1 3 7

9 8 9 8
R B R B
E E

6 8 1 6 8 1
4 4
C F C F

Edge weights in order:

d. (4 points) True or false? Assume you are given an undirected graph G = (V, E) with n nodes and m
edges, and assume all edge-costs are all different. Suppose for a node v edge e = (v, w) is the cheapest
edge adjacent to v. In this case edge e is in the Minimum Cost Spanning Tree.
If false, give a counter-example. If true, give a short (one phrase or one sentence) explanation of why.

Solution: True. starting from root r = v this is the first edge Prim’s algorithm adds to the tree.
Alternately, the edge is the min-cost edge in the cut (v, V − {v}) and the min-cost edge in any cut is in
the MST.

e. (4 points) True or false? Assume you are given a directed graph G = (V, E) with n nodes and m
edges, a source and sink s, t ∈ V , and costs on the edges, and assume G has no negative cost cycles.
Suppose we have a direct edge e = (s, t), and edge e is the minimum cost edge in the whole network
(recall that costs of edges can be negative). In this case edge e = (s, t) itself is the min-cost path from
s to t.
If false, give a counter-example. If true, give a short (one phrase or one sentence) explanation of why.

Solution: False. Suppose the min-cost is -4, and there are two edges (s, v) of cost -2, and (v, t) of
cost -3.

2. (14 points) In problem set 2 you considered a shift scheduling problem with one person optimizing her
schedule. Here you consider a version of this problem from the hospital’s perspective. We have 3 nurses,
called A, B and C, and we are planning a sequence of n shifts, labeled as shifts i = 1, . . . , n. For each shift
i we need exactly one of the three nurses to work. If worker X works that shift, that has value r[X, i].
However, by law (and common sense) any one worker cannot work two consecutive periods, that is, needs
to take a break between any two shifts. The hospital would like the maximize the sum of the values of
the three nurses over the n shifts. To illustrate the problem, consider the following example. There are 5
shifts, and the values are
1 2 3 4 5
A 10 10 10 10 10
B 2 3 7 5 4
C 3 5 5 4 2
Then the optimal solution is to have A work on shifts 1, 3, and 5 and have C work on shift 2, and B work
on shift 4 for a total value of 40.
Give a polynomial-time algorithm to find the maximum possible sum of the three nurses values. You need
not actually return the list of shifts.
You must give the algorithm and analyze the running time, explain how your algorithm works (for example,
explain the meanings of all variables other than loop counters), but you do not need to provide the
proof of correctness. Pseudocode is acceptable so long as you explain in English the intended meaning
of your variables.
Dynamic programming Algorithm Let Opt[i, X] be the optimal solution for shifts 1, . . . , i with X
working on shift i, where X = A, B or C.
• base case is opt[0, X] = 0 for all X = A, B, C.
• recurrence for i ≥ 1 is Opt[i, X] = r[i, X] + maxY 6=X (Opt[i − 1, Y ].
• this can be computed in the order i = 2, . . . , n.
 • the optimal reward possible is maxX Opt[n, X].
• runtime is O(n).
Common mistakes
• Some students tried to use Opt[i] as the best solution for days 1, . . . , i, and to help with the re-
quirement output also the last nurse, so Opt[i] is a 2 dimensional answer, a value and a last nurse.
And then the update is Opt[i][1] = maxX6=Opt[i−1][2] r[i, X] + Opt[i − 1][1]. This algorithm is actually
greedy, when setting Opt[1] the algorithm commits to x which maximizes max r[1, X], which may
not be the right decision.
• Some students had theg recurrence Opt[i, X] = r[i, X] + max(maxY 6=X (Opt[i − 1, Y ], Opt[i − 2, X]).
This solution allows to have some uncovered days, which can be bad is the values are negative on
some day. The question did require that there is a nurse every day.
3. (16 points) You supervise a swim club and you need to hire life guards. The swim club will be open
for the time interval [s, f ]. There are n total life guards and each life guard i can work during the time
interval [si , fi ] ⊂ [s, f ]. Combined, the life guards’ intervals cover the entire time: ∪i [si , fi ] = [s, f ]. Note
that multiple intervals may start or end at the same time. You would like to hire as few life guards as
possible while ensuring that your chosen life guards cover the entire time interval [s, f ]. For example, if
the club is open 7 until 22, and intervals are [7, 12], [10, 14], [12, 16], [15, 19], [15, 22], then hiring guards 1,
3 and 5 minimizes the total number of guards needed to cover the entire time by using 3 total life guards.
Below, you are given two potential algorithms to solve the problem. For each proposed algorithm, either
prove that it returns an optimal solution and analyze its running time, OR give a example input on which
the algorithm fails to return an optimal solution.

Algorithm A:
Step 1: preprocessing: Sort intervals by start time. If a start time has multiple intervals
that start at that time, keep only the one that has the latest finish time. Initialize the result S
to be empty.
Step 2: add intervals to set S: Iterate through intervals in the above sorted order and add
an interval to S if it extends the time covered by the intervals already in S.
Return the set S.

Algorithm B:
Initialize t = s and initialize S = ∅.
While t < f
Among the remaining intervals that start either at time t or before time t, select the interval i
that has the latest end time fi . Add interval i to S, and update t = fi .
Return S

Algorithm A is wrong. Consider intervals [8, 13], [11 − 15], [12, 18]. The algorithm will take all 3, but 1
and 3rd is enough.
Algorithm B works.
Running Time It is easy to argue that the running time is O(n2 ) as it has n iteration, and each iteration
chooses among n items.
To implement this algorithm in O(n log n) time, we sort the intervals by their beginning time si , and
process them in this order. Once [s, t] is covered by some intervals for a current time t, we need to only
consider guards with si ≤ t, and want to select the guard in this set that has maximum fi . We can do
this by adding this set of guards to a priority queue with their finish time. Alternately can process the
intervals in while identifying the one with the maximum fi .
Proving optimality by ”greedy stays ahead” We can prove that the algorithm is optimal by a greedy
stays ahead argument. Consider an optimal solution O with intervals j1 , . . . , jk sorted by increasing order
of their finish time. And let i1 , i2 , . . . denote the intervals selected by our algorithm. We claim that fi` ≥ fj`
for all selections `. This will prove that our selection is optimal, as if the optimal sequence ends at the `th
interval, than f` = f , and then our claim implies that i` = f also, so our algorithm terminates.
We prove the claim by induction on `. For ` = 1 the claim of fi1 ≥ fj1 is true by the choice of the algorithm.
To prove the claim in general, recall that the part covered by the first ` intervals in our algorithm is [s, fi` ],
while the part covered by the first ` intervals of the optimum O is [s, fj` ] as we sorted the optimum also by
finish time. The next interval in the optimum must be a guard available just after fj` , so sj`+1 ≤ fj` . By
the induction hypothesis fi` ≥ fjk ` , so this interval j`+1 was one of the intervals considered by our greedy
algorithm, and we selected i`+1 so we must have fi`+1 ≥ fj`+1 .
Proving optimality by exchange Consider an optimal solution O with intervals j1 , . . . , jk where the
first some intervals are the same as the ones selected by our algorithm for as long as possible, say till
interval j` , and our algorithm selects i as the next interval, which is not in this optimum. The first `
intervals cover the time [s, fj` ]. The optimum must have an interval `0 that extends this to the time right
after fj` . We claim that replacing `0 with i in the solution creates another optimum solution O0 that agrees
with the algorithm one step longer. A contradiction that proves that our solution is optimal.
To see why the exchange works, recall that i was the interval with si ≤ fj` , and fi maximal, so by this
choice we must have f`0 ≤ fi , so adding i in place of `0 covers at least as much time.
Common mistakes
• Some students try to use ”greedy stays ahead” with a claim that at each time t the interval for [s, t]
is covered by no more life-guards. We don’t see a way to prove this by induction: just because this
is true for t it may not be true for t0 > t (or t + 1) because the last interval may be too short.
• Some people do not comparing to an optimal solution. For example argue that in our solution no
two lifeguards can be replaced with a single life guard. This is true, but does not imply that we
cannot replace 3 life guards with 2 (or k life guards with k − 1 of them).
• Some people claimed that Algorithm B is the same as the algorithm from the homework, or the
balloon problem from the review sheet, and hence correct. While the algorithm is similar to the
one we used for visit times, it is a different problem, we don’t see a viable reduction between these
problems. The proof is similar also, but does need a new proof, as it is not the same problem.