Fall 2013Unique Number 54115CS 388RRandomized Algorithms

InstructorGreg Plaxton (email: plaxton at cs); office hours MTh 3-4 in GDC 4.512 Teaching AssistantChunzhi Su (email: suchunzhi at gmail dot com); office hours T 11-12 and F 1-2 in GDC 6.440 Class TimeMW 9:30-11 Class LocationGDC 6.202 TextbookThe textbook for the course is Randomized Algorithmsby Motwani and Raghavan (Cambridge University Press, 1995).Course OutlineThe 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. PrerequisitesGraduate standing and either an undergraduate algorithms course (such as CS 331 or CS 357) or consent of instructor. Recommended ExercisesSix 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. QuizzesMost 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. TestsThere will be three in-class tests, on October 2,November 4, andDecember 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 TestsPlease 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 ScoreEach 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 GradesThe 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.) FeedbackThroughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course. Academic HonestySee the following departmental document.