## Computer
Science 599.60 / 601.60 - Randomized Algorithms

### Contents

News

Course
Summary

Textbooks

Requirements

Lectures

Contact

Office
Hours

License Information

### News

17. Sept.
2007: I won't post news on this website
anymore. All information and
news for this course is now availble in the course forum.

### 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, randomized algorithms are available,
which are simpler or faster (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 will include

- Fundamental techniques for the design and analysis of
randomized algorithms (lower bound techniques, moments and deviations,
tail inequalities, the probabilistic method)

- Applications (data structures, load balancing, network
algorithms, and others)

- 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:

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).
- You might not get
credit for this course if you have received credit for CPSC 517 from
Winter 2007 (other years are o.k.).

### Lectures

Time: Tuesdays and
Thursdays, 12:30-13:45pm.

Location: ENC 123

### Contact

See my homepage.

### Office Hours

Tuesdays and Thursdays,
14:00-15:00pm (ICT 655), or by appointment.

Please approach me right after class if you want to meet me during my
regular office hours.

### License Information

All work published on this
webpage is licensed under a Creative
Commons Attribution-Noncommercial-Share Alike 3.0 License, unless
otherwise stated.