Probability, randomness, and statistics play a key role in modern computer science. From the highly theoretical notion of probabilistic theorem proving to the very practical applications of cryptography and web search ranking, sophisticated probabilistic techniques have been developed in the last two decades for a broad range of challenging computing applications.
This course introduces the basic probabilistic techniques used in the design of randomized algorithms and in probabilistic analysis of algorithms. The course covers the basic probability theory required for working with these techniques and demonstrates their use in various computing applications.
Instructor: Eli Upfal (eli <AT> cs . brown . edu). Hours: Thursday 4pm - 5pm (CIT 319)
Lecture Place and Hours: Tuesday and Thursday 2:30pm - 3:50pm (CIT 368)
Grad TA: Cyrus Cousins (ccousins <AT> cs . brown . edu). Hours: Tuesday 1pm - 3pm (CIT 321)
Head TA: Michael Nisenzon (mnisenzo <AT> cs . brown . edu). Hours: Wednesday 4pm - 6pm (CIT 269)
TA: George Wangensteen (gwangens <AT> cs . brown . edu). Hours: Monday 6pm - 8pm (CIT 269)
Email the course staff: cs1550tas <AT> lists . brown . edu
30% homework, where the best six homeworks are counted.
30% take-home midterm (a non-collaborative problem set)
40% take-home final (a non-collaborative problem set)
The final will replace a lower homework and/or midterm score.
Problem sets (except the midterm and final) are collaborative. You may discuss the problems with other students to get a general idea of how to solve them. However, you may not take away written notes about the problems from such discussions, and the answers you turn in must be your own, not written in a group.
Total time spent in and out of class for this course is estimated at ~180 hours. Students will spend 3 hours in class each week (a total of 39 hours). Although specific out-of-class time investments may vary for individual students, a reasonable estimate to support this course's learning outcomes is 140-150 total out-of class hours, or on average, 10 hours weekly over a 13-week term, in reviewing class material and answering the weekly problem sets, and 10-20 hours working on the take-home final.
If you feel you have physical, psychological, or learning disabilities that could affect your performance in the course, we urge you to contact SEAS. We will do whatever we can to support accommodations recommended by SEAS.
The textbook for the course is Probability and Computing Randomization and Probabilistic Techniques in Algorithms and Data Analysis, 2nd Edition by Michael Mitzenmacher and Eli Upfal.
Errata for the 1st Printing, Errata for the 2nd Printing
Last Updated: Jan 2019