Week 3: Divide and Conquer

Question 1

What is the Divide and Conquer Approach?

Answer 1

1. Divide the problem into some subproblems, which are smaller instances of the same problem (D(n))
2. Conquer the subproblems by solving them recursively, or if they are small enough just solve the subproblems normally (aT(n/b))
3. Combine the solutions to the subproblems into the solution for the original problem (C(n))

T(n)=Θ(1) if n≤c

T(n) = D(n) + aT(n/b) + C(n) otherwise

Question 2

What is Merge Sort?

Answer 2

Divide: Divide the n element sequence into two subsequces of n/2 elements each Θ(1)

Conquer: Sort the two subsequences recursively using merge sort 2T(n/2)

Combine: Merge the two sorted subsequences to produce the sorted answer Θ(n)

T(n)=Θ(1) if n=1
T(n) = Θ(1) + 2T(n/2) + Θ(n) otherwise

Question 3

Merge Sort time complexity?

Answer 3

The merge step has a time complexity of O(n)

The sequence of size n will be divided log2(n) times

Overallm the time complexity of the merge sort algorithm is O(nlog2(n))

Question 4

What is the Substitution method?

Answer 4

The substitution method is a method for solving recursive time complexity algorithms for T(n).

T(n) = {c n = 1
{2T(n/2) + cn n > 1

Base case: Show that the inequality holds for some n sufficiently small

Ind. Hyp: Assume that T(n) ≤ cn log n for c > 0 holds for all positive m < n, in particular for m = n/2

Step case: use the Ind. Hyp to replace part of the time complexity formula

Question 5

How to make good guesses

Answer 5

Guessing a solution requires both experience and creativity:

• Heuristics can help become a good guesser.
• Recursion trees can help with this as well

Start with loose upper and lower bounds and allow them to converge

Algebraic manipulation can be used to make a recurrance simular to more familiar ones