CSC301.01 2015F, Class 06: Asyptotic Analysis and Recurrence Relations
======================================================================

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