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 and E = E1 U E2 U E3 where E3 is a new set of edges that all cross the cut (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) = 4 D(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 1x1 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.
