Problem Set 11
Data Structures and Algorithms, Fall 2021
Due: December 16, in class.
Problem 1
(a) Run Dijkstra’s algorithm on the following directed graph, first using vertex s as the source and then
648 dist and parent
using vertex z as the source. Show the Chapter 24 Single-Source
values Shortest
and the vertices in Paths
“the known region R”
after each iteration of the while loop.
t x t x t
6 6
3 9 3
4 3 3
4 4
s 2 1 2 1 s 0 2 1 2 7 s 0 2 1
3 3
5 5 5
5 11 5
6 6
y z y z y
(a) (b) (c)
(b) Give a simple example of a directed graph with negative-weight edges for which Dijkstra’s algorithm
produces incorrect answers.
Figure 24.2a vertex
(c) Give a simple example of an undirected graph containing (a) A weighted, directed
s such that graph with shortest-path
the minimum spanning weights from sou
shaded edges form a shortest-paths tree rooted at the source s. (c) Another shortest-
tree and the shortest-path tree rooted at s are different.
the same root.
Problem 2 Shortest paths are not necessarily unique, and neither are shortest-pat
example, Figure 24.2 shows a weighted, directed graph and two shortes
We are given a directed graph G = (V, E) on which with the
eachsame
edgeroot.
(u, v) ∈ E has an associated value
r(u, v), which is a real number in the range 0 ≤ r(u, v) ≤ 1 that represents the reliability of a commu-
Relaxation
nication channel from vertex u to vertex v. We interpret r(u, v) as the probability that the channel from
u to v will not fail, and we assume that these probabilities are independent.
The algorithms Devise an
in this chapter useefficient algorithm
the technique of relaxation. For
2 V ,swe
to find the most reliable path between two given vertices t. You need
andmaintain to give :d,
an attribute the pseudocode
which is anofupper bound on th
your algorithm and analyze its running time. a shortest path from source s to . We call :d a shortest-path es
initialize the shortest-path estimates and predecessors by the following
Problem 3 procedure:
I NITIALIZE -S INGLE -S OURCE .G; s/
For any edge e in any graph G = (V, E), let G \ e denote the graph obtained by deleting e from E.
Suppose we are given a graph G and two vertices 1s ∈for V each ∈ V .The
and tvertex 2 G:V
replacement paths problem
2 :d D 1
asks us to compute the shortest-path distance from s to t in G \ e, for every edge e of E. The output is
3 : D NIL
an array of |E| distances, one for each edge of G.
4 s:d D 0
(a) Suppose G is a directed graph, and there is a unique shortest path from vertex s to vertex t that
After initialization,
passes through every vertex of G. Devise an algorithm to solve thiswe : D
have case
special of NIL for all 2 V , s:d D 0, and
the replacement
paths problem in O((|V | + |E|) log |V |) time. 2 V fsg.
The process of relaxing an edge .u; / consists of testing whether
(b) Devise an algorithm to solve the replacement paths problem for arbitrary undirected graphs in
prove the shortest path to found so far by going through u and,
O((|V | + |E|) log |V |) time.
ing :d and :. A relaxation step1 may decrease the value of the s
In both subproblems, you may assume that all edge weights are non-negative. You need to briefly argue
the correctness of your algorithms.
1 It may seem strange that the term “relaxation” is used for an operation that tightens a
The
1 use of the term is historical. The outcome of a relaxation step can be viewed
of the constraint : d u: d C w.u; /, which, by the triangle inequality (Lemma 2
satisfied if u: d D ı.s; u/ and : d D ı.s; /. That is, if : d u: d C w.u; /, there i
to satisfy this constraint, so the constraint is “relaxed.”
Problem 4
The greedy algorithm we described in class for the activity selection problem is not the only greedy
strategy we could have tried. For each of the following alternative greedy strategies, either claim that the
resulting algorithm always constructs an optimal solution, or describe a small input example for which
the algorithm does not produce an optimal solution (that is, either answer “correct strategy” without
proof, or answer “incorrect strategy” and give a counterexample). Assume that all algorithms break ties
arbitrarily (that is, in a manner that is completely out of your control).
(a) Choose the activity x that ends last, discard all activities that conflict with x, and recurse.
(b) Choose the activity x that starts first, discard all activities that conflict with x, and recurse.
(c) Choose the activity x that starts last, discard all activities that conflict with x, and recurse.
(d) Choose the activity x with shortest duration, discard all activities that conflict with x, and recurse.
(e) Choose an activity x that conflicts with the fewest other activities, discard all activities that conflict
with x, and recurse.
(f) If no activities conflict, choose them all. Otherwise, discard the activity with longest duration and
recurse.
4. GREEDY ALGORITHMS
(g) If no activities conflict, choose them all. Otherwise, discard an activity that conflicts with the most
other activities and recurse.
(h) If any activity x completely contains another activity, discard x and recurse. Otherwise, choose the
y that
activity(c) ends last, and
Describe discard all activities
analyze thaty,always
that conflict with
an algorithm and recurse.
computes an optimal
schedule. [Hint: Your algorithm will not be greedy.]
Problem 5
3. Let X be a set of n intervals on the real line. We say that a subset of intervals
Let X be a set of n intervals on the real line. We say that a subset of intervals Y ⊆ X covers X if
Y ⊆ X covers X if the union of all intervals in Y is equal to the union of all
the union of all intervals in Y is equal to the union of all intervals in X. The size of a cover is just the
numberintervals
of intervalsinin Xthe
. The See of
cover.size a cover
following is just
figure theexample.
for an number of intervals.
Devise an efficient algorithm
Describe to compute
and analyze the smallest
an efficient cover of X.toAssume
algorithm that your
compute the input consists
smallest
coverL[1
of two arrays of ·X· ·.n]Assume
and R[1 · ·that
· n], representing
your inputtheconsists
left and right endpoints
of two arraysof the
L[1intervals in X.
.. n] and
(For simplicity, you may assume all 2n endpoints are distinct.) You need to give the pseudocode of your
R[1 .. n], representing the left and right endpoints of the intervals in X . If
algorithm and analyze its runtime. You also need to prove that it is correct.
you use a greedy algorithm, you must prove that it is correct.
A set of intervals, with a cover (shaded) of size 7.
4. Let X be a set of n intervals on the real line. We say that a set P of points
Problem
stabs6X if every interval in X contains at least one point in P. Describe and
Supposeanalyze
you are aan efficient
simple algorithm
shopkeeper living intoa compute
country withthe smallest
n different setofofcoins,
types points
withthat
values
1 = c[1]stabs X .<Assume
< c[2] that
· · · < c[n]. (Inyour input
the U.S., for consists
example, of
n= two arrays
6 and L[1 ..are
the values n]1,and R[1
5, 10, n],and
25,..50
100 cents.) Your belovedthe
representing andleft
benevolent dictator,
and right El Generalissimo,
endpoints has decreedin
of the intervals X .whenever
that As usual,you Ifgive
a customer
youchange,
use a you
greedymust algorithm,
use the smallest
you possible
must number of coins,
prove that it issocorrect.
as not to wear out the image
of El Generalissimo lovingly engraved on each coin by servants of the Royal Treasury.
(a) In the United States, there
1 is a simple greedy algorithm that always
2 3 results
4 in the smallest number
1 2 3
of coins: subtract the largest coin and recursively give change for the remainder. El Generalissimo does
1 3 4
1 2 3
1 2 4
2
A set of intervals stabbed by four points (shown here as vertical segments)
not approve of American capitalist greed. Show that there is a set of coin values for which the greedy
algorithm does not always give the smallest possible of coins.
(b) Suppose El Generalissimo decides to impose a currency system where the coin denominations are
consecutive powers b0 , b1 , b2 , · · · , bk of some integer b ≥ 2. Prove that despite El Generalissimo’s dis-
approval, the greedy algorithm described in part (a) does make optimal change in this currency system.
