CSOR 4231代写、c++，Python程序代写

日期：2021-12-21 11:13

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: