HOMEWORKS

ANTICIPATED LECTURE TOPICS

  • Part I: BASIC PROBABILITY

  • Part II: RANDOMIZED ALGORITHMS

    • [Wed Feb 25] Chernoff Bounds I Examples from lecture
    • [Fri Feb 27] Recitation: Review of Midterm I
    • [Mon Mar 2] Chernoff Bounds II
    • [Wed Mar 4] Introduction to Randomized Algs -- Las Vegas algorithms: Quicksort, k-Select
    • [Fri Mar 6] NO CLASS: Mid-Semester Break
    • SPRING BREAK
    • [Mon Mar 16] Introduction to Randomized Algs -- Monte Carlo algorithms: Polynomial Multiplication, Matrix Multiplication, Min-Cut
    • [Wed Mar 18] Advanced Randomized Algs -- Hypercube routing, Streaming
    • [Fri Mar 20] Recitation
    • [Mon Mar 23] Advanced Randomized Algs -- Primality Testing
    • [Wed Mar 25] MIDTERM II
    • [Fri Mar 27] Recitation: Discussion of Midterm 2 solutions
  • Part III: MARKOV CHAINS & QUEUES

    • [Mon Mar 30] Discrete time Markov Chains (DTMCs) (Chpt 8)
    • [Wed Apr 1] DTMC II (Chpt 8)
    • [Fri Apr 3] Recitation
    • [Mon Apr 6] DTMC III (Chpt 9)
    • [Wed Apr 8] DTMC IV (Chpt 9)
    • [Fri Apr 10] Recitation
    • [Mon Apr 13] PageRank + Back to Exponential (Chpt 10)
    • [Wed Apr 15] Poisson Process (Chpt 11)
    • [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
    • [Mon Apr 27] M/M/k + M/M/k/k (Chpt 14)
    • [Wed Apr 29] Capacity Provisioning (Chpt 15)
    • [Fri May 1] Recitation: Review for final