Chapter 5

• 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

• 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

• 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.

• 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.

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

• 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)

• 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