Probabilistic Methods in Computer Science and Applications

Dates: 22.5 - 2.6
Professor: W. Szpankowski
Course Hours: Mon-Fri, 11:00-14:00 in Room EA 06 (Mon-Th), in Room EA23 (Fri)
Consulting: Mon-Fri, 14:00-15:00 in Room 130


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 t e first part of the course, we discuss several 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. More ...