ANNOUNCEMENTS

First Page of Midterm II is here . The midterm is a little long, so look for the "easy" questions first, and don't spend too long on any one question. You can bring a 3"x5" index card with writing on one side. Midterm will start promptly at 1:30 p.m. I will give you until 3:00 p.m.

HOMEWORKS

ANTICIPATED LECTURE TOPICS

  • Part I: BASIC PROBABILITY

  • Part II: RANDOMIZED ALGORITHMS

    • [Wed Feb 25] Chernoff Bounds I -- See Chpt 1 Notes outside my office Examples from lecture
    • [Fri Feb 27] Recitation: Review of Midterm I
    • [Mon Mar 2] Chernoff Bounds II -- See Chpt 1 Notes outside my office
    • [Wed Mar 4] Introduction to Randomized Algs -- Las Vegas algorithms: Quicksort, k-Select -- See Chpt 2 Notes outside my office
    • [Fri Mar 6] NO CLASS: Mid-Semester Break
    • SPRING BREAK
    • [Mon Mar 16] Introduction to Randomized Algs -- Monte Carlo algorithms: Matrix Multiplication, Monomial Multiplication, Min-Cut -- See Chpt 3 Notes outside my office Examples from lecture
    • [Wed Mar 18] Advanced Randomized Algs -- Randomized Hashing (David) Notes
    • [Fri Mar 20] Recitation -- Random Graphs Sheet1 and Sheet2
    • [Mon Mar 23] Advanced Randomized Algs -- Randomized Geometry (Jakub) Notes
    • [Wed Mar 25] New topic: Discrete time Markov Chains (DTMCs) (Chpt 8) Examples from lecture
    • [Fri Mar 27] Recitation: Midterm 2 review Sheet1 and Sheet2
    • [Mon Mar 30] MIDTERM 2 EXTRA OFF HOURS: Sunday, Mar 29, 4 p.m. - 5 p.m., GHC 5th Floor Commons area
  • Part III: MARKOV CHAINS & QUEUES

    • [Wed Apr 1] DTMC II (Chpt 9) Examples from lecture and Mor's Number Theory Notes
    • [Fri Apr 3] Recitation
    • [Mon Apr 6] DTMC III (Chpt 9)
    • [Wed Apr 8] DTMC IV (Chpt 9)
    • [Fri Apr 10] Recitation Sheet1
    • [Mon Apr 13] PageRank + Back to Exponential (Chpt 10)
    • [Wed Apr 15] Poisson Process (Chpt 11) Examples from lecture
    • [Fri Apr 17] NO CLASS: Spring Carnival
    • [Mon Apr 20] Continuous-time Markov chains (Chpt 12) + Little's Law (Chpt 6)
    • [Wed Apr 22] M/M/1 + Scaling Examples + PASTA (Chpt 13)
    • [Fri Apr 24] Recitation Sheet1 and Sheet 2
    • [Mon Apr 27] M/M/k + M/M/k/k (Chpt 14)
    • [Wed Apr 29] Open Problems in Queueing Theory / Markov chains
    • [Fri May 1] Recitation: Review for final