CS 590: Randomized and Probabilistic Algorithms

Spring 2005

Welcome to CS590!
This is a homepage of CS 590 ``Randomized and Probabilistic Algorithms'' course. This course will teach you how to design and analyze algorithms and data structures on strings (e.g., digital trees, pattern matching, data compression schemes). Following the general precept: {\it 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 of precise analysis of algorithms. The area of (precise) analysis of algorithms (at least, the way we understand it) was born on July 27, 1963, when D. E. Knuth wrote his ``Notes on Open Addressing'' about hashing tables with linear probing. Since 1963 the field has been undergoing substantial changes. You want to know what's new? Come to the course and learn these new exciting developments. This site contains important administrative information, class announcements, assignments, and handouts.