INSTRUCTOR: Varun Kanade (vkanade at eecs, 665 Soda)
OFFICE HOURS: Tuesday 2-3pm, Wednesday 5:30-6:30pm in 665 SODA

GSI: Richard Starfield (rstarfield at berkeley)
OFFICE HOURS: Mondays 4-5pm SODA 750, Tuesdays 4-5pm SODA 611

LECTURES: Tuesday, Thursday 09:30-11:00 in 310 SODA
101: Monday 3:00-4:00 in 71 EVANS


There will be two midterms and one final. The final is scheduled for December 11, 3-6pm. Tentative midterm dates are 10/16 and 11/13.


Your grade in the class will be determined as follows: Homeworks 20% (best 8 out of 10); Midterms 20% each; Final 40%.



The following is a list of topics covered in each lecture, together with pointers to the corresponding portions of the Mitzenmacher/Upfal text and, where appropriate, additional lecture notes.

The homework and midterm schedule may change slightly. In general homeworks will be posted on Tuesdays after class, and will be due on Thursday a week later (before class). Thus, you have 9 days for all homeworks.
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 (Will be posted)
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 (Tentative)
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 (Tentative)
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


Prerequisites: You should have taken an Upper Division course on algorithms (CS170 or equivalent) and a course on discrete mathematics including basic probability (CS70, Math55 or equivalent). If you found those classes hard, then you will find this course harder and you should consider carefully whether it is the right class for you. It is also assumed that you have experience with programming in a standard imperative language such as C, C++ or Java. Although most homeworks will be pencil-and-paper exercises, you may also be expected to do some small programming assignments. If you have any doubts about your background, you should come and talk to me as soon as possible.

Homework Policy: All homeworks are due Thursday at 9:30am unless otherwise stated. Submission of homeworks must be done electronically via bspace. Typing your solutions using a typesetting system such as Latex is strongly encouraged! If you must handwrite your solutions, write cleanly and legibly and scan your homework for submission. Please check that your scan quality is good. Messy and unreadable homeworks will not be graded. No late homeworks will be accepted.

Collaboration: You are encouraged to work on homework problems in study groups of two to four people; however, you must write up the solutions on your own, and you must never read or copy the solutions of other students. Similarly, you may use books or online resources to help solve homework problems, but you must credit all such sources in your writeup and you must never copy material verbatim.
Warning: Your attention is drawn to the Department's
Policy on Academic Dishonesty. In particular, you should be aware that copying solutions, in whole or in part, from other students in the class or any other source without acknowledgment constitutes cheating. Any student found to be cheating risks automatically failing the class and being referred to the Office of Student Conduct.

Regrading Policies: Regrading of homeworks or exams will only be undertaken in cases where you believe there has been a genuine error or misunderstanding. Bear in mind that our primary aim in grading is consistency, so that all students are treated the same; for this reason, we will not adjust the score of one student on an issue of partial credit unless the score allocated clearly deviates from the grading policy we adopted for that problem. If you wish to request a regrading of a homework or exam, you must return it to the instructor or the TA with a written note on a separate piece of paper explaining the problem. The entire assignment may be regraded, so be sure to check the solutions to confirm that your overall score will go up after regrading. All such requests must be received within one week from the date on which the homework or exam was made available for return.

Readings: The required text for the class is Probability and Computing: Randomized Algorithms and Probabilistic Analysis , by Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005. It is essential that all students have regular access to this book. Pointers to the relevant sections of the book will be provided as we go along. (See here for errata in the first and second printing of the book.)

Contact Information: The instructor and TA will post announcements, clarifications, hints, etc. to the Piazza Forum. Please sign up here. All important announcements will be posted to the course web-page and the Piazza forum. However, most discussions will be restricted to Piazza. Please set your notification preferences on Piazza accordingly.

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.


The following tips are offered based on our experience with Upper Division classes in CS Theory. If you follow these guidelines, you will make life much easier for yourself in this class.

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.