Name: Basic Algorithms (Section 5) HW10 (Due 4/24 23:59)
Net ID: Spring 2025 Instructor: Jiaxin Guan
Problem 1 (Topological Sort, 25 pts)
How many valid topological sorts does the directed graph below have? List all the valid
topological sorts in the following table. One of them has been listed as an example, where
node A is output first and D is output last.
1. A B C F E D
2.
B C
A D
F E
Discussion Partners: 1
Name: Basic Algorithms (Section 5) HW10 (Due 4/24 23:59)
Net ID: Spring 2025 Instructor: Jiaxin Guan
Problem 2 (Reachability, 35 pts)
Suppose you are given a directed graph G = (V, E) where each vertex, u ∈ V , is labeled
with a unique value L(u) from the set {1, . . . , |V |}. For each vertex u, let R(u) denote the
set of vertices reachable from u in G. Define max(u) to be the vertex vu∗ in R(u) with the
maximum label, i.e. L(vu∗ ) ≥ L(v) for all v ∈ R(u).
Give an O(|V | + |E|) time algorithm to compute max(u) for all vertices in u ∈ V . Briefly
justify correctness and runtime of your algorithm.
Discussion Partners: 2
Name: Basic Algorithms (Section 5) HW10 (Due 4/24 23:59)
Net ID: Spring 2025 Instructor: Jiaxin Guan
Problem 3 (Helping Botanical Garden, 40 pts)
Suppose the New York Botanical Gardens are trying to drum up interest for their tree and
shrub collections by offering tours through the arboretum, and you are tasked with reviewing
their proposed routes. There are a set V of trees they want some tour to stop at, and a set
E of routes from tree to tree their proposed tours would make. In order to make sure all the
trees are visited, they want the following property:
For all pairs u, v ∈ V such that u ̸= v, we must have a path from u to v or a path from v to
u (or both).
Notice how this property is different from strongly connectedness. They provide
you and your classmates with many proposed plans and a strict deadline for your feedback,
and so you want to develop an efficient algorithm to automate this task.
(a) Suppose G = (V, E) is a directed acyclic graph (DAG). Your classmates propose two
possible algorithms to determine whether or not the given graph G satisfies the de-
sired property. For each of the proposed algorithms below, analyze its runtime and
whether it is correct. If it is correct, give a justification. If it is incorrect,
provide a counterexample.
(i) Student A proposes the following algorithm: First, find a source vertex s in the
graph that has no incoming edges. If there are multiple sources, pick an arbitrary
one. Then, run a DFS-Visit (notice this is only the recursive portion of DFS, not
the entire DFS) on G starting from s. G satisfies the property if and only if the
DFS-Visit visits all the vertices in the graph.
(ii) Student B proposes the following algorithm: First, run DFS on the graph to obtain
a topological sort of the vertices. Let the topological sort be v1 , v2 , . . . , vn . Then,
we check for the following edges (v1 , v2 ), (v2 , v3 ), (v3 , v4 ), . . . , (vn−1 , vn ). If all of
these edges exist, then we say G satisfies the property. If any of the edges are
missing, we say G does not satisfy the property.
(b) Now you want to generalize the algorithm to work for any directed graph. Design a
O(|V | + |E|) time algorithm to determine whether or not the given graph G satisfies the
desired property. You may use the algorithms from part (a) as a subroutine. Make sure
to justify the correctness and runtime of your proposed algorithm.
Discussion Partners: 3