csci 3|6907 : randomized algorithms

»   schedule · archives: spring 2009

Course Description (+)

This is a course about randomization and computation. We will study the use of randomization in:

1. designing efficient algorithms: e.g. load-balancing algorithms, namely how to assign jobs to machines so as to minimize the maximum load; Bloom filters and hashing techniques for identifying duplicates and popular items in massive and/or streaming data sets (e.g. human genome sequences and Internet traffic).
2. modeling and quantifying certain "natural processes": e.g. the "birthday paradox" -- in any group of 23 people, it's quite likely that two will have the same birthday; random graph models used in explaining the structure of the Internet and large social networks.

Textbook. Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005.

Prerequsites. Algorithms (cs212) and Probability. Familiarity with expectation, variance, independent random variables (more)

Homework. #1 (due 1/30) · #2 (due 2/13) · #3 (due 2/27) · #4 (due 3/19) · #5? (due 4/2)

Exercises. #2 · #3 · #4 · #5 ·

Announcements.

• Mar 23: posted tentative assignments and schedule for final presentations.
• Apr 9: Rate the presentations for week #1 here by Fri Apr 12.
• Apr 16: Rate the presentations for week #2 here by Fri Apr 19.
• Apr 22: Submit project homework question+solution as a pdf file via email by May 1 (Wed).
• Apr 24: Rate the presentations for week #3 here by Fri Apr 26.