CSC301.01 2015F, Class 05: Divide and Conquer Approaches
========================================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Divide and Conquer Algorithms.
* Analyzing Divide-and-Conquer Algorithms.
* Estimating Recurrence Relations.
* Solving Recurrence Relations with Recursion Trees.
* Proving Recurrence Relations with the Substitution Method.
* Solving Recurrence Relations with the Master Theorem.

Preliminaries
-------------

### Admin

* My normal office hours are MWF 11:00-11:50.  I've added MWF 8:30-9:00.
  You sign up for those at <https://rebelsky.youcanbook.me>.  

### Upcoming Work

* For Wednesday: Problems 2-1, 2-2, 2-3, 2-8, 2-13, 2-14, 2-15, 2-18, 2-23, 
  2-32, 2-37, any two interview problems from chapter 2.  
* Revised: Problems 2-1, 2-2, 2-8, 2-13, 2-18, 2-23, two interview problems
    * Turn in *hardcopy*.
    * I prefer that you write your homework in LaTeX.  If you don't know 
      LaTeX, now is a good time to start learning!
* For Wednesday: Read Skiena 4-10.  (Optionally: Read CLRS 4.)

### Extra Credit

#### Academic

* CS Table, *Tuesdays*, topic Cellular Networks for Developing Countries
* CS Extras, Thursdays, topics forthcoming.
* Convo, Thursday, 11am.

#### Peer

* Congrats to Men's Soccer! (And to EE for the picture!)
* Congrats to Women's Soccer!

### Questions

Divide and Conquer Algorithms
-----------------------------

Basic strategy

* Take a large problem and divide it into smaller problems (does
  smaller = simpler)
* Solve the smaller problems (often using the same technique)
* Compose the solved problems into a solution to the bigger problem.

What divide and conquer algorithms do you already know?

* Merge sort
    * Split values in half
    * Sort each half
    * Merge by repeatedly removing the smallest element from
      either sorted half
* Binary search
    * Requirement on data: Sorted!
    * Split values in half
    * Look at middle
    * Search in appropriate half
* Quicksort
    * Pick a pivot
    * Separate into smaller than pivot and larger than pivot
    * Sort the two halves
    * Join them together (can happen automatically)

Analyzing Divide-and-Conquer Algorithms
---------------------------------------

How do we normally analyze algorithms (informally)

* Identify all the loops
* Count the number of times each loop repeats
* Count the number of steps in each loop
* Multiply and add as appropriate

Will this strategy work for divide and conquer?

        define Quicksort(A)
          if (small(A))
            return
          else
            partition(A)
            Quicksort(firsthalf(A))
            Quicksort(secondhalf(A))

In general, we write equations to carefully specify the cost.
Merge sort

        define mergesort(A)
          if (oneelement(A))
            return
          merge(sort(firsthalf(A)),sort(secondhalf(A)))

        T(n) is supposed to be "bound on steps to sort an array
        of size n using mergesort"

        T(1) = 1
        T(n) = T(n/2) ; sort(firsthalf(A))
               + T(n/2) ; sort(secondhalf(A))
               + Theta(n) ; merge

As mathematicians, we'd like to find an exact bound for that
function.  (As computer scientists, we're okay with an extra
constant multiplier.)  How do we do so?

Estimating Recurrence Relations
-------------------------------

        T(n) <= 2*T(n/2) + c*n
        T(1) = 1

### Top-down expansion

* Repeatedly expand the right-hand side using the recurrence
  relation and look for a pattern.

        T(n) <= 2*T(n/2) + c*n
                ; T(n/2) <= 2*T(n/4) + c*n/2
             <= 2*(2*T(n/4) + c*n/2) + c*n
             =  4*T(n/4) + 2*c*n 
                ; T(n/4) <= 2*T(n/8) + c*n/4
             <= 4*(2*T(n/8) + c*n/4) + 2*c*n
             =  8*T(n/8) + cn + 2cn 
             =  8*T(n/8) + 3cn
                ; T(n/8) <= 2*T(n/16) + c*n/8
             <= 8*(2*T(n/16) + c*n/8) + 3cn
             =  16*T(n/16) + 4cn

Look at the main results

        T(n) <= 2*T(n/2) + c*n
             <= 4*T(n/4) + 2*c*n 
             <= 8*T(n/8) + 3cn
             <= 16*T(n/16) + 4cn
             <= 2^k*T(n/2^k) + k*c*n

Solve for 2^k = n; k = log_2(n)

            <= n*T(1) + log_2(n)*c*n
            <= 1 + c*n*log_2(n)

### Bottom-up expansion

* Build up from T(1) to T(2) to T(4) to T(8) to ....  And look
  for a pattern.

        T(1) = 1
        T(2) <= 2*T(1) + 2c = 2 + 2c
        T(4) <= 2*T(2) + 4c <= 2*(2 + 2c) + 4c <= 4 + 8c

Solving Recurrence Relations with Recursion Trees
-------------------------------------------------

        T(n) = 3*T(n/4) + Theta(n^2)
Proving Recurrence Relations with the Substitution Method
---------------------------------------------------------

Solving Recurrence Relations with the Master Theorem
----------------------------------------------------