CSOR 4231辅导、c++，Python程序辅导
- 首页 >> Algorithm 算法 CSOR 4231 Fall 2021
Final Practice Problems
These problems are ungraded, and are intended as a study aid. They are very similar in
style and level to the problems that will appear on the final. The final exam will have between
6 and 8 problem (including the true/false question).
The final covers all the material until lecture 23 (including all the material covered by HW1
through HW6), with a bigger emphasis on the post-midterm material. There final is 2h30min.
Like in midterm, most problems won’t require full analysis (correctness + runtime); instead
each problem will ask explicitly which part of the analysis, if any, is required.
Problem 1 (DFS) If we perform depth-first-search on graph, we obtain a forest containing
all the vertices of the graph and a subset of the edges. Each node u has a “discovery time” u.d
and a “finish time” u.f . We consider the possible relationships between the intervals [u.d, u.f ]
and [v.d, v.f ] for two distinct vertices u and v. For each, either draw a DFS tree where the
relationship holds, or explain why it is impossible.
u.d < v.d and v.f < u.f
u.f < v.d
u.d < v.d < u.f < v.f
Solution. 1. This situation arises when v is a descendant of u in the DFS tree. An example
is pictured in Figure 1. below.
2. This situation can arise when u is discovered before v and v is not reachable from u. An
example is pictured in Figure 2. below for a directed graph.
3. This is impossible. Since u is discovered before v but not yet finished, all of the nodes
reachable from v will be discovered before u is finished, hence u.d < v.d implies that v.f < u.f .
Problem 2 (MST) Consider the undirected, connected, weighted graph pictured in Fig. 3
below. Use an algorithm of your choice to find a minimum spanning tree in that graph. Briefly
explain your algorithm, indicate which edges of the graph are contained in your final tree, and
the order in which you add them to your tree.
Solution. We will use Kruskal’s algorithm, which initially considers these 8 vertices as 8
separate components and iteratively builds a minimal weight spanning tree by adding a lightest
remaining edge that connects two previously disconnected components. When there is more
than one lightest such edge (i.e. there is a tie for the lightest edge with this property), we can
choose among these tied candidates arbitrarily.
We start by adding the light edge of weight 1 from b to e. We next add the edge of weight 1
from e to h. Next we add the edge of weight 2 from e to a, then the edge of weight 2 from b to d.
1
Figure 1: 1. v is a descendant of u in the DFS tree.
Now, we add the edge of weight 3 from c to f. At this point, we have 3 connected components:
one containing b,e,h,a,d, one containing c and f, and one containing just g. As a lightest edge
connecting two of these components, we can next take the edge of weight 4 connecting e and c,
and finally the edge of weight 4 connecting h and g.
Problem 3 (Hardness: Search to Decision) Another important hard problem (NP-hard)
is the SUBSET-SUM problem. The decision version of the problem is formulated as follows:
we are given n numbers S = {x1, x2, . . . xn}, in the range {0, 1, . . . 2n ? 1} (note that it takes n
bits to describe each number), and a target sum T , determine if there’s a subset S′ ? S such
that
∑
i∈S′ xi = T .
Suppose we have a magic algorithm M that solves the decision version of the SUBSET-SUM
problem in polynomial time. Prove that, in this case, we can actually recover the set S′ in
polynomial time as well. In particular, assuming M, design a polynomial time algorithm for
the following problem: given a set S = {x1, . . . xn}, and a target T , find a set S′ such that∑
i∈S′ xi = T .
Solution. Note that for a subset S′ = {xi1 , xi2 . . . xik} of S, we have
∑
ij∈S′ xij = T if and
only if
∑
ij∈S′\{i1} xij = Txi1 . This forms the basis of algorithm: we first check if such a subset
S′ exists. If not, we output and stop. If yes, however, we iterate over the elements of S and
for each xi, we check whether there exists a subset S
′′ of S \ {xi} such that
∑
ij∈S′′ xi = T ? xi
with M. If so, we add xi to S′, subtract xi from T , and move on to the next element of S.
Once T hits 0 during any iteration, we output S′ and stop.
Runtime: it’s just (at most) n calls to the procedure M, and hence polynomial overall.
2
Figure 2: 2. u is discovered first and v is not reachable from u.
Problem 4 (FLOW)
Consider a flow network as a directed graph G where each edge (u, v) has a capacity
c(u, v) ≥ 0. We designate a source node s and a sink node t. Recall that a cut (S, T ) is
a partition of the nodes into sets S and T with s ∈ S and t ∈ T . The capacity of the cut
(S, T ) is the sum of the capacities of the edges that go from a vertex in S to a vertex in
T . Is it possible to have such a G where the max flow from s to t is 13 and there exists a
cut (S, T ) with capacity 10? Explain your answer.
Consider a directed graph G, containing vertices s, u, t (along with many others). Describe
an efficient way to compute the number of edge disjoint paths between s and t that do
not go through the vertex u.
Solution. For the first part, recall the max-flow, min-cut theorem. This states that the
maximum flow we can send from s to t is equal to the minimum capacity of a cut (S, T ) such
that s ∈ S and t ∈ T . Thus, if there is a cut with capacity 10, the max flow must be at most
10, and hence cannot be 13. So no, this is not possible.
For the second part, turn G into a flow network by assigning a capacity to each edge. If the
edge does not involve u, then assign it a capacity of 1. If it does involve u, assign it a capacity
of 0. Thus, edges that travel through u will not contribute to the max flow. Now, if we compute
the max flow from s to t in such a graph, it will count the number of edge disjoint paths, since
a flow of 1 can be sent along each edge disjoint path, and no additional flow can then be sent.
Problem 4 (Path Width in DAG) Suppose we are given a directed acyclic graph G =
(N,E) with weights wu,v ≥ 0 for each edge (u, v). The graph represents a network of (one-way)
roads, where wu,v represents the width of the road from u to v. We are also given two node in-
dices: s, the start node, and t, the destination node. The goal of the problem is to determine the
Figure 3: graph for the problem MST.
maximal width W so that there is a path from s to t composed entirely of roads of width at least
W (in other words, we need to determine the width of the widest car that can travel from s to t.)
Design an algorithm that, given graph G, widths wu,v for (u, v) ∈ E, and nodes s, t, determines
the maximal width W . Your runtime should be O(|V |+ |E|). Briefly argue runtime bound and
correctness.
Solution. Our algorithm is as follows:
Algorithm 1 Path Width in DAG
Given: G = (V,E), s, tv ∈ N , set d[v]← 0, p[v]←⊥
d[s]← +∞
for each node a ∈ N iterating in topological order do
for each neighbor b of a do
if d[b] < min{d[a], w(a, b)} then
d[b] = min{d[a], w(a, b)}
p[b] = a
end if
end for
end for
return d[t]
Correctness: After running topological sort, we can employ a dynamic programming approach
4
to compute the maximum width. When iterating in topological order, we can write a recurrence
relation that computes the max width d(v) up to some node v i.e. a value such that we can
always find a path from s to some node v such that all roads along that path have width at
least the max width value. We can compute this max width by considering the subproblems of
finding the max width to all neighbors of v and simply comparing to the weight of the given
edge, which yields the recurrence relation:
Final Practice Problems
These problems are ungraded, and are intended as a study aid. They are very similar in
style and level to the problems that will appear on the final. The final exam will have between
6 and 8 problem (including the true/false question).
The final covers all the material until lecture 23 (including all the material covered by HW1
through HW6), with a bigger emphasis on the post-midterm material. There final is 2h30min.
Like in midterm, most problems won’t require full analysis (correctness + runtime); instead
each problem will ask explicitly which part of the analysis, if any, is required.
Problem 1 (DFS) If we perform depth-first-search on graph, we obtain a forest containing
all the vertices of the graph and a subset of the edges. Each node u has a “discovery time” u.d
and a “finish time” u.f . We consider the possible relationships between the intervals [u.d, u.f ]
and [v.d, v.f ] for two distinct vertices u and v. For each, either draw a DFS tree where the
relationship holds, or explain why it is impossible.
u.d < v.d and v.f < u.f
u.f < v.d
u.d < v.d < u.f < v.f
Solution. 1. This situation arises when v is a descendant of u in the DFS tree. An example
is pictured in Figure 1. below.
2. This situation can arise when u is discovered before v and v is not reachable from u. An
example is pictured in Figure 2. below for a directed graph.
3. This is impossible. Since u is discovered before v but not yet finished, all of the nodes
reachable from v will be discovered before u is finished, hence u.d < v.d implies that v.f < u.f .
Problem 2 (MST) Consider the undirected, connected, weighted graph pictured in Fig. 3
below. Use an algorithm of your choice to find a minimum spanning tree in that graph. Briefly
explain your algorithm, indicate which edges of the graph are contained in your final tree, and
the order in which you add them to your tree.
Solution. We will use Kruskal’s algorithm, which initially considers these 8 vertices as 8
separate components and iteratively builds a minimal weight spanning tree by adding a lightest
remaining edge that connects two previously disconnected components. When there is more
than one lightest such edge (i.e. there is a tie for the lightest edge with this property), we can
choose among these tied candidates arbitrarily.
We start by adding the light edge of weight 1 from b to e. We next add the edge of weight 1
from e to h. Next we add the edge of weight 2 from e to a, then the edge of weight 2 from b to d.
1
Figure 1: 1. v is a descendant of u in the DFS tree.
Now, we add the edge of weight 3 from c to f. At this point, we have 3 connected components:
one containing b,e,h,a,d, one containing c and f, and one containing just g. As a lightest edge
connecting two of these components, we can next take the edge of weight 4 connecting e and c,
and finally the edge of weight 4 connecting h and g.
Problem 3 (Hardness: Search to Decision) Another important hard problem (NP-hard)
is the SUBSET-SUM problem. The decision version of the problem is formulated as follows:
we are given n numbers S = {x1, x2, . . . xn}, in the range {0, 1, . . . 2n ? 1} (note that it takes n
bits to describe each number), and a target sum T , determine if there’s a subset S′ ? S such
that
∑
i∈S′ xi = T .
Suppose we have a magic algorithm M that solves the decision version of the SUBSET-SUM
problem in polynomial time. Prove that, in this case, we can actually recover the set S′ in
polynomial time as well. In particular, assuming M, design a polynomial time algorithm for
the following problem: given a set S = {x1, . . . xn}, and a target T , find a set S′ such that∑
i∈S′ xi = T .
Solution. Note that for a subset S′ = {xi1 , xi2 . . . xik} of S, we have
∑
ij∈S′ xij = T if and
only if
∑
ij∈S′\{i1} xij = Txi1 . This forms the basis of algorithm: we first check if such a subset
S′ exists. If not, we output and stop. If yes, however, we iterate over the elements of S and
for each xi, we check whether there exists a subset S
′′ of S \ {xi} such that
∑
ij∈S′′ xi = T ? xi
with M. If so, we add xi to S′, subtract xi from T , and move on to the next element of S.
Once T hits 0 during any iteration, we output S′ and stop.
Runtime: it’s just (at most) n calls to the procedure M, and hence polynomial overall.
2
Figure 2: 2. u is discovered first and v is not reachable from u.
Problem 4 (FLOW)
Consider a flow network as a directed graph G where each edge (u, v) has a capacity
c(u, v) ≥ 0. We designate a source node s and a sink node t. Recall that a cut (S, T ) is
a partition of the nodes into sets S and T with s ∈ S and t ∈ T . The capacity of the cut
(S, T ) is the sum of the capacities of the edges that go from a vertex in S to a vertex in
T . Is it possible to have such a G where the max flow from s to t is 13 and there exists a
cut (S, T ) with capacity 10? Explain your answer.
Consider a directed graph G, containing vertices s, u, t (along with many others). Describe
an efficient way to compute the number of edge disjoint paths between s and t that do
not go through the vertex u.
Solution. For the first part, recall the max-flow, min-cut theorem. This states that the
maximum flow we can send from s to t is equal to the minimum capacity of a cut (S, T ) such
that s ∈ S and t ∈ T . Thus, if there is a cut with capacity 10, the max flow must be at most
10, and hence cannot be 13. So no, this is not possible.
For the second part, turn G into a flow network by assigning a capacity to each edge. If the
edge does not involve u, then assign it a capacity of 1. If it does involve u, assign it a capacity
of 0. Thus, edges that travel through u will not contribute to the max flow. Now, if we compute
the max flow from s to t in such a graph, it will count the number of edge disjoint paths, since
a flow of 1 can be sent along each edge disjoint path, and no additional flow can then be sent.
Problem 4 (Path Width in DAG) Suppose we are given a directed acyclic graph G =
(N,E) with weights wu,v ≥ 0 for each edge (u, v). The graph represents a network of (one-way)
roads, where wu,v represents the width of the road from u to v. We are also given two node in-
dices: s, the start node, and t, the destination node. The goal of the problem is to determine the
Figure 3: graph for the problem MST.
maximal width W so that there is a path from s to t composed entirely of roads of width at least
W (in other words, we need to determine the width of the widest car that can travel from s to t.)
Design an algorithm that, given graph G, widths wu,v for (u, v) ∈ E, and nodes s, t, determines
the maximal width W . Your runtime should be O(|V |+ |E|). Briefly argue runtime bound and
correctness.
Solution. Our algorithm is as follows:
Algorithm 1 Path Width in DAG
Given: G = (V,E), s, tv ∈ N , set d[v]← 0, p[v]←⊥
d[s]← +∞
for each node a ∈ N iterating in topological order do
for each neighbor b of a do
if d[b] < min{d[a], w(a, b)} then
d[b] = min{d[a], w(a, b)}
p[b] = a
end if
end for
end for
return d[t]
Correctness: After running topological sort, we can employ a dynamic programming approach
4
to compute the maximum width. When iterating in topological order, we can write a recurrence
relation that computes the max width d(v) up to some node v i.e. a value such that we can
always find a path from s to some node v such that all roads along that path have width at
least the max width value. We can compute this max width by considering the subproblems of
finding the max width to all neighbors of v and simply comparing to the weight of the given
edge, which yields the recurrence relation: