Spring 2011
Unique Number 53640
CS 388R
Randomized Algorithms

Instructor Greg Plaxton (email: plaxton at cs); office hours M 10-11 and W 11-12 in ACE 3.434

Teaching Assistant Chao Ruan (email: ruan at cs); office hours T 2-3 in PAI 5.33 (Desk 2) and F 12-1 in PAI 5.33 (Desk 1)

Class Time MW 3:30-5

Class Location WAG 420

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. You are free to use the library or online resources to enhance your understanding of the course material, but you are not allowed to make use of existing solutions to the the specific problems assigned. If you obtain a key idea for solving one of the assigned problems through discussion with another person (other than the TA or course instructor), or from a book (other than the course textbook) or other online material, you should cite the source of that idea in your solution; no penalty will be assessed.

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 Wednesday, March 23 and will cover all of the course material related to Chapters 1 through 6. The second test will be held on Wednesday, May 4 and will cover the remainder 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. The last time I taught the course, the grades were fairly evenly distributed over the symbols A, A-, B+, and B.

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.

Instructor	Greg Plaxton (email: plaxton at cs); office hours M 10-11 and W 11-12 in ACE 3.434

Teaching Assistant	Chao Ruan (email: ruan at cs); office hours T 2-3 in PAI 5.33 (Desk 2) and F 12-1 in PAI 5.33 (Desk 1)

Class Time	MW 3:30-5

Class Location	WAG 420

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. You are free to use the library or online resources to enhance your understanding of the course material, but you are not allowed to make use of existing solutions to the the specific problems assigned. If you obtain a key idea for solving one of the assigned problems through discussion with another person (other than the TA or course instructor), or from a book (other than the course textbook) or other online material, you should cite the source of that idea in your solution; no penalty will be assessed.

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 Wednesday, March 23 and will cover all of the course material related to Chapters 1 through 6. The second test will be held on Wednesday, May 4 and will cover the remainder 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. The last time I taught the course, the grades were fairly evenly distributed over the symbols A, A-, B+, and B.

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.