ANNOUNCEMENTS: FINAL EXAM: DEC 12 at 1-4 p.m., Margaret Morrison A14 You can bring one 3x5 index card with notes on both sides. FINAL includes Chpts 8-14, plus parts of Chpt 15 and parts of Chpt 6. Final includes HW 8,9,10,11. Please review the HW problems carefully.

Midterm II is Oct 29 in class. Please arrive on time. You can bring one 3x5 index card with notes on both sides. Midterm II includes all of HW 5, 6, and 7. Topics included are: Normal Distribution, Central Limit Theorem, Laplace Transforms, Markov Inequality, Chebyshev Inequality, Chernoff Bound (lots on this), and Randomized Algorithms. Make sure to know Chpts 1,2,3 of the Randomized Algorithms notes well.

HOMEWORKS

FINAL EXAM: DEC 12 at 1-4 p.m., Margaret Morrison A14

ANTICIPATED LECTURE TOPICS

  • Part I: BASIC PROBABILITY

    • [Tues Aug 27] Introduction, Review of math prereqs: worksheet1 ; worksheet2 ; worksheet3 ; worksheet4 .
    • [Thurs Aug 29] Probability on events (Chpt 3)
    • [Fri Aug 30] Recitation: More review of math prereqs pdf
    • [Tues Sept 3] Discrete Random Variables, Expectation, Conditional Probability, Conditional Expectation (Chpt 3)
    • [Thurs Sept 5] Expectation via Conditioning, Linearity of Expectation, start Variance (Chpt 3)
    • [Fri Sept 6] Recitation: More practice with Conditional Expectation and Linearity of Expectation (Chpt 3) pdf
    • [Tues Sept 10] Variance; Higher Moments, Random Sums of Random Variables (Chpt 3)
    • [Thurs Sept 12] Z-transform (beginning of Chpt 25)
    • [Fri Sept 13] Recitation: Practice computing means, variances, transforms (Chpt 3 + beginning of Chpt 25) pdf
    • [Tues Sept 17] Continuous Random Variables (Chpt 3)
    • [Thurs Sept 19] Pareto distribution (Chpt 20 + Chpt 11.1 and 11.2)
    • [Fri Sept 20] Recitation: Generating Random Variables for Simulation (Chpt 4)
    • [Tues Sept 24] Normal distribution and Central Limit Theorem
    • [Thurs Sept 26] Laplace Transform
    • [Fri Sept 27] Recitation: Review for Midterm pdf
    • [Tues Oct 1] MIDTERM 1
  • Part II: RANDOMIZED ALGORITHMS

    • [Thurs Oct 3] Discussion of Midterm 1 solutions
    • [Fri Oct 4] No Recitation
    • [Tues Oct 8] Chernoff Bounds I
    • [Thurs Oct 10] Chernoff Bounds II
    • [Fri Oct 11] Recitation: Tricks to use with Chernoff Bounds pdf
    • [Tues Oct 15] Introduction to Randomized Algs -- Las Vegas algorithms: Quicksort, k-Select
    • [Thurs Oct 17] Introduction to Randomized Algs -- Monte Carlo algorithms: Polynomial Multiplication, Matrix Multiplication, Min-Cut
    • [Fri Oct 18] MID-SEMESTER BREAK (No Recitation)
    • [Tues Oct 22] Randomized Algs -- Hypercube routing, Streaming pdf
    • [Thurs Oct 24] Randomized Algs -- Primality Testing pdf
    • [Fri Oct 25] Recitation: Review pdf
    • [Tues Oct 29] MIDTERM 2
  • Part III: MARKOV CHAINS & QUEUES

    • [Thurs Oct 31] Discrete time Markov Chains (DTMCs) (Chpt 8)
    • [Fri Nov 1] Recitation: Discussion of Midterm 2 solutions
    • [Tues Nov 5] DTMC II (Chpt 8)
    • [Thurs Nov 7] DTMC III (Chpt 9)
    • [Fri Nov 8] Recitation
    • [Tues Nov 12] DTMC IV (Chpt 9)
    • [Thurs Nov 14] PageRank + Back to Exponential (Chpt 10)
    • [Fri Nov 15] Recitation
    • [Tues Nov 19] Poisson Process (Chpt 11)
    • [Thurs Nov 21] Continuous-time Markov chains (Chpt 12) + Little's Law (Chpt 6)
    • [Fri Nov 22] Recitation
    • [Tues Nov 26] M/M/1 + Scaling Examples + PASTA (Chpt 13)
    • [Thurs Nov 28] THANKSGIVING BREAK
    • [Fri Nov 29] THANKSGIVING BREAK
    • [Tues Dec 3] M/M/k + M/M/k/k (Chpt 14)
    • [Thurs Dec 5] Capacity Provisioning (Chpt 15)
    • [Fri Dec 6] Recitation: Review for final pdf