Design and Analysis of Algorithms: Divide and Conquer

Merge sort recurrence:



We "solve" these by finding a closed-form equation that describes the recurrence but without recursion.
Solution: T(n) = Θ(n lg n)

Methods:

• Substitution method: Guess a solution and then use induction to prove it.
• Recursive-tree method: Convert the recurrence into a tree whose nodes represent costs incurred at each level.
• Master method:
  Solves recurrences of the form:
  T(n) = aT(n / b) + f(n)
  where a ≥ 1, b > 1.

Technicalities
We often omit floors, ceilings, and boundary conditions. For instance, if n is odd, we may say n / 2 anyway.

Try every combination of two elements!
A n choose 2 problem, so order of Ω(n²).
n choose 2 will be about 1/2 n², since it equals n(n - 1) / 2. So we can establish a lower bound by setting c = 1/3, for instance, and n choose 2 will always be bounded from below by c*n².

We loon at the problem differently: let's find the nonempty, contiguous subarray of our array whose values have the largest sum. We call this the maximum subarray.

To solve this problem, we divide an array A into three subarrays, and ask what is the maximum subarray in each:

1. From A[low] to A[midpoint - 1].
2. Crossing the mid-point.
3. From A[midpoint + 1] to A[high]

Problems 1 and 3 are simply this same problem on a smaller array! Problem 2 can be solved by finding the maximum subarrays in low-to-mid and in mid+1-to-high.

The recurrence is the same as for merge sort.

We divide each of our initial matrices into four sub-matrices, and multiply them. Which we do by dividing each of them into four...

In the base case when each matrix has only one member, we just multiply them and return the result.

So what is our recurrence? Each step except the base case multiplies eight matrices of size n / 2. So they contribute 8T(n / 2) to running time. There are also four matrix additions of matrices containing n² / 4 entries -- squared because n specifies an n x n matrix. So this contributes Θ(n²) time.

So our recurrence is:



The master method will show us that the solution to this recurrence is:
T(n) = Θ(n³)

By adding ten additions, we can cut the divide portion of our algorithm down to seven multiplications instead of eight.

Let's try one!

Here is the method:

For two matrices:



Define:

P₁ = A(F - H)
P₂ = H(A + B)
P₃ = E(C + D)
P₄ = D(G - E)
P₅ = (A + D) * (E + H)
P₆ = (B - D) * (G + H)
P₇ = (A - C) * (E + F)

Then:



So let's try this example:



Important Lesson

There are often serious trade-offs between set-up time and aymptotic run-time. One must carefully consider how large one's inputs are likely to be before opting for a complex algorithm like Strassen's. On modern hardware optimized for matrix multiplication, matrix sizes often need to be in the thousands before Strassen's algorithm yields significant gains.

The monks in a temple have the job of moving all of the disks on one peg to another, constrained by these rules:
1) Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk.
( Source )



Recurrence:



Why is this the recurrence? Well, to move disk n, we first move disks 1 to n - 1 to the spare peg, then move n to the target peg, then move disks 1 to n - 1 to the target peg.

So we guess the closed-form solution is something like 2ⁿ. Why? Well, we multiply by a factor of 2 each recursion!
Now, let's try writing out a few elements of the sequence:
T(0) = 0
T(1) = 2*0 + 1 = 1
T(2) = 2*1 + 1 = 3
T(3) = 2*3 + 1 = 7
T(4) = 2*7 + 1 = 15
T(5) = 2*15 + 1 = 31
So is the answer 2ⁿ - 1?
Base case: T(0) = 0 = 2⁰ - 1.
Yes!
Now induction: we want to show that, if T(n - 1) = 2^{(n - 1)} - 1, then T(n) will equal 2ⁿ - 1.
How proof by induction works: we have proved our base case. Now we try to prove that for any n, if for n - 1 (or sometimes all smaller n) our hypothesis is true, then it is true for n as well. And since we have already proved that for n = 0 it is true, that will mean it will be true for all n whatsoever.
So we substitute in for n - 1:
T(n) = 2(2^{(n - 1)} - 1) + 1
= 2 * 2^{(n - 1)} - 2 + 1
= 2ⁿ - 1
And we are done!

Let's look at the recurrence:
T(n) = T(n/3) + T(2n/3) + n
T(0) = 1
T(1) = 1

This does not have the form the master method requires. And if we sketch a recursion tree, not every node is the same on a level, so it is different from what we usually deal with there. But if we do diagram a recursion tree, we will see that the work looks constant at each level, like a master theorem case 2. And since the function part of the equation is f(n) = n, let's "guess":
T(n) <= cn log n

But that is just our hunch: we have to prove it!

Let's look at base cases for our inductive proof. Use floors for divisions! Is:

• T(0) <= c(0 * log 0) --> nonsense! (There is no log 0.)
  
• T(1) <= c(1 * log 1) --> false! (There is no such c.)
  
• T(2) <= c(2 * log 2) --> true!
  T(2) = T(floor(2/3)) + T(floor(4/3)) + 2 = 1 + 1 + 2 <= c(2 * log 2) = c(2 * 1)
  So if we set c = 2 (or greater) the inequality holds.

How many base cases do we need to examine? We will see!
But we can prove it for any given "small" n > 2 by setting:
c ≥ T(n) / n log n

Recursion step:
We assume that for k where:
2 <= k < n
the claim is true.
Now, we need to show that if for sub-problems smaller than n the claim is true, then it is true for n.