COT5405: ANALYSIS OF ALGORITHMS
Sample Exam III
Date: 2019
Time: 100 minutes
Professor: Alper Ungor (Oce CSE 534)
This is a closed book exam. No collaborations are allowed. Your solutions should be concise, but complete, and handwritten clearly. Use only the space provided in this booklet, including the even numbered pages. When appropriate, feel free to give reference to the algorithms, denitions and concepts discussed in class rather than describing them in detail.
GOOD LUCK!
First name:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Last name:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Credit
Max
Problem 1
20
Problem 2
30
Problem 3
30
Problem 4
30
Total
110
1. [20 points] True/False. No need for justication.
(a) True/False
For an undirected, connected graph G with distinct edge weights, the minimum spanning tree of G includes the minimum-weight edge in every cycle in G.
(b) True/False
(Let G = (V, E) be an undirected connected graph with distinct edge weights.)
For every vertex v ∈ V, the edge with the smallest weight incident to v must be an edge in the minimum spanning tree of G.
(c) True/False
(Consider an undirected, connected graph G = (V, E) with distinct edge weights. The second smallest spanning tree of a given graph G, is dened as a/the spanning tree of G with the smallest total weight except for the minimum spanning tree.)
The second smallest spanning tree of G is unique.
(d) True/False
If all edge capacities in a ow network are integer multiples of 35, then the value of the maximum ow must be a multiple of both 5 and 7.
(e) True/False
(Let G = (V,E) be a directed graph with nonnegative weights on edges, and γ(p,q) denote the length of the longest simple path between p and q.)
The triangle inequality γ(p, q) + γ(q, r) ≤ γ(p, r) holds for every p, q, and r in V .
3
4
2. [30 points] Minimum Spanning Tree Update
Consider an undirected, connected graph G = (V,E) with edge weights w : E → Z+, and a minimum spanning tree T = (V,E′) of G, both given as adjacency lists. Consider the following updates on G. For each case, decide whether an update might be necessary, and if so, describe and analyze an ecient algorithm for updating the minimum spanning tree.
(a) The weight of a particular edge e ∈ E − E ′ is increased to w^ (e) > w(e). (b) The weight of a particular edge e ∈ E − E ′ is decreased to w^ (e) < w(e).
(c) The weight of a particular edge e ∈ E ′ is decreased to w^ (e) < w(e). (d) The weight of a particular edge e ∈ E ′ is increased to w^ (e) > w(e).
(e) Anewedgee=(u,v)∈/EisaddedtoEwithweightw^(e).
5
6
3. [30 points] An Alternative Algorithm for All Pairs Shortest Path Problem Let G = (V, E) be a directed graph with n vertices and weighted (-, 0, or +) edges.
(a) How could we delete an arbitrary vertex v from this graph, without changing the shortest-path distance between any other pair of vertices? Describe and analyze an algorithm that constructs a directed graph G′ = (V′,E′) with weighted edges, where V ′ = V − {v}, and the shortest-path distance between any two nodes in G ′ is equal to the shortest-path distance between the same two nodes in G, in O(n2) time.
(b) Suppose we have already computed all pairs shortest-path distances in G′. Describe and analyze an algorithm to compute the shortest-path distances from v to every other vertex, and from every other vertex to v, in the original graph G, in O(n2) time.
(c) Describe and analyze a new all-pairs shortest path algorithm that runs in O(n3) time by combining parts (a) and (b).
7
8
4. [30 points] Flow Networks
Consider the ow network G = (V,E), where V = {s,a,b,c,d,e,f,g,t}, s is the source, t is the sink, and the edge set with capacities is E = { ((s, a), 3), ((s, b), 6), ((a, c), 4), ((a, d), 2), ((b, d), 3), ((b, e), 5), ((c, f), 1), ((d, f), 6), ((d, g), 7), ((e, g), 2), ((f, t), 8), ((g, t), 5) }.
(a) Draw this ow network G and nd a minimum cut on it.
(b) Give a maximum ow function f : E → R on G matching the minimum cut.
(c) Is the maximum ow function f on G unique? Justify.
(d) Prove or disprove the claim: The maximum ow function on a ow network is unique
if and only if the minimum cut on it is unique.
(e) Draw the residual graph for ow f that you built in part (b).
(f) Describe and analyze an ecient algorithm to determine whether a given ow network has a unique maximum ow. [Hint: First give a characterization on the residual graph.]
9
10