15-859(D) Randomized Algorithms, Fall 1998

Course Information


Lectures: Tues, Thurs 10:30--11:50, Wean 5409B

Instructor: Avrim Blum (Wean 4107, avrim+@cs.cmu.edu, x8-6452. Office Hours: Mon 10:30-12:00)

Course Secretary: Dorothy Zaborowsky (Wean 4116, daz@cs.cmu.edu, x8-3779)

Credits: 12 Units, 1 CU.

Evaluation and Responsibilities: Grading will be based on a collection of homework assignments, a take-home final, and class participation. As part of class participation, each student (possibly in teams) will give a class presentation on a topic chosen in consultation with the instructor. Because this course has no TA, students from time to time will also be asked to help with the grading of assignments.

Text: Randomized Algorithms by Rajeev Motani and Prabhakar Raghavan, plus papers and notes for topics not in the book.

Course description: Randomness has proven itself to be a useful resource for developing provably efficient algorithms and protocols. As a result, the study of randomized algorithms has become a major research topic in recent years. This course will explore a collection of techniques for effectively using randomization and for analyzing randomized algorithms, as well as examples from a variety of settings and problem areas. Specific topics to be covered include: