CS 560, HOMEWORK 5 (DUE: SUNDAY NOV 24, 11:59 PM)
INSTRUCTOR: HOA VU
Each question is worth 27.5 points.
When you are asked to design an algorithm, do the following: a) describe the algorithm,
b) explain (or more rigorously prove) why it is correct, and c) provide the running time.
Unless specified otherwise, the problems are from the textbook by Jeff Erickson.
(1) Question 1: Recall the algorithm Dijkstra(G, s) we went over in class:
• For all u ∈ V \ {s}, set dist(u) ← ∞.
• dist(s) ← 0.
• R = {}.
• While R 6= V :
– Pick u /∈ R with smallest dist(u), then R ← R ∪ {u}.
– For all vertices uv ∈ E, if dist(v) > dist(u) + `(uv), then update
dist(v) ← dist(u) + `(uv).
Consider Dijkstra’s algorithm for finding single-source shortest paths starting
from vertex s to all other nodes.
What are the different (distinct) values of dist(a) and dist(d) during the execution
of Dijkstra’s algorithm (list their values over time) in the above graph.
(2) Question 2: Problem 19a page 253. Your algorithm should run in O(|V | log |V | +
|E| log |E|) time. Use the following hints.
A) First sort each adjacency list A[i] (for i = 1, 2, . . . , n) that contains all (outgoing)
neighbors of i based on the neighbors’ weights. Explain why this takes
12 INSTRUCTOR: HOA VUO(E log E) time. Use the fact thatXni=1
(# of edges i → j) = |E| .
In particular, you simply sort each adjacency list. But you need to argue why the
running time for this step is O(E log E).
B) Sort the nodes by their weights.
C) Use Depth-First-Search to find the longest increasing-weight sequence (hint:
the order in which you explore unvisited nodes matters).
(3) Question 3: Problem 3 page 245 (Hint: try applying an existing algorithm). The
running time should be O(|V | log |V | + |E|).
(4) Question 4: You need to build source code files. If source code file A.cpp refers to
file B.cpp (i.e., “#include B.cpp”) then we need to build file B.cpp first. Suppose
we want to build a target file T.cpp without building unncessary files (for example,
if there are 3 files A, B, T and T includes A, then we only need to build A then T
and not build B). Design an algorithm (as efficient as possible) to list out the files
and the ordering to build them.