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), CIT 319, Hours by appointment
Lecture Place and Hours: CIT 368, Tue,Thu, 2.30pm — 3.50pm
Note: Office hours begin after the first homework comes out, and they are all in different locations!
Grad TA: Lorenzo De Stefani (lorenzo <AT> cs . brown . edu). Office Hours: Tuesday 12:15pm — 2:15pm, CIT 321
Head TA: Sorin Vatasoiu (svatasoi <AT> cs . brown . edu). Office Hours: Monday 6-8pm, CIT 207
Email the course staff: cs1550tas <AT> lists . brown . edu
Class Email: Don't forget to subscribe to the course mailing list firstname.lastname@example.org
20% midterm (a non-collaborative homework set).
40% take home final.
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, 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: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal.
Errata for the 1st Printing, Errata for the 2nd Printing
Last Updated: Jan 26th 2017