HOMEWORKS

ANTICIPATED LECTURE TOPICS

  • Part I: BASIC PROBABILITY

    • [Mon Jan 12] Introduction, Review of math prereqs. Memorize these!
    • [Wed Jan 14] Probability on events (Sec 3.1 to 3.6 of book) Examples from lecture
    • [Fri Jan 16] Recitation: More review of math prereqs Sheet1 and Sheet2
    • [Mon Jan 19] NO CLASS -- MLK Day
    • [Wed Jan 21] Discrete Random Variables, Expectation, Conditional Probability, Conditional Expectation (Sec 3.6 to 3.11 of book, but only the "Discrete" case). Examples from lecture
    • [Fri Jan 23] Recitation: More conditioning practice Sheet1 and Sheet2
    • [Mon Jan 26] Expectation via Conditioning, Linearity of Expectation, start Variance (Sec 3.12 to 3.13 of book, but only "Discrete" case) Examples from lecture and Quiz
    • [Wed Jan 28] Variance; Higher Moments, Random Sums of Random Variables (Sec 3.9, 3.13, 3.15 of book, but only "Discrete" case), starting Z-transforms Examples from lecture
    • [Fri Jan 30] Recitation: More on linearity of expectations and variance Sheet1 and Sheet2
    • [Mon Feb 2] Z-transform (beginning of Chpt 25), starting Continuous Random Variables (Sec 3.8.2)
    • [Wed Feb 4] Continuous Random Variables (Chpt 3.8.2 to 3.13, but only "Continous" case)
    • [Fri Feb 6] Recitation -- more Continuous examples
    • [Mon Feb 9] Pareto distribution (Chpt 20 + Chpt 11.1 and 11.2)
    • [Wed Feb 11] Normal distribution and Central Limit Theorem (Sec 3.14)
    • [Fri Feb 13] Recitation
    • [Mon Feb 16] Generating Random Variables for Simulation (Chpt 4)
    • [Wed Feb 18] Laplace Transform
    • [Fri Feb 20] Recitation -- Review for Exam
    • [Mon Feb 23] MIDTERM 1
  • Part II: RANDOMIZED ALGORITHMS

    • [Wed Feb 25] Chernoff Bounds I
    • [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