CMPUT675: Randomized Algorithms
Fall 2005, TR 3:30-4:50:, in CSC B10.
Instructor: Mohammad R. Salavatipour


CMPUT304, an undergraduate course in probability or statistics,, or strong undergraduate background in theoretical computer science and mathematics.

Randomized Algorithms, by Motwani and Raghavan, Cambridge press (1995). The link also includes an errata list.

Further reading: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by Michael Mitzenmacher and Eli Upfal, 2005.

Here is the course information sheet.

Lecture notes:

Other notes:

Template for course notes (modified from the one provided for CSC2401 offered by Micah Adler in 1998 in Univ. of Toronto).
Here is a sample and its source file.


Grading policy:
There will be 3 assignment sets (for a total of 60%), a take-home final exam or project (for 30%). Also, each participant in the course is required to provide scribe notes for one or two weeks of lectures. This (together with class participation) is worth 10% of your final mark. Scribe notes for each week are due the next Monday at noon. Scribe notes must be typed in LaTeX using the template provided above.

Tentative syllabus:

Useful Links:
Here are some useful links to more resources (books, course notes by other people who have taught this course, problems, etc.): Questions? Send email to me ...