Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Proving closed forms of recurrence relations.
• Finding the kth-largest element of an unsorted array/list.

Preliminaries

Admin

• Friday PSA.

Upcoming Work

• For next Wednesday: Homework 2
  • 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 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 Monday: No additional readings.

Extra Credit

Academic

• CS Table, Tuesday, Hacking Cars
• CS Extras, Wednesday, Jonathan Wellons '04 from Google

Peer

• DNP 11pm on KDIC.

Questions

Using assert

    #include <assert.h>

    main ()
    {
      assert(square(x) == x);
    }

Proving closed forms of recurrence relations

    T(n) = 2*T(n/2) + dn
    T(1) = 1

    Conclusion T(N) is in O(nlogn)

Let's prove it. What techniques do you know? induction, contradiction, strong induction, construction, prove the inverse of the contrapositive

Goal is to prove T(n) is in O(nlogn). We need to prove that there exist an n0 and a c s.t. for all n > n0 T(n) <= c*nlogn.

The (strong) inductive hypothesis says ...

With your group

• Figure out what the strong indicutive hypothesis says
• Use that to come up with c (and maybe n0)
• Have we forgotten anything?

Base case: Exists c s.t. T(1) <= c*1log1. Whoops. log(1) = 0. So ... Choose a different base case (or base cases)

Does there exist a c s.t. T(2) <= c*2log2

• T(2) = 2T(1) + 2d = 2 + 2d = (1+d)2 <= (1+d)2log2
• T(3) = 2T(3/2) + 3d =
  • When we write our recurrence relations, we should think about whether we mean floor or ceiling of n/2.
  • For merge sort T(n) <= T(floor(n/2)) + T(ceiling(n/2)) + dn
  • T(3) = T(1) + T(2) + 3d = 1 + 2 + 2d + 3d = ?3log3

Inductive hypothesis: For n > n0 T(n/2) <= c(n/2)*log(n/2)

General indicutive hypothesis. We are trying to prove CLAIM(n). We assume for all k < n, CLAIM(k) holds.

Inductive hypothesis: For n0 < k < n, T(k) <= cklogk

    T(n) = 2*T(n/2) + dn
    T(n) <= 2*c*n/2*log(n/2) + dn 
            ; because n/2 < n and 
            ; T(n/2) = c * n/2 * log(n/2)
    T(n) <= c*n*log(n/2) + dn
            ; Cancel the 2 and 1/2
    T(n) <= c*n*(log(n)+log(1/2)) + dn
            ; log(ab) = log(a) + log(b)
    T(n) <= c*n*(log(n)+log(2^-1)) + dn
    T(n) <= c*n*(log(n)-1) + dn
    T(n) <= c*n*log(n) - cn + dn
    T(n) <= c*n*log(n) + (d-c)n
            ; If c > d, (d-c)*n is negative
    T(n) <= c*n*log(n) + (d-c)n <= c*n*log(n)
    T(n) <= c*n*log(n) Q.E.D.

Revised hypothesis n0 and a c > d s.t. for all n > n0 T(n) <= c*nlogn.

Finding the kth-largest element of an unsorted array/list