Fall 2013
Unique Number 54115
CS 388R
Randomized Algorithms

Instructor Greg Plaxton (email: plaxton at cs); office hours MTh 3-4 in GDC 4.512
Teaching Assistant Chunzhi Su (email: suchunzhi at gmail dot com); office hours T 11-12 and F 1-2 in GDC 6.440
Class Time MW 9:30-11
Class Location GDC 6.202
Textbook The textbook for the course is Randomized Algorithms by Motwani and Raghavan (Cambridge University Press, 1995).
Course Outline The following major topics will be covered: moments and deviations; randomized graph algorithms; Chernoff bounds and their applications; randomized data structures; hashing; martingales; the probabilistic method; Markov chains and random walks; randomized parallel and distributed algorithms; randomized online algorithms. See the schedule for a more detailed specification of the lecture plan.
Prerequisites Graduate standing and either an undergraduate algorithms course (such as CS 331 or CS 357) or consent of instructor.
Recommended Exercises Six sets of recommended exercises will be handed out during the semester. The tentative dates for these handouts are indicated on the class schedule. Sample solutions will also be handed out. It is suggested that students attempt to solve the recommended exercises (either alone or in a group) before reading the sample solutions.
Quizzes Most of the lectures will begin with a short quiz based on material covered in the previous lecture. Each quiz will be graded out of 20. Attendance is worth 50%, i.e., anyone who turns in a quiz will get a score of at least 10 out of 20. The quizzes are open book/notes. Electronic devices may be used during the quizzes, but only for the following two purposes: (1) to access an electronic version of the class textbook; (2) to access an electronic version of your personal class notes. As explained in the section below entitled "Overall Raw Score", all of your low quiz scores will be dropped in the computation of your course grade. If you miss a quiz for any reason (legitimate or otherwise), your score for that quiz will be a zero, so it will be dropped.
Tests There will be three in-class tests, on October 2, November 4, and December 4. The tests are closed book/notes, except that you are allowed to bring one page of notes (both sides may be used). Please try to arrive in class a few minutes early on the test dates; this will allow us to start the test right at the beginning of the class period.
Make-Up Tests Please note that no make-up tests will be given in this course. If a student has a legitimate and properly documented excuse for missing one of the tests, the missing test score will be estimated based on the other test scores. More complicated scenarios, e.g., where a student misses multiple tests for legitimate reasons, will be treated on a case-by-case basis. In the event of a non-excused absence, a score of zero will be assigned.
Overall Raw Score Each student's overall raw score out of 100 will be determined from the quiz and test scores as follows. First, the test average is computed (as a percentage), call it X. Then, each individual quiz score lower than X is replaced by X. Let Y denote the resulting quiz average. Then the overall raw score is 0.4 X + 0.6 Y.
Letter Grades The mapping from overall raw scores to letter grades will be determined at the end of the course. In a typical outcome, the final letter grades might be approximately evenly distributed over the symbols B, B+, A-, and A. (At the same time, the grade distribution can vary significantly from one class to another.)
Feedback Throughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course.
Academic Honesty See the following departmental document.