====== Chapter 5 ======

===== 5.1: A First Recurrence: The Mergesort Algorithm =====
   *Mergesort is a great example of divide and conquer.
   *To quote Professor Stough: "Sorting is hard, so don't do it. Just merge"
     * From the book:
       * Divide the input into two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending only linear time for the initial division and final recombining.
   * All recursion needs a base case where it "bottoms out"
   * Two ways to solve recurrence:
     * "Unroll" the recursion
     * Start with a guess for the solution and keep substituting into the recurrence relation
   * Examples of those two methods being used to solve mergesort can be found on pages 212-214

===== 5.2: Further Recurrence Relations =====
   *Following are different cases with grouped by the amount of subproblems:
     *pages 215-221 cover the following different cases:
       * q>2 subproblems
       * q = 1 subproblem
       * q = 2 subproblems

===== 5.3: Counting Inversions =====
   *This subchapter onward covers different applications of divide and conquer
   *The problem covered first is the analysis of rankings(like google pagerank)
   *Most web sites use collaborative filtering, in which they try to match your preferences with those of other people on the internet
   *5.3 Covers the design and analysis of an algorithm whose purpose is to optimally perform collaborative filtering. 

===== 5.4: Finding the Closest Pair of Points =====
   *Here we have the most recent problem covered in class and probably the one I understand the best
   *The problem is: given n points on a plane find the pair that is closest together
   *The most immediately apparent brute force solution is to take these points and simply go through each pairing to see which points are closest together. 
   *There is, however, an O(nlogn) solution covered in this chapter using divide and conquer. 

===== Final Thoughts =====
This chapter is probably my weakest chapter so far and, as a result, I am not as able to adequately put this chapter into my own words based on my knowledge from class discussions and my reading of the chapter. That being said, I should take this as a sign that I need to see Prof. Sprenkle this afternoon for help on this difficult subject. Readability: 5/10

===== 5.5: Integer Multiplication =====
   * Using divide and conquer to multiply integers:
     * This chapter seeks to improve on the basic integer multiplication algorithm (currently n^2)
     * Divide into n/2 bits using 3 recursive calls. 
       * O(n^1.59)

===== 5.6: Convolutions and the Fast Fourier Transform =====
   * Basic recurrence in the design of the Fast Fourier Transform:
     * Deals with combining vectors. Used in signal processing. 
     * Design and analysis of this algorithm using recurrence can be found on pages 238 - 242