Divide and conquer

• analyzing involves a “recurrence relation”

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

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.

• 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

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