<< Home

Course Description

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.

Syllabus

• Weeks 1-3: Review of discrete probability spaces
  • Events, Expectation, Variance, Chebyshev Inequality
  • Simple randomized algorithms analysis (polynomial identity, min-cut algorithm, median algorithm)
  • Naïve Bayesian classifier
• Week 3-4: Basic concentration bounds (Chernoff and Hoeffding)
  • Applications: Set balancing, network packet routing, …
• Week 5: The occupancy problem
  • Hashing and random graphs
• Week 6: The Probabilistic Method – explicit constructions
• Week 7: Martingales and concentration bounds
• Week 8 - 10: Foundations of Machine Learning – Sample Complexity
  • PAC learning
  • VC-dimension
  • Rademacher complexity
• Week 11: Markov Chains and the Monte Carlo method
• Week 12-13: Rapidly mixing chains and the coupling method

Course Information

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 cs1550student@lists.brown.edu

Syllabus

Grading

• 40% homework

• 20% midterm (a non-collaborative homework set).

• 40% take home final.

Collaboration policy

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.

Time Requirements

​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.

Accommodations

​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.

Textbook

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