This is an old revision of the document!
Table of Contents
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