Computer
Science
599.01
/ 601.07 - Randomized Algorithms
Contents
Course
Summary
Textbooks
Requirements
Lectures
Contact
Office
Hours
Course Summary
In this course we study
algorithms that make random choices as they proceed. Over the last
decades, such randomized (or probabilistic) algorithms have found
widespread application in essentially all areas of computing, and
randomization has become one of the most powerful tools in algorithm
design. For many applications we know randomized algorithms that are
simpler or more efficient (or both) than any known deterministic
algorithms.
This course will explore
techniques for designing and analyzing randomized algorithms, and will
provide examples from a variety of problem areas. Topics include
- Fundamental techniques for the design and analysis of
randomized algorithms
- Applications
- Randomized complexity classes
Basic knowledge in
probability theory is required (e.g., the notion of random variables,
expectation, independence, etc.). More advanced material will be
introduced whenever necessary.
Textbooks
- Required:
Randomized
Algorithms, R.
Motwani and P. Raghavan, Cambridge University Press 1995. ISBN
0-521-47465-5.
- Additional reading:
- Design and Analysis of Randomized
Algorithms, Juraj Hromkovič,
Springer 2005. ISBN 3-540-23949-9
- Probability and
Computing - Randomized Algorithms and Probabilistic Analysis, M. Mitzenmacher and E. Upfal,
Cambridge University Press 2005. ISBN 0-521-83540-2.
Requirements
- Consent of the department.
- Basic knowledge in
probability theory (Math 321 is recommended).
- Practice in the
analysis of algorithms
(CPSC 413 is strongly recommended).
Lectures
Time: Tuesdays and
Thursdays, 14:00-15:15.
Location: KNB 128
Contact
See my homepage.
Office Hours
Tuesdays and Thursdays,
11:00-11:45 (ICT 655), or by appointment.
Please approach me right after class if you want to meet me during my
regular office hours.