CS 590: Probabilistic Methods in Computer Science

Spring 2010

Welcome to CS590!

This is a homepage of CS 590 ``Probabilistic Methods in Computer Science'' In this course we discuss probabilistic and analytic methods that are often used in designing and analyzing (randomized) algorithms and data structures. Donald E. Knuth in ``Randomization and Religion'' confessed: ``If somebody would ask me, what in the last 10 years, what was the most important change in the study of algorithms I would have to say that people getting really familiar with randomized algorithms had to be the winner''. Following the general precept: Give a man a fish and you feed him for the day; teach him to fish and you feed him for his lifetime, we will concentrate on methodology. In the first part of the course, we focus on techniques, and every method is illustrated by a variety of specific problems that arose from algorithms and data structures, mostly on strings. Our choice of algorithms stems from the fact that there has been a resurgence of interest in algorithms on sequences and their applications in computational biology, security, multimedia compression, and information theory. This site contains important administrative information, class announcements, assignments, and handouts.