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.
Solution:
No. Here is a counter example.
The correct solution will have edges AB, DC, and AD in the MST. The above solution will result in an incorrect MST with edges AD, BC, and DC.
2. Solve the following recurrences using the Master Method: a. A(n) = 3 A(n/3) + 15
f(n)=15=O(1), 𝑛log𝑏𝑎 =𝑛log33 =𝑛1 This falls under case 1 A(n) = θ(n)
b. B(n) = 4 B(n/2) + n3
f(n)=n3, 𝑛log𝑏𝑎 =𝑛log24 =𝑛2
This can fall under case 3. Now we need to check that
af(n/b)≤cf(n) forsomec<1:
a f(n/b) = 4 * (n/2)3 = 4 * n3/8 = n3/2 = .5 f(n) , so we have found c=.5 such that
a f(n/b) ≤ c f(n) and the inequality checks out, and case 3 applies B(n) = θ(n3)
c. C(n) = 4 C(n/2) + n2
f(n)=n2, 𝑛log𝑏𝑎 =𝑛log24 =𝑛2
This falls under case 2 C(n) = θ( n2 log 𝑛)
d. D(n)=4D(n/2)+n
f(n)=n, 𝑛log𝑏𝑎 =𝑛log24 =𝑛2
This falls under case 1 D(n) = θ(n2)
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.
Find the median of the two arrays. Say the medians are mA and mB. If mA=mB, then this is our median.
Otherwise, say mA < mB then throw away all terms lower than mA in A, and all terms greater than mB in B. Solve the resulting subproblem recursively.
Complexity analysis:
- Divide step takes O(1). This includes finding medians in A and B and throwing away half
of A and B.
- There is no combine step
- Number of subproblems (a) at each step is 1. The size of the subproblem (n/b) is n/2
So we can apply the Master Method:
f(n) = O(1), 𝑛log𝑏 𝑎 = 𝑛log2 1 = 𝑛0= O(1) This falls under case 2 T(n) = θ(log 𝑛)
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.
Solution: Here is a tromino:
The figure below shows a 2nx2n checkerboard with a hole highlighted in dark blue. Here is a divide and conquer solution:
- Divide the grid into 4 equal grids of size 2n-1x2n-1
- Add holes to the three grids that do not have a hole in them. The position of the new
holes should be at the center of the grid so that when each region is solved/tiled
recursively we can cover the remaining three holes with one tromino.
- Solve all 4 subproblems recursively
- When combining the solutions, place a tile over the three holes in the center to complete
the tiling.
- During recursion, when we reach 2x2 grids, we can solve the problem directly by placing
a single tromino to tile the grid (that has a single hole).
2n
2n
Complexity analysis:
Divide steps takes O(1) time. So does the combine step.
Number of subproblems (a) = 4, size of each subproblem is half the size of the original problem, so b=2.
f(n)=O(1), 𝑛log𝑏𝑎 =𝑛log24 =𝑛2 This falls under case 1 T(n) = θ(𝑛2)
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=