Held: Wednesday, 9 September 2015

Back to Outline 05 - Divide and Conquer Approaches. On to Outline 07 - Pause for Breath.

Summary

We consider proofs related to recurrence relations, and therefore to divide-and-conquer algorithms.

Related Pages

Overview

• Recursion trees, revisited.
• Proving asymptotic bounds of recursive functions.
• The master theorem.
• The kth-largest problem.

Administrivia

• Picnic signup!
• Homework due!

Upcoming Work

• For next Wednesday:
  • Part 1: Experimental Analysis
    • Look up the randomized nth-largest divide-and-conquer algorithm.
    • Implement it in C.
    • Write unit tests using assert.
    • Write a program that does lots of repeated tests to evaluate it's running time.
  • Part 2: Proof
    • Find bounds for each of the following using the master theorem.
      • a. T(n) <= 3T(n/3) + O(n^2).
      • b. T(n) <= 3T(n/3) + O(n).
      • c. T(n) <= 3T(n/3) + O(1).
      • d. T(n) <= 3T(n/5) + O(n^2).
      • e. T(n) <= 3T(n/5) + O(n).
      • f. T(n) <= 3T(n/5) + O(1).
      • g. T(n) <= 9T(n/3) + O(n^2).
      • h. T(n) <= 9T(n/3) + O(n).
      • i. T(n) <= 9T(n/3) + O(1).
      • j. T(n) <= T(2n/3) + O(n^2).
      • k. T(n) <= T(2n/3) + O(n).
      • l. T(n) <= T(2n/3) + O(1).
    • Prove the bounds of a-c using induction.
• For Friday: No additional readings.

Extra Credit

Academic

• CS Table, Tuesdays, Hacking Cars
• CS Extras, Thursday, System Administration
• Convo, Thursday, 11am.

Peer

Recursion Trees, Revisited

• It sometimes helps to draw a tree that shows what's happening with the recursion.
• We show the size of the problem at each level.
• We can sum across each level, and then sum those sums to get an overall estimate of the running time.
• This analysis requires that we identify the sum of the values at each level and the number of levels.
• Exercise: Build the recursion tree for T(n) = 2*T(n/2) + cn.
• Exercise: Build the recursion tree for T(n) = 2*T(n/2) + c.

Solving Recurrence Relations with the Substitution Method

• Basically, this is proof by induction.
• We'll assume that the recurrence relation holds for values smaller than n and then prove it for n.
• Unfortunately, it turns out that there are a lot of subtleties with this technique.
• _Exercise: Prove that if T(n) = 2*T(n/2) + O(n) and T(n) = 1, then T(n) is in O(nlogn).

Solving Recurrence Relations with the Master Theorem

• The master theorem works for recurrences of the form T(n) = aT(n/b)+f(n).
• The computation depends on the relationship between f(n) and how quickly the n/b drops to 0.
• There are three rules
  1. If f(n) is in O(n^(log_b(a)-e)) for some e > 0, then T(n) is in Theta(n^(log_b(a)))
  2. If f(n) is in Theta(n^log_b(a)), then T(n) is in Theta(n^(log_b(a)*log n))
  3. If f(n) is in Omega(n^(log_b(a)+e))_ for some e > 0, and af(n/b) <= cf(n) for some c < 1 and large enough n, then T(n) is in Theta(f(n)).
• There's a simpler version (which I'm taking from Weiss). This is for recurrences of the form T(n) = aT(n/b) + O(n^k)
• There are once again three rules
  1. If a > b^k, then T(n) is in O(n^(logb(a)))
  2. If a = b^k, then T(n) is in O(n^klog2(n))
  3. If a < b^k, then T(n) is in O(n^k)
• We'll try some basic examples.

Randomized kth-Largest

If there's time, we'll go over this.