Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Recursion trees, revisited.
• Proving asymptotic bounds of recursive functions.
• The master theorem.
• The kth-largest problem. (Maybe)

Preliminaries

Admin

• Picnic signup!
• Homework due!
• Would you like a Slack channel for this class?
• Handout!

Upcoming Work

• For next Wednesday:
  • Part 1: Experimental Analysis
    • Look up the randomized kth-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 its 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

• Convo, Thursday, 11am, JRC 101.
• CS Extras, Thursday, System Administration
• CS Table, Tuesday, Hacking Cars

Peer

• CS Extra, Thursday

Questions

Recursion trees, revisited

Proving asymptotic bounds of recursive functions

The master theorem

The kth-largest problem