Problem 4. (30 pts) Boruvka's MST algorithm: given a n-nodes and m-edges weighted undirected and connected graph G, here's Boruvka's algorithm for finding a MST. procedure Boruvka(G) while (A induces more than one connected-component) do ** A is a set of edges that starts as empty and ends up being the MST. foreach connected-component C formed by A do find ect min-weight edge connecting C with V\C ** Be careful: ec could have already been added to B, you need to avoid duplicates 4 (a) (5 pts) Exhibit how Boruvka's algorithm runs on the following ex- ample on the right. Show all intermediate steps (Any edge whose weight wasn't explicitly stated has weight of 6.) (b) (1 pts) Given a subset of the edges A and the set of connected- components it induces C = {G,C, ,Ck), let E(G) be the set of all edges with one node in Ci and the other in V\Ci. Prove that every edge belongs to at most 2 sets E(Ci) and E(C). Deduce that no matter how many connected components A induces and regardless of their size, it always holds that |E(G) 2m (c) (4 pts) Argue that in each iteration of the while-loop the number of connected components is cut down in at least half. Deduce that we iterate through the while-loop at most log(n) times (d) (20 pts) Show how to implement Boruvka's algorithm in O(m log(n))-time. You are free to do it anyway you'd like, however, you're advised to base your implementation using a combination of Union-Find and Priority-Queues (and maybe Lists too) Hint 1: You want to design your use of the two data-structures so that whenever we check whether the two endpoints of an edge belong to the same connected component, then either we remove the edge and it will be forever disregarded or this edge becomes the first edge in one of the Priority-Queues (and therefore, in the next round Hint 2: Imagine you have t Priority-Queues, each with n elements. While there are several ways to merge them into a single Priority-Queue in time O(ni +n2 + +ni), one simple way is to use Array-to-List conversion and List-to-Array conversion. (What's the runtime for merging two lists?) Problem 4. (30 pts) Boruvka's MST algorithm: given a n-nodes and m-edges weighted undirected and connected graph G, here's Boruvka's algorithm for finding a MST. procedure Boruvka(G) while (A induces more than one connected-component) do ** A is a set of edges that starts as empty and ends up being the MST. foreach connected-component C formed by A do find ect min-weight edge connecting C with V\C ** Be careful: ec could have already been added to B, you need to avoid duplicates 4 (a) (5 pts) Exhibit how Boruvka's algorithm runs on the following ex- ample on the right. Show all intermediate steps (Any edge whose weight wasn't explicitly stated has weight of 6.) (b) (1 pts) Given a subset of the edges A and the set of connected- components it induces C = {G,C, ,Ck), let E(G) be the set of all edges with one node in Ci and the other in V\Ci. Prove that every edge belongs to at most 2 sets E(Ci) and E(C). Deduce that no matter how many connected components A induces and regardless of their size, it always holds that |E(G) 2m (c) (4 pts) Argue that in each iteration of the while-loop the number of connected components is cut down in at least half. Deduce that we iterate through the while-loop at most log(n) times (d) (20 pts) Show how to implement Boruvka's algorithm in O(m log(n))-time. You are free to do it anyway you'd like, however, you're advised to base your implementation using a combination of Union-Find and Priority-Queues (and maybe Lists too) Hint 1: You want to design your use of the two data-structures so that whenever we check whether the two endpoints of an edge belong to the same connected component, then either we remove the edge and it will be forever disregarded or this edge becomes the first edge in one of the Priority-Queues (and therefore, in the next round Hint 2: Imagine you have t Priority-Queues, each with n elements. While there are several ways to merge them into a single Priority-Queue in time O(ni +n2 + +ni), one simple way is to use Array-to-List conversion and List-to-Array conversion. (What's the runtime for merging two lists?)
