Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

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.
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 = T−xi1 . 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.
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
ab
c
d
e
f
12
g
h
2
5
1
7
2
4
8 1
4
7
3
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, t
∀v ∈ 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
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:
d(v) = max
(q,v)∈E
{min{w(q, v), d[q]}}
Runtime: We first run topological sort, which takes time O(|V |+ |E|). Then, we iterate over
all the vertices and edges again to update the array d, which gives an overall running time of
O(|V |+ |E|).
Problem 6 (Hardness) Recall the 0-1 Knapsack problem, where there are n items with
(positive) weights w1, . . . , wn and (positive) values v1, . . . , vn. The optimization version of this
problem is to maximize the sum of the values for a subset of the items while staying within a
given weight constraint W . An item must be taken in whole and cannot be split into fractional
pieces.
1. State the decision version of this problem.
2. Suppose someone proposes a dynamic programming approach to solving the optimization
problem. He suggests defining V (k,W ) to be the optimal value that can obtained using
only the first k items with a weight bound of W , and proposes to compute V (k,W ) by
maximizing over V (k − 1,W ) and vk + V (k − 1,W − wk). Will this approach yield a
polynomial time algorithm to find the optimal value V (n,W )? Explain why or why not.
Solution. 1. The decision version of the problem can be stated as follows: Given a bound
b ≥ 0, does there exist a subset S of the items such that the sum of the weights of the items in
S is ≤W while the sum of the values is ≥ b?
2. Since this problem is NP-complete, we should guess that this approach will not lead to a
polynomial time algorithm. One reason is that the computation of V (k,W ) requires computing
values of the form V (k−1,W−wk): if we try to compute and store all of the values V (k−1,W ′)
for all the W ′ ≤ W we will encounter in this dependence, it will be far too many values of W ′
(more than polynomially many). This is because there are 2n different subsets of the weights
to subtract from W , and we need to run in time polynomial in n and the number of bits to
represent W , b, {vi}, {wi} in binary.
Problem 7 (True/False) For each of the claims below circle True or False, and justify your
answer. Your justifications are more important than the True/False designations, and must be
succinct, precise and convincing.
All the parts can be adequately answered and justified in a few lines.
All the times below refer to worst-case time.
• Suppose that a problem can be solved in two ways. Approach 1 is a Dynamic Programming
algorithm that runs in O(n2) time. Approach 2 is a divide and conquer algorithm that
reduces an instance of size n to 8 instances of size n/3 and spends Θ(n) time in the divide
and combine steps.
Claim. Approach 1 has a better asymptotic running time.
True False
Solution. False
The recurrence for Approach 2 is: T (n) = 8T (n/3) + Θ(n). Using Master Theorem,
a = 8, b = 3, f(n) = Θ(n), we have nlogb a = nlog3 8 = Ω(n1+); hence it is Case 1.
Solution: T (n) = Θ(nlog3 8). Since log3 8 < 2 , Approach 2 has a better asymptotic
running time.
• We are given an array A with 3n distinct numbers. We want to partition the elements
of A into three equal-sized sets A1, A2, A3 (i.e., |A1| = |A2| = |A3| = n), such that all
elements of A1 are smaller than all elements of A2, and all elements of A2 are smaller than
all elements of A3.
Claim. This task requires Ω(n · log n) time in the comparison-based model.
True False
Solution. False.
We can do this in O(n) time. Use a linear-time selection algorithm to select the element
x of A with rank n and element y with rank 2n. Then compare all the elements of A
to x and y, and partition them into the three sets A1, A2, A3, where A1 contains the
elements that are ≤ x, A2 contains the elements that are > x and ≤ y, and A3 contains
the remaining elements that are > y.
• We are given a directed graph G = (N,E). We wish to determine if there exist two nodes
u, v such that G does not contain any path from u to v.
Claim. This problem can be solved in O(|N |+ |E|) time.
True False
Solution. True.
There exist two nodes u, v such that G does not contain any path from u to v if and only
if the graph is not strongly connected. We can use DFS from class to test if a graph is
strongly connected in O(|N |+ |E|) time.
• We are given a network G = (N,E) with positive integer capacities on the edges, source
node s, sink node t, and a maximum s-t flow f (i.e., a value fe for each edge E satifying
the flow property).
Claim: We can compute a minimum s− t cut in O(|N |+ |E|) time. (Note that the output
is the actual set S).
True False
Solution. True.
Construct the residual network Gr with respect to f and compute the set S of reachable
nodes from s in Gr. Both parts can be done in O(|N | + |E|) time. The minimum s − t
cut is (S,N \ S).
• Claim. Suppose we are given a matrix A of size n × n, where Aij is the length of the
shortest path from node i to node j in an unweighted graph G. Then we can sort all the
n2 numbers {Aij}i,j=1,...n in time O(n2).
True False
Solution. True.
From the special structure of A, we can see that the maximum value of any element in
A is n, since that is the max distance between any two vertices. Thus, we can use any
linear-time sort such as counting sort or bucket sort to sort the n2 numbers in O(n2).
• Consider an algorithm A that has the following runtime recurrence: T (n) = 4 · T (√n) +
O(log n). Another algorithm B has runtime O(log n).
Claim. Algorithm A has the same asymptotic running time as the algorithm B.
True False
Solution. False.
We can solve the recurrence for Algorithm A by changing variabl es so we can apply Master
Theorem. Solving gives that the recurrence should be O(log2(n)), while Algorithm B has
running time O(log n). These are not the same asymptotic running time, so the answer
is False.
• The MAX-CUT problem is as follows: given an undirected, unweighted graph G = (N,E),
and nodes s, t, find an s− t cut of maximum value — i.e., partition N into sets S, T , with
s ∈ S, t ∈ T , maximizing the number of edges (u, v) such that u ∈ S, v ∈ T .
Claim. We can solve MAX-CUT problem by running a max-flow algorithm from the
source s to the terminal t.
True False
Solution. False.
Max-flow is equivalent to finding the min-cut, not the max-cut. (Side remark: MAX-CUT
is actually an NP-hard problem, so that would also imply that P=NP.)
Problem 8 (LP) Suppose we have an extremely efficient LP solver at hand (i.e., implementa-
tion of some new fancy algorithm for the generic Linear Programming problem), and we decide
that we are better off computing graph connectivity using this LP solver.
So let P be the problem: given an undirected unweighted graph G = (N,E), as well as two
nodes s, t, determine if there a path between s and t.
Show how to formulate the problem P as an instance of Linear Program of small size. For
example, you may want to have variables fu,v and fv,u for each (undirected) edge (u, v) ∈ E.
(The number of constraints in the LP should be O(|N |+ |E|).
Solution. The idea is that we can formulate the connectivity problem as a special case of the
flow problem, and just use the LP for the max-flow problem we discussed in class. Specifically,
we think of G as a graph, where each undirected edge {u, v} is replaced by 2 directed edges
(u, v) and (v, u), and associate flow variables fu,v, fv,u to each such edge. The capacity for each
edge is 1. Let the set of directed edges be called E′ (note that |E′| = 2|E|).
Now the LP formulation is exactly as for the max-flow problem discussed. In particular the
LP is to maximize
∑
u:(s,u)∈E′ fs,u −
∑
v:(v,s)∈E′ fv,s subject to the constraints:
fu,v ≥ 0, ∀(u, v) ∈ E′
fu,v ≤ 1, ∀(u, v) ∈ E′∑
v:(u,v)∈E′
fu,v −
∑
v:(v,u)∈E′
fv,u = 0, ∀u ∈ N \ {s, t}
If the optimal LP solution is at least 1, there is a path from s to t (and vice versa). If the
LP solution is 0, s, t are disconnected.