ANNOUNCEMENTS
Final exam: Friday, May 8, at 8:30 a.m.  11:30 a.m.  Doherty Hall (DH) A302.
You can bring a 3"x5" index card with writing on one side. The exam is designed to take 1.5 hours. Exam will cover all of Part 3 of the course, but will assume knowledge of basic probability and transforms. I recommend studying HW 10,11,12,13.
Your graded HW 13's will be in the bins by Wednesday afternoon.
HOMEWORKS
 Here is an OPTIONAL Latex Template template . I expect that most of you will just hand write your homeworks. Please turn in your homework during recitation. For all homeworks, please turn in problems 14 in one batch and the remaining problems in a second batch. This makes it easier for us to grade your homework. Thank you!
 Homework 1  DUE FRIDAY, JAN 23
 Homework 2  DUE FRIDAY, JAN 30
 Homework 3  DUE FRIDAY, FEB 6
 Homework 4  DUE FRIDAY, FEB 13
 Homework 5  DUE FRIDAY, FEB 20 No late days!
 Homework 6  DUE FRIDAY, FEB 27
 Homework 7  DUE THURSDAY, MAR 5, MIDNIGHT
 Homework 8  DUE FRIDAY, MAR 20
 Homework 9  DUE FRIDAY, MAR 27 No late days!
Some Hints for HW 9!
 Homework 10  DUE FRIDAY, APR 3
 Homework 11  DUE MONDAY, APR 13, Start of class
 Homework 12  DUE WEDNESDAY, APR 22, Start of class
 Homework 13  DUE FRIDAY, MAY 1, Recitation
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 Ztransforms
Examples from lecture
 [Fri Jan 30] Recitation: More on linearity of expectations and variance
Sheet1 and
Sheet2
 [Mon Feb 2] Ztransform (beginning of Chpt 25), starting Continuous Random Variables (Sec 3.8.2)
Examples from lecture and
Quiz
 [Wed Feb 4] Continuous Random Variables (Chpt 3.8.2 to 3.13, but only "Continous" case)
 [Fri Feb 6] Recitation  more Continuous examples
Sheet1 and
Sheet2
 [Mon Feb 9] Pareto distribution (Chpt 20 + Chpt 11.1 and 11.2)
Examples from lecture and
Quiz
 [Wed Feb 11] Normal distribution and Central Limit Theorem (Sec 3.14)
Examples from lecture
 [Fri Feb 13] Recitation  Normal, Pareto, and Exponential
Sheet1 and
Sheet2
 [Mon Feb 16] Laplace Transform (Chpt 25)
Examples from lecture
 [Wed Feb 18] Generating Random Variables for Simulation (Chpt 4)
Examples from lecture
 [Fri Feb 20] Recitation  Review for Exam
Sheet1 and
Sheet2
 [Mon Feb 23] MIDTERM 1
EXTRA OFF HOURS: Sunday, Feb 22, 4 p.m.  5:30 p.m., GHC 7207  Mor's Office.

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, kSelect  See Chpt 2 Notes outside my office
 [Fri Mar 6] NO CLASS: MidSemester Break
 SPRING BREAK
 [Mon Mar 16] Introduction to Randomized Algs  Monte Carlo algorithms:
Matrix Multiplication, Monomial Multiplication, MinCut  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] Continuoustime 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