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

1. Introduction

2. Pseudo Random Numbers

3. Random Number Generators

PART 2: Stochastic Methods

4. Computing Integrals

5. Local and Global Optimization

6. Discrete Event Simulation

PART 3: Probabilistic Algorithms for Discrete Problems

7. Introduction to Discrete Algorithms (Motwani & Raghavan)
     Paradigms for Probabilistic Algorithms
     Randomized Quicksort
     Randomized Min-Cut Algorithm
     Classification of Probabilistic Algorithms
   

8. Searching (Brassard & Bratley, Törn)
     Searching an Ordered List
     Hashing
   

9. Finding and Using Large Prime Numbers (Harel)
     Primality Testing
     Cryptography
   

10. Fingerprinting (Motwani & Raghavan)
      Verifying Matrix Multiplication
      Verifying Equality of Strings

11. Summary