ANNOUNCEMENTS:
FINAL EXAM: DEC 12 at 14 p.m., Margaret Morrison A14
You can bring one 3x5 index card with notes on both sides.
FINAL includes Chpts 814, 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 14 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] Ztransform (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, kSelect
 [Thurs Oct 17] Introduction to Randomized Algs  Monte Carlo algorithms:
Polynomial Multiplication, Matrix Multiplication, MinCut
 [Fri Oct 18] MIDSEMESTER 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] Continuoustime 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