Spring 2008
Unique Number 55840
CS 388R
Randomized Algorithms

Instructor Greg Plaxton (office hours W 3-4, Th 11-12, TAY 3.132; email: plaxton at cs)

Teaching Assistant Jing-Tang (Keith) Jang (office hours M 10-11, W 11-12, Desk #3 in ENS 31NQ; email: keith at cs)

Class Time TTh 3:30-5

Class Location GEA 114

Textbook The textbook for the course is Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal (Cambridge University Press, 2005).

Course Outline The following major topics will be covered: events and probability (Chapter 1); discrete random variables and expectation (Chapter 2); moments and deviations (Chapter 3); Chernoff bounds (Chapter 4); balls, bins, and random graphs (Chapter 5); the probabilistic method (Chapter 6); Markov chains and random walks (Chapter 7); the Monte Carlo method (Chapter 10); coupling of Markov chains (Chapter 11); martingales (Chapter 12); pairwise independence and universal hash functions (Chapter 13); balanced allocations (Chapter 14). See the schedule for a more detailed specification of the lecture plan.

Assignments There will be seven assignments. You are allowed to discuss high-level approaches to the problems with other members of the class, but you are not allowed to discuss or exchange detailed solutions.

Quizzes Most of the lectures will include a brief quiz based on material from the previous lecture. The quizzes are open book/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 two in-class tests. The tests will be closed book and closed notes; you are only allowed to bring one page of notes (both sides may be used). The first test will be held on Thursday, March 20 and will cover all of the course material related to Chapters 1 through 6. The second test will be held on Thursday, May 1 and will cover all the rest of the course material. 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 taken to be equal to the other test score. More complicated scenarios, e.g., where a student misses both 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 points, will be determined from performance on the assignments, quizzes, and tests. Assignment 1 is worth 4 points, and Assignments 2 through 7 are each worth 7 points, for a total of 46 points. The remainder of the raw score is determined as follows. Let x denote your average score on the tests (expressed as a fraction, e.g., if you have a 70% test average, then x is 0.7), let n denote the total number of quizzes, let A denote the set of quizzes on which you scored higher than your test average, let y denote your average score (again expressed as a fraction) over the quizzes in set A, and let w denote 36 * |A| / n. Then your raw score out of 54 for the quizzes and tests is (54 - w) * x + w * y. Example 1: Mary doesn't take any of the quizzes, but she scores 100% on all three tests. Mary's raw score for the quizzes and tests is 54 out of 54. Example 2: Joe enjoys a brief quiz -- and aces all of them -- but, for unknown reasons, he refuses to participate in any sort of "test". Joe's raw score for the quizzes and tests is 36 out of 54. Example 3: Pat has a test average of 75%, and gets better than 75% on 21 out of a total of 28 quizzes. The average of Pat's top 21 quiz scores is 90%. Pat's raw score for the quizzes and tests is (54 - 27) * 0.75 + 27 * 0.9 = 44.55 out of 54, or 82.5%.

Letter Grades The mapping from overall raw scores to letter grades will be determined at the end of the course. A letter grade distribution in which about half of the students in the class receive an A- or better is not atypical for this kind of course.

Feedback Throughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course.

Academic Dishonesty Cheating on the assignments, quizzes, or tests will not be tolerated. If you find yourself overwhelmed by coursework or other special circumstances, do not resort to cheating. Instead, make an appointment to see the instructor to discuss your situation.

Instructor	Greg Plaxton (office hours W 3-4, Th 11-12, TAY 3.132; email: plaxton at cs)

Teaching Assistant	Jing-Tang (Keith) Jang (office hours M 10-11, W 11-12, Desk #3 in ENS 31NQ; email: keith at cs)

Class Time	TTh 3:30-5

Class Location	GEA 114

Textbook	The textbook for the course is Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal (Cambridge University Press, 2005).

Course Outline	The following major topics will be covered: events and probability (Chapter 1); discrete random variables and expectation (Chapter 2); moments and deviations (Chapter 3); Chernoff bounds (Chapter 4); balls, bins, and random graphs (Chapter 5); the probabilistic method (Chapter 6); Markov chains and random walks (Chapter 7); the Monte Carlo method (Chapter 10); coupling of Markov chains (Chapter 11); martingales (Chapter 12); pairwise independence and universal hash functions (Chapter 13); balanced allocations (Chapter 14). See the schedule for a more detailed specification of the lecture plan.

Assignments	There will be seven assignments. You are allowed to discuss high-level approaches to the problems with other members of the class, but you are not allowed to discuss or exchange detailed solutions.

Quizzes	Most of the lectures will include a brief quiz based on material from the previous lecture. The quizzes are open book/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 two in-class tests. The tests will be closed book and closed notes; you are only allowed to bring one page of notes (both sides may be used). The first test will be held on Thursday, March 20 and will cover all of the course material related to Chapters 1 through 6. The second test will be held on Thursday, May 1 and will cover all the rest of the course material. 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 taken to be equal to the other test score. More complicated scenarios, e.g., where a student misses both 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 points, will be determined from performance on the assignments, quizzes, and tests. Assignment 1 is worth 4 points, and Assignments 2 through 7 are each worth 7 points, for a total of 46 points. The remainder of the raw score is determined as follows. Let x denote your average score on the tests (expressed as a fraction, e.g., if you have a 70% test average, then x is 0.7), let n denote the total number of quizzes, let A denote the set of quizzes on which you scored higher than your test average, let y denote your average score (again expressed as a fraction) over the quizzes in set A, and let w denote 36 * \|A\| / n. Then your raw score out of 54 for the quizzes and tests is (54 - w) * x + w * y. Example 1: Mary doesn't take any of the quizzes, but she scores 100% on all three tests. Mary's raw score for the quizzes and tests is 54 out of 54. Example 2: Joe enjoys a brief quiz -- and aces all of them -- but, for unknown reasons, he refuses to participate in any sort of "test". Joe's raw score for the quizzes and tests is 36 out of 54. Example 3: Pat has a test average of 75%, and gets better than 75% on 21 out of a total of 28 quizzes. The average of Pat's top 21 quiz scores is 90%. Pat's raw score for the quizzes and tests is (54 - 27) * 0.75 + 27 * 0.9 = 44.55 out of 54, or 82.5%.

Letter Grades	The mapping from overall raw scores to letter grades will be determined at the end of the course. A letter grade distribution in which about half of the students in the class receive an A- or better is not atypical for this kind of course.

Feedback	Throughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course.

Academic Dishonesty	Cheating on the assignments, quizzes, or tests will not be tolerated. If you find yourself overwhelmed by coursework or other special circumstances, do not resort to cheating. Instead, make an appointment to see the instructor to discuss your situation.