Course material prepared by Aimo Törn in the Autumn 1998 for a course on Probabilistic Algorithms at the Computer Science Department of Åbo Akademi University and TUCS Turku, Finland. The course is based on the books listed in the Abstract.© A. Törn. Must not be reproduced verbatim or by editing, or used for giving a course without permission from the author.
In scientific text all variable names should be in mathematical font (italic). We will try to adhere to this in the running text but not in the displayed formulas because of readability reasons.
PART 1: Motivation and Tools
PART 2: Stochastic Methods
PART 3: Probabilistic Algorithms for Discrete Problems
- Introduction to Discrete Algorithms (Motwani & Raghavan)
Paradigms for Probabilistic Algorithms
Randomized Quicksort
Randomized Min-Cut Algorithm
Classification of Probabilistic Algorithms
- Searching (Brassard & Bratley, Törn)
Searching an Ordered List
Hashing
- Finding and Using Large Prime Numbers (Harel)
Primality Testing
Cryptography
- Fingerprinting (Motwani & Raghavan)
Verifying Matrix Multiplication
Verifying Equality of Strings- Summary