Course Information
Instructor: Saray Shai, sshai [at] wesleyan.edu, Exley 643.
Meetings: Mon, Wed 1:20 – 2:40pm in Exley Science Center 139.
Office Hours: Wed 3 – 4:30 p.m., Fri 1:30 – 3 p.m.
Prerequisites : COMP 211, COMP 212, and MATH 228
Exams: Midterm: Oct 18 1:20 – 2:40 p.m., Final: Dec 15, 2 – 5 p.m.
Course Overview
Randomization and probabilistic techniques have become fundamental tools in modern computer science, with applications ranging from network security, cryptography and communication protocols to web search, machine learning and data analysis. Randomized algorithms, which make random choices during their execution, are typically faster, simpler, and easier to implement compared to purely deterministic algorithms. Together with the increased availability of massive (aka BIG) data sets, such as the World Wide Web, social networks and genome data, randomized algorithms are receiving much attention as an effective tool to tackle the complexity and high-dimensionality arising in data analysis problems.
The purpose of this course is to introduce the underlying probability theory and rigorous techniques used in the design and analysis of randomized algorithms. As such, the emphasis is on probabilistic techniques and paradigms rather than any specific application. However, we will see various applications throughout the course and try to maintain a healthy balance between theory and applications. By the end of the course, we expect you to:
Have a firm grasp of basic probability theory and concentration bounds
Conduct probabilistic analysis of deterministic algorithms
Analyze the correctness and complexity of randomized algorithms
Design and implement randomized algorithms
Reading Material
Most of the course content will follow, or at least be strongly informed from the book Probability and Computing by Mitzenmacher and Upfal. Occasionally I will also borrow some material from Upfal's lecture notes and from O'Donnell’s lecture notes for their courses on probability and computing at Brown University and Carnegie Mellon University respectively.
Another two great books for this course are:
Randomized Algorithms by Motwani and Raghavan
The Probabilistic Method by Alon and Spencer
Assessment
We will have weekly homework assignments posted on the course website (to be submitted either in class or through the website). Most of the problems will require proofs, sometimes pseudo code, and we might have a few small programming assignments (that can be done in your favorite programming language among Python, C/C++, Java, R. If you prefer another language, please come and talk to me about it).
You are free and highly encouraged to discuss these problems with other students to get a general idea of how to solve them but you must write out your own solutions. Please make every effort to turn in papers that are neat and written so as to be coherent and easily
readable, not your first drafts with scribbles and scratch-outs.
You are allowed two late homework submissions (up to 24 hours after the deadline), but other than that no late submissions will be accepted (unless a special permission was given from the instructor).
We will also have an in-class midterm (Wed, Oct 18) and a final exam (Friday, Dec 15).
Your grade will be based on homework assignments (45%), a midterm exam (25%), and a final exam (30%).
Assignment 1 (Due Sep 11, beginning of class)
Attendance
While attendance is not required, it is strongly encouraged as the lectures will be your primary source of information for the course. Please come to class prepared to learn! You should try to contribute to the class discussion and discuss the course material regularly with other students.
Honor Code
All students are expected to be familiar with, and to comply with, the Wesleyan Honor Code. You may (and probably should) work together on homework and when preparing for exams, but homework papers should be written up by each individual alone and should properly credit any sources used. Exams will be closed book individual efforts.
Disability Accommodation
Wesleyan University is committed to ensuring that all qualified students with disabilities are afforded an equal opportunity to participate in and benefit from its programs and services. To receive accommodations, a student must have a documented disability as defined by Section 504 of the Rehabilitation Act of 1973 and the ADA Amendments Act of 2008, and provide documentation of the disability. Since accommodations may require early planning and generally are not provided retroactively, please contact Accessibility Services as soon as possible. If you believe that you need accommodations for a disability, please contact Accessibility Services, located in North College, rooms 021/022, or call 860-685-5581 to arrange an appointment to discuss your needs and the process for requesting accommodations.