Problem Set 12

Data Structures and Algorithms, Fall 2021

Due: December 24, in class.

Problem 1
(a) Run the Bellman-Ford algorithm on the following directed graph, using vertex z as the source. In
each pass, Update edges in the order (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y),
652 Chapter 24 Single-Source Shortest Paths
and show the dist and parent values after each pass.

t 5 x t 5 x t
–2 6 –2 ∞ 6
6 6 6
–3 –3
s 8 s 0 8 s 0 8
–4 9 –4 7
2 2
7 7 7
7 ∞ 7
11 9
y z y z y
(a) (b) (
(b) Run the DAGSSSP algorithm
656 on the following directed
Chapter 24 graph, using
Single-Source Paths r as the source. You need
vertex
Shortest
to show the dist and parent values after each iteration
t of5 the outer
x loop. t 5 x
2 –2 4 2 –2 4
6 6 1 6 6 1
r s t x –3 y z r s –3 t x y
5 s 0 2 87 –1 –2 s 0 8 5 2 7 –1 –2
–4 7 ∞ 0 –4 7 ∞ ∞ ∞
2 2
8 7 4 2 7 3 4 2
7 2 7 –2
9 9 (b)
y z y z
(d) (e)
6 1 6 1
r s xt y z r s t x y
Problem 2 5 2 7 –1 –2 5 2 7 –1 –2
∞ 0 6 24.4 ∞The execution
Figure2 ∞ ∞
of the Bellman-Ford 0 algorithm.2 The 6source is 6vertex
(a) Run the Floyd-Warshall algorithm on ues appear
3 the following withindirected
4weighted, 2 the vertices,
graph.andShow
shadedthe edges
n3×indicate
n matrix predecessor
4 values: 2 if
shaded, then :  D u. In this particular example, each pass relaxes the edg
dist[·, ·, r] after each outermost loop. (That, for each
(c) r ∈ [1, n], show the dist matrix.) (d)
.t; x/; .t; y/; .t; ´/; .x; t/; .y; x/; .y; ´/; .´; x/; .´; s/; .s; t/; .s; y/. (a) The situation
(b) Use Johnson’s algorithm to find the shortest paths first passbetween
over the all pairs(b)–(e)
edges. of vertices in the
The situation following
after each successive pass over the
6 and allvalues
graph. Show the final shortest distance value between pairs1inofpart
vertices, h value
the final
(e) are the values.for The 6
eachBellman-Ford
vertex, algorithm1return
r 25.1s Shortest
t paths and
x
example. matrixymultiplication
z r s t x 691
y
and the updated edge weight ŵ(u, v) 2 edge7(u, v).–1
5 for each –2 5 2 7 –1 –2
∞ 0 2 6 5 4 ∞ 0 2 6 5
1 4 2 24.23 2
13 2Lemma 3 4 2
(e) G D .V; E/
Let be a weighted, directed graph with (f) source s and
–3 tion
7 w W 12E !–8R, and assume that G contains no negative-weight cy
2 6–1 reachable
5 from
1 s. Then, after the jV j  1 iterations of the for loop
r s t of Bx ELLMAN z , we have :d D ı.s; / for all vertices  that a
y -F ORD
5 4 23 57 –1 6 –2
∞ 0 2 from 6 s. 5 3
3 4 2
Proof We prove the lemma by appealing to the path-relaxation pro
(g)
Figure 25.2 A weighted, directed graph for use in Exercises 25.1-1, 25.2-1, and 25.3-1.
sider any vertex  that is reachable from s, and let p D h0 ; 1 ; : : :
0 D s and k D , be any shortest path from s to . Because short
FASTER -A LL -P
Figure 24.5 AIRS
simple, -Sexecution
The pHORTEST of-P
has at most ATHS
the jV .W1 /edges,
j
algorithm and so
for shortest k
paths in jV j  1. Each
a directed acyclicofgraph.
the
1 n D W:rows
vertices 1
tions of the for loop of lines 2–4 relaxes all jEj edges. Among the edga
are topologically sorted from left to right. The source vertex is s. The d values
within
.1/
2 L D W the the vertices, and shaded for
ith iteration, edgesi Dindicate : : :; k,
1; 2;the values.
is .(a) The situation before the first ite
i 1 ; i /. By the path-relaxat
of the for loop of lines 3–5. (b)–(g) The situation after each iteration of the for loop of lines
3 mD 1 therefore, :d D k :d D ı.s; k / D ı.s; /.
The newly blackened vertex in each iteration was used as u in that iteration. The values sho
4 while m < n  1
Problem 3
The PERT chart formulation discussed in class is somewhat unnatural. In a more natural structure,
vertices would represent jobs and edges would represent sequencing constraints; that is, edge (u, v)
would indicate that job u must be performed before job v. We would then assign weights to vertices
instead of edges. In this problem, you are given a DAG graph G = (V, E) with a weight function
w : V → R+ . Assume G has a unique source s and a unique sink t. For each of the following tasks,
design an O(|V | + |E|) time algorithm:
(a) Compute the total number of paths in G.
(b) For each vertex v ∈ V , the earliest starting time of the job represented by v, assuming the job
represented by s starts at time 0.
(c) For each vertex v ∈ V , the latest starting time of the job represented by v, without affecting the
project’s total duration.

Problem 4
Suppose you are given a directed graph G in which every edge has negative weight, and a source vertex
s. Design an algorithm that computes the shortest-path distances from s to every other vertex in G.
Specifically, for every vertex t:
• If t is not reachable from s, your algorithm should report dist(s, t) = ∞.
• If G has a cycle that is reachable from s, and t is reachable from that cycle, then the shortest-path
distance from s to t is not well-defined, because there are paths from s to t of arbitrarily large
negative length. In this case, your algorithm should report dist(s, t) = −∞.
• If neither of the two previous conditions applies, your algorithm should report the correct shortest-
path distance from s to t.
Try to devise the fastest algorithm you can come up with. You need to describe your algorithm, briefly
argue its correctness, and analyze its running time.

Problem 5
You are the owner of a steamship that can ply between a group of port cities V . You make money at
each port: a visit to city i earns you a profit of pi dollars. Meanwhile, the transportation cost from port
i to port j is cij > 0. You want to find a cyclic route in which the ratio of profit to cost is maximized.
To this end, consider a directed graph G = (V, E) whose nodes are ports, and which has edges between
each pair of ports. For any cycle C in this graph, the profit-to-cost ratio is
P
(i,j)∈C pj
r(C) = P
(i,j)∈C cij

Let r∗ be the maximum ratio achievable by a simple cycle. One way to determine r∗ is by binary search:
by first guessing some ratio r, and then testing whether it is too large or too small. Consider any positive
r > 0. Give each edge (i, j) a weight of wij = r · cij − pj .
(a) Prove that if there is a cycle of negative weight, then r < r∗ .
(b) Prove that if all cycles in the graph have strictly positive weight, then r > r∗ .
(c) Design an algorithm that takes as input a desired accuracy ϵ > 0 and returns a simple cycle C for
which r(C) ≥ r∗ − ϵ. Remember to briefly argue the correctness of your algorithm and analyze its
running time in terms of |V |, ϵ, and R = max(i,j)∈E (pj /cij ).

2
Problem 6
You’ve just accepted a job from Elon Musk, delivering burritos from San Francisco to New York City.
You get to drive a Burrito-Delivery Vehicle through Elon’s new Transcontinental Underground Burrito-
Delivery Tube, which runs in a direct line between these two cities. Your Burrito-Delivery Vehicle runs
on single-use batteries, which must be replaced after at most 100 miles. The actual fuel is virtually free,
but the batteries are expensive and fragile, and therefore must be installed only by official members of
the Transcontinental Underground Burrito-Delivery Vehicle Battery-Replacement Technicians’ Union.
Thus, even if you replace your battery early, you must still pay full price for each new battery to be
installed. Moreover, your Vehicle is too small to carry more than one battery at a time.
There are several fueling stations along the Tube; each station charges a different price for installing
a new battery. Before you start your trip, you carefully print the Wikipedia page listing the locations
and prices of every fueling station along the Tube. Given this information, how do you decide the best
places to stop for fuel?
More formally, suppose you are given two arrays D[1 · n] and C[1 · · · n], where D[i] is the distance
from the start of the Tube to the i-th station, and C[i] is the cost to replace your battery at the i-th station.
Assume that your trip starts and ends at fueling stations (so D[1] = 0 and D[n] is the total length of
your trip), and that your car starts with an empty battery (so you must install a new battery at station 1).
(a) Describe a greedy algorithm to find the minimum number of refueling stops needed to complete your
trip. You do not need to prove that your algorithm is correct, but you need to analyze its running time.
(b) But what you really want to minimize is the total cost of travel. Show that your greedy algorithm in
part (a) does not produce an optimal solution when extended to this setting.
(c) Describe an algorithm to compute the locations of the fuel stations you should stop at to minimize
the total cost of travel. You do not need to prove that your algorithm is correct, but you need to analyze
its running time.

Problem 7
Assume that you have a subroutine IsWord that takes an array of characters as input and returns True
iff that string is a “word”. Design an algorithm that, given an array A[1 · · · n] of characters, compute the
number of partitions of A into words. You need to give the pseudocode of your algorithm, and analyze
the runtime of your algorithm by bounding the number of calls to IsWord. For example, given the
string ARTISTOIL, your algorithm should return 2, for the partitions ARTIST·OIL and ART·IS·TOIL.