===== Chapter 5 =====
Divide and conquer
  * analyzing involves a "recurrence relation" 

==== 5.1 A first Recurrence: The Mergesort Algorithm ====
  * We've seen mergesort before. Basic example for divide and conquer
  * divide the input into two pieces of equal size and solve the two subprobles with recursion. 
    * basically you continue to divide until you hit the base case. 
    * this should give a faster running time then other ways to solve. 
  * 5.1 - For some constant c, T(n) <= to 2T(n/2) + cn when n > 2 and T(2) <= c
    * this is what a the running time needs to satisfy for a recurrrence relation

Approaches to solving recurrences
  * natural way is to "unroll" the recursion. identify a pattern after looking at first few levels and go from there. 
  * Guess and check for a solution. 

Unrolling the mergesort solution
  * we did this in class
  * see page1 212 - 213
  * 5.2 T(n) will be bounded by O(nlogn) 

Subsituting into the mergesort recurrence - guess and check 
  * proof by induction that the running time is right

An approach using partial substitution
  * this seems less helpful. the book calls it weaker
  * but good if we don't know the exact constants. 

==== 5.2 Further Recurrence Relations ====

5.3 T(n) <= qT(n/2) + cn, when n > 2 and t(2) <= c. q is not the number subproblems

What to do with q>2 subproblems
  * analyze the first few levels. 
  * identify a patterns. at abitrary level j we have qq^j distinct instances each of size (n/2^j) 
  * See diagram on page 216
  * sum over all levels of recursion. 
  * end up with O(n^(log2(q))) (because of geometric series etc. (5.4)
  * can also apply partial substitution - to derive the answer above. (I like unrolling, but see page 217 if need review) 

What happens when q = 1
  * well you keep solving half a problem so the work per level is decreasing
  * only one instance at each level 
  * when we sum over we get linear order. (5.5)

Related recurrence
  * looking at a recurrence relation of T(n) <= 2T(n/2) + O(n^2)
  * same process for Unrolling the recurssion. Can analyze, identify and sum. 

==== 5.3 Counting inversions ====
The problem
  * rankings (netflix suggestions, amazon suggestions etc.) 
  * measure ranking by counting the number of inversions between your ranking and comp generated one. 

The algorithm
  * can find an O(nlogn) solution
  * uses a merge and count and sort and count algorithm
  * see the algorithm on page 224. did a lot with this in class. makes sense. 

==== 5.4 Finding the closest pair of points ====
  * in class this is where my mind was "blown" 
  * the problem is how to find the closets points in a set of points
  * divide the points into sections and then find min, in each section and around the dividing line. 
  * first find the mind of your different sections. compare each of those and set delta = to the min of the mins
  * THE TRICK is setting up the boxes around the line that are of size delta/2 by delta/2 therefore you only have to check the point and it's seven neighboring boxes. 
  * really reduces the number of checks

==== 5.5 interger multiplication====
The Problem
  * want to reduce our running times from o(n^2) to something slightly lower using recursion for example O(n^log2(q)) (saw that before!)
  * see algorithm on 233
  * we get O(n^log2(3))