- An Upper Division course on algorithms (CS170 or equivalent)
- A course on discrete mathematics including basic probability (CS70, Math55, or equivalent)
The course may be of interest to graduate students from EECS, IEOR, Mathematics and the Statistics departments. Graduate students are welcome to consult the instructor prior to enrolling in the course.
This course will provide familiarity with basic tools in discrete probability and their applications to the design and analysis of randomized algorithms and data structures. You will learn how probabilistic ideas and techniques can lead to more efficient and conceptually simpler algorithms for many problems.
- A selection of topics from the text, in particular most of chapters 1-7 and additional topics from other chapters
- Probability and Computing: Randomized Algorithms and Probabilistic
Analysis, by Michael Mitzenmacher and Eli Upfal, Cambridge University
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 printing of the book, some of which were corrected in the second printing.)
- Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005.
- 20% Problem Sets (The lowest two problem set scores will be dropped)
- 40% Two Midterms (20% each)
- 40% Final Exam (Thursday, December 15, 2011, 11:30-2:30PM)
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.
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. For each homework you must write your group member names and SID. 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.
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.
This course webpage is based on an earlier version by Y. Song.