Topic | Readings | |
08/23 | Introduction; basic probability, polynomial identity testing |
MU Sections 1.1-1.2 |
08/28 | Verifying matrix multiplication, Randomized min-cut algorithm Homework 1 posted In order to encourage you to use latex -- here is the latex code and the math macros. |
MU Sections 1.3-1.4 |
08/30 | Complete randomized min-cut. Improved running time for min-cut 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.1-2.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.4-2.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.1-3.3
|
09/13 | Complete Chebychev's inequality, Randomized Mean Finding Homework 2 due by 9:30am |
MU Sections 3.3-3.4
|
09/18 | Complete Mean Finding, Chernoff Bounds Homework 2 solutions posted Homework 4 posted Tex File Updated macros |
MU Sections 3.4, 4.1-4.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.1-5.3 |
09/25 | Balls and Bins, Poisson Approximation, Hashing Homework 5 posted Tex File Homework 3 Solutions |
MU Sections 5.4-5.5 |
09/27 | Balls and Bins -- maximum load, Random Graph Models Homework 4 due by 9:30am |
MU Sections 5.4-5.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.1-2
|
10/04 | Probabilistic Method -- de-randomization, second moment method Homework 5 due by 9:30am |
MU Sections 6.3-6.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.5-6.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 k-SAT |
MU Sections 6.7-6.8
|
10/23 | Markov Chains, 2-SAT algorithm Homework 8 posted Tex File |
MU Sections 7.1-7.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.2-7.4
|
11/01 | Markov Chains -- random walks on undirected graphs, cover time
Homework 8 due by 9:30am |
MU Sections 7.3-7.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 : 9-11am ( Homework 10 posted |
|
11/15 | Pattern Matching (see notes posted on 11/08) Repeated n-decision games HW10 posted [Tex file] (due 11/29 -- 2 weeks) |
Lecture notes on online learning
|
11/20 | Repeated n-decision games, Weighted Majority Algorithm |
|
11/22 | No Class - Thanksgiving Break
|
|
11/27 | Multi-armed 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.