Computer Science > SOLUTIONS MANUAL > University of TorontoCSC 373a2 ( WITH DETAILED EXPLANATIONS ) (All)

University of TorontoCSC 373a2 ( WITH DETAILED EXPLANATIONS )

Document Content and Description Below

Problem 1 1. Given an algorithm taking inputs (a) G = (V; E) a connected, undirected graph (b) w : E ! Z+ a weight function (c) T ⊆ E, a MST of G (d) e1 = fu; vg 62 E, an edge no in G (e) w1 2... Z+, a weight for e1 and outputs a MST T1 for G1 = (V; E [ fe1g) with w(e1) = w1. For full marks, your algorithm must be more efficient than computing a MST for G1 from scratch. Justify that this is the case by analysing your algorithms worst-case running time. Finally, write a detailed proof that your algorithm is correct. Solution. Algorithm (a) Let G1 = (V; E [ fe1g), let e1 = (s; t) for some s; t 2 V (b) Find the unique simple cycle c in G1. Starting from s (or t, the choice is arbitrary), run DFS on G1 with slight modification. When looking at vertex u 2 V , Check if v:color is GRAY . Break from DFS if true, otherwise continue DFS. (c) Find the largest weight edge e2 in the cycle. Iterate through G1:E, find e2 = (u; v) 2 G1:E such that u:color and v:color are both GRAY (in the cycle) and w(u; v) is maximum of all edges with GRAY vertices (max weighted edge). (d) Return MST T1 = T [ fe1g n fe2g Analysis (a) Since we are adding a constant time check at every while iteration and DFS itself has a run time of O(V + E), the part of algorithm for finding a cycle (modified DFS) has a worst case running time of O(V + E) (b) The loop over all vertices to locate the maximum weight edge runs for jEj iterations, each time doing a constant time operation. hence has a worst case running time of O(E) (c) Altogether the algorithm runs for O(V +E), which is more efficient by computing MST from ground up which takes O(E lg V ) 11 Function DFS-Visit (G; u) 2 u:color GRAY 3 for v 2 G1:Adj[u] do 4 if v:color is GRAY then 5 Exit-DFS 6 if v:color is W HITE then 7 DFS-Visit(G; v) 8 u:color BLACK 9 Function Find-MST-1 (G; w; T; e1; w1) 10 G1 (V; E = E [ fe1g) with w : E ! R and w(e1) = w1 11 (s; t) e1 12 for v 2 V do 13 v:color W HITE 14 DFS-Visit(G1; s) 15 maxw 0 16 e2 NIL 17 for (u; v) 2 G1:E do 18 if u:color = GRAY and v:color = GRAY and w(u; v) > maxw then 19 maxw w(u; v) 20 e2 (u; v) 21 T1 T [ fe1g n fe2g return T1 Lemma. The graph G1 = (V; E = E [ fe1g) has a unique simple cycle c, and e1 is in c Proof. Let T ⊆ E, and e1 = (s; t). Since T is MST, s is reachable from t, i.e. exists a path p such that t p s. Consider E1 = E [ fe1g, we have c = s ! t p s = hv0 = s; · · · ; vk = si. Therefore e1 is in c. Now we prove c is unique. This is equivalent to proving that p is unique, since if adding e1 to E produces more than 1 cycle, then there must exists p0 such that p0 6= p. This is not possible since s p t p0 s forms a cycle, which is not possible in MST T. Also, c is simple because T is simple. Proof of correctness Proposition. The output T1 is a MST for G1 = (V; E = E [ fe1g) Proof. By correctness of DFS, when we first explored (u; v), if v:color is GRAY , then (u; v) is a back edge, indicating we have found a cycle c in the graph. By the previous lemma and the fact that we started from s where e1 = (s; t), we will always find such a cycle (i.e. discover t such that s 2 G1:Adj[t] and s:color is GRAY ). When Exit-DFS is called, the vertices v 2 V such that v:color is GRAY represents vertices [Show More]

Last updated: 2 years ago

Preview 1 out of 15 pages

Buy Now

Instant download

We Accept: