Discussion 5
1. Suppose we have two graphs G1 = (V1, E1) and G2 = (V2, E2), along with T1 which is a MST of G1 and T2 which is a MST of G2. Now consider a new graph G = (V, E) such that V = V1 U V2 andE=E1 UE2 UE3 whereE3 isanewsetofedgesthatallcrossthecut(V1,V2).
Consider the following algorithm, which is intended to find a MST of G.
Does this algorithm correctly find a MST of G? Either prove it does or prove it does not.
2. Solve the following recurrences using the Master Method:
a. A(n) = 3 A(n/3) + 15
b. B(n) = 4 B(n/2) + n3
c. C(n) = 4 C(n/2) + n2
d. D(n)=4D(n/2)+n
3. There are 2 sorted arrays A and B of size n each. Design a D&C algorithm to find the median of the array obtained after merging the above 2 arrays (i.e. array of length 2n). Discuss its runtime complexity.
4. A tromino is a figure composed of three 1×1 squares in the shape of an L. Given a 2nx2n checkerboard with 1 missing square, tile it with trominoes. Design a D&C algorithm and discuss its runtime complexity.