Topic  Readings  
08/23  Introduction; basic probability, polynomial identity testing 
MU Sections 1.11.2 
08/28  Verifying matrix multiplication, Randomized mincut algorithm Homework 1 posted In order to encourage you to use latex  here is the latex code and the math macros. 
MU Sections 1.31.4 
08/30  Complete randomized mincut. Improved running time for mincut algorithm. 
MU Sections 1.4 + Lecture Notes ( 
09/04  Random variables, expectation, variance, Jensen's inequality. Bernoulli and Binomial random variables. Conditional Expectation. Homework 2 posted HW2 Latex Code 
MU Sections 2.12.3

09/06  Geometric Random Variables, Coupon Collector Problem Randomized Quicksort and Probabilistic Analysis of Deterministic Quicksort Homework 1 due by 9:30am 
MU Sections 2.42.5

09/11  Calculating mean privately, Markov's inequality Variance, Standard Deviation, Chebychev's inequality Homework 1 solutions posted Homework 3 posted Tex File Updated Macros(without this HW3.tex won't compile!) 
MU Sections 3.13.3

09/13  Complete Chebychev's inequality, Randomized Mean Finding Homework 2 due by 9:30am 
MU Sections 3.33.4

09/18  Complete Mean Finding, Chernoff Bounds Homework 2 solutions posted Homework 4 posted Tex File Updated macros 
MU Sections 3.4, 4.14.4

09/20  Some properties of random permutations Balls in Bins, Birthday Paradox Homework 3 due by 9:30am 
Notes (from previous years on random
permutations) MU Sections 5.15.3 
09/25  Balls and Bins, Poisson Approximation, Hashing Homework 5 posted Tex File Homework 3 Solutions 
MU Sections 5.45.5 
09/27  Balls and Bins  maximum load, Random Graph Models Homework 4 due by 9:30am 
MU Sections 5.45.6

10/02  Random Graph Properties, Introduction to Probabilistic Method Homework 6 posted Tex File Homework 4 Solutions Practice Midterm (Fall 2011) 
MU Sections 5.6, 6.12

10/04  Probabilistic Method  derandomization, second moment method Homework 5 due by 9:30am 
MU Sections 6.36.4 
10/09  Probabilistic Method  second moment method, method of conditional moment,
Lovasz local lemma Homework 5 Solutions posted No homework  prepare for midterm 
MU Sections 6.56.7

10/11  Revision for Midterm Homework 6 due by 9:30am 

10/16  Midterm 1 ( Homework 6 solutions posted Homework 7 posted Tex File 

10/18  Finish Lovasz Local Lemma; Application to kSAT 
MU Sections 6.76.8

10/23  Markov Chains, 2SAT algorithm Homework 8 posted Tex File 
MU Sections 7.17.2

10/25  Discussion of Midterm 1. Markov Chains. Homework 7 due by 9:30am 
MU Sections 7.2

10/30  Markov Chains  stationary distributions. Random walks. Homework 9 posted Tex File Homework 7 Solutions Midterm 2 (Fall 2011) 
MU Sections 7.27.4

11/01  Markov Chains  random walks on undirected graphs, cover time
Homework 8 due by 9:30am 
MU Sections 7.37.4

11/06  Monte Carlo Techniques Solutions to Homework 8 No homework this week  prepare for midterm 
MU Chapter 10

11/08  Markov Chain Monte Carlo Fingerprinting and Pattern Matching Homework 9 due by 9:30am Homework 9 Solutions 
MU Chapter 10 and Notes on Fingerprinting

11/13  Midterm 2 : 911am ( Homework 10 posted 

11/15  Pattern Matching (see notes posted on 11/08) Repeated ndecision games HW10 posted [Tex file] (due 11/29  2 weeks) 
Lecture notes on online learning

11/20  Repeated ndecision games, Weighted Majority Algorithm 

11/22  No Class  Thanksgiving Break


11/27  Multiarmed bandits 

11/29  Primality Testing Homework 10 due by 9:30am 
Lecture notes on primality testing. 
12/04  Reading Period


12/06  Reading Period


If you have a straightforward clarification question, your best option is to post a message to Piazza. There is a good chance that this will be answered by your classmates or the TA or the instructor, very quickly. Please do not post any solutions or obvious hints to the homework questions on Piazza.
If your question is personal you should send a private message to the instructor or TA through Piazza. Please use email as a last resort. Please only send emails regarding questions that cannot be satisfactorily handled in office hours or on Piazza. Please allow either the TA or the instructor at least 48 hours for an email response.
In any class, it can be challenging for the instructor to
gauge how smoothly the class is going. We always welcome any feedback
on what we could be doing better. If you would like to send anonymous
comments or criticisms, please feel free to use an anonymous emailer
like this
one to avoid revealing your identity.
1. Don't fall behind! In a conceptual class such as this, it is particularly important to maintain a steady effort throughout the semester, rather than hope to cram just before homework deadlines or exams. This is because it takes time and practice for the ideas to sink in. Make sure you allocate a sufficient number of hours every week to the class, including enough time for reading and understanding the material as well as for doing assignments. (As a rough guide, you should expect to do at least one hour of reading and two hours of problem solving for each hour of lecture.) Even though this class does not have any major projects, you should plan to spend as much time on it as on any of your other Upper Division technical classes.
2. Take the homeworks seriously! The homeworks are explicitly designed to help you to learn the material as you go along. Although the numerical weight of the homeworks is not huge, there is usually a strong correlation between homework scores and final grades in the class. Also, regardless of how well you did on the homework, read the sample solutions, even for the problems you got right. You may well learn a different way of looking at the problem, and you may also benefit from emulating the style of the solutions. (In science people learn a lot from emulating the approach of more experienced scientists.)
3. Make use of office hours! The instructor and TA hold office hours expressly to help you. It is often surprising how many students do not take advantage of this service. You are free to attend as many office hours as you wish. You will also likely get more out of an office hour if you have spent a little time in advance thinking about the questions you have, and formulating them precisely. (In fact, this process can often lead you to a solution yourself!)
4. Take part in discussion sections! Discussion sections are not auxiliary lectures. They are an opportunity for interactive learning, through guided group problem solving and other activities. The success of a discussion section depends largely on the willingness of students to participate actively in it. As with office hours, the better prepared you are for the discussion, the more you are likely to get out of it.
5. Form study groups! As stated above, you are encouraged to form small groups (two to four people) to work together on homeworks and on understanding the class material on a regular basis. In addition to being fun, this can save you a lot of time by generating ideas quickly and preventing you from getting hung up on some point or other. Of course, it is your responsibility to ensure that you contribute actively to the group; passive listening will likely not help you much. And recall the caveat above that you must write up your solutions on your own.