Syllabus for Computer Science 469b/569b: Randomized Algorithms. Instructor: James Aspnes.
A study of randomized algorithms from several areas: graph algorithms, algorithms in algebra, approximate counting, probabilistically checkable proofs, and matrix algorithms. Topics include an introduction to tools from probability theory, including some inequalities such as Chernoff bounds.
2. Meeting times
MW 1:00–2:15 in AKW 500. See ../Schedule for more details.
3. On-line course information
On-line information about the course, including copies of all handouts, can be found using the URL http://pine.cs.yale.edu/pinewiki/CS469. This will also be the main location for announcements about the course, lecture schedules, and so forth. Please check it frequently.
Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms. Cambridge University Press, 1995. ISBN 0521474655. QA274 M68X 1995. Also available on-line from Yale campus IP addresses.
You may also find it helpful to have a good reference on probability theory. See ../ReservedBooks for some possibilities.
5. Course requirements
Six homework assignments (60% of the semester grade) plus a final exam (40%).
6. Use of outside help
Students are free to discuss homework problems and course material with each other, and to consult with the instructor or a TA. Solutions handed in, however, should be the student's own work. If a student benefits substantially from hints or solutions received from fellow students or from outside sources, then the student should hand in their solution but acknowledge the outside sources, and we will apportion credit accordingly. Using outside resources in solving a problem is acceptable but plagiarism is not.
7. Clarifications for homework assignments
From time to time, ambiguities and errors may creep into homework assignments. Questions about the interpretation of homework assignments should be sent to the instructor at <email@example.com>. Clarifications will appear in the on-line version of the assignment.
8. Late assignments
Late assignments will not be accepted without a Dean's Excuse.