Discussion 5

Description

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:

2. 1. A(n) = 3 A(n/3) + 15

2. 2. B(n) = 4 B(n/2) + n³

   3. C(n) = 4 C(n/2) + n²

   4. D(n) = 4 D(n/2) + n

2. 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.

2. A tromino is a figure composed of three 1×1 squares in the shape of an L.

Given a 2ⁿx2ⁿ checkerboard with 1 missing square, tile it with trominoes.

Design a D&C algorithm and discuss its runtime complexity.