Held: Friday, 11 September 2015

Back to Outline 06 - Asyptotic Analysis and Recurrence Relations. On to Outline 08 - Roles of Data Structures and Abstract Data Types.

Summary

We pause to catch up on some important ideas that will better prepare us for the homework.

Related Pages

Overview

• Proving closed forms of recurrence relations.
• Finding the kth-largest element of an unsorted array/list.

Administrivia

• Friday PSA.

Upcoming Work

• For next Wednesday:
  • Part 1: Experimental Analysis
    • Look up the randomized nth-largest divide-and-conquer algorithm. (We may talk about it in class today.)
    • 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, Tuesday, Hacking Cars
• CS Extras, Wednesday, Jonathan Wellons '04 from Google

Peer

Proving Closed Forms of Recurrence Relations with Induction

• 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, subtleties best learned through practice.
• _Exercise: Prove that if T(n) = 2*T(n/2) + O(n) and T(n) = 1, then T(n) is in O(nlogn).

Randomized kth-Largest

• How do you find the kth largest element of an unsorted array (as quickly as possible)?
• Take about five minutes to brainstorm approaches.
• We'll then talk about techniques.