The most well-known algorithm design technique.

TODO

General Divide and Conquer Recurrence (Master Theorem)

If a recurrence relation is of the following format—

T(n) = aT(n/b) + f(n) \quad \text{where} f(n) \in \Theta (n^d), d \ge 0

—we can use Master Theorem to quickly tell time efficiency.

Master Theorem:

T(n)

This’ll be on the next exam!

Mergesort

Algorithm:

1. Split array (A) in two and make copies of each half in arrays (B and C).
2. Recursively sort arrays B and C
3. Merge sorted arrays. TODO

Splitting is easy, but how to you merge?

We only need to compare two elements when merging, because B and C are sorted.

mergesort
merge

Analysis

As a recurrence relation, this is:

T(n) = 2T(n/2) + f(n)

Where f(n) is the merge operation

We know the recursive depth is \log n. In the worst case, we do n comparisons on each level.

Thus, we intuitively know we need at most O(n \log n) comparisons.

Now, let’s return to the master theorem solution.

We can say f(n) \in O(n)

Thus, a=2, b=2, d=1.

Thus, T(n)= \T(n \log n)

Tradeoff: Extra memory use.

Quicksort

Select a pivot. Rearrange the list so all element in first s positions are smaller than or equal to the pivot and all the element in the remaining n-s positions are \le the pivot.

TODO

Hoare’s Partitioning Algorithm

TODO

Analysis

Partitioning can be done in O(n) time, where n is the size of the array.

Let T(n) be the number of comparisons required.

As a recurrence relation, this is:

T(n) = T(n-k) + T(k-1) + n

where the pivot ends up at position k.

To find best/worst/avg we must find the k that causes it.

Worst case, k=1 (our pivot is a max or min).

Best case, k=??? (we almost partion into half)

This lets us apply master theorem. a=2, b=2, d=1. This is case 2.

T(n) \in \Theta (n \log n )

Average case is more complex to work out, ends up being TODO.

Improvements

• Pick good pivot (use a median).
• Use insertion sort on small subfiles.
• Eliminate recursion.

Note — Using all of these improvements can result in 20—25% improvement.

Binary Tree Algorithms

Structure is obviously ready for divide and conquer.

Height

TODO

Computing height of binary tree.

• Idea: Know ??? about left subtree and right subtree, and add 1.
  • (??? Add max of left subtree and max of right subtree plus one?)

Plus one for the root.

h(T) = TODO

Closest-Pair by Divide and Conquer

Recall — When we did this by brute force, we generated every single pair and checked the distance (O(???)).

TODO

Algorithm:

1. Divide points into two subsets, P_1 and P_2 split by a line x=m.
   • Half of points should be on the left (or on) the line, the other half should be on the right (or on) the line.
2. Find the closest pair in the left half and the closet pair in the right half
   • We know that the points in-between these pairs are the only points that could possibly be smaller. Anything outside can be excluded (???) We may actually just use the min coord of a the shorted pair???

Analysis

This function can be represented as

T(n) = 2T(n/2) + f(n)

??? case, f(n) \in O(n). (What is f(n)?)

By master theorem, this gives a=2,b=2,d=1

Thus TODO