## Probability and Algorithms (WS 2015/2016)

Lectures: Tu, 11:45 - 13:15 in 48-582 and Fr, 08:15 - 09:45 in 44-380

Exercises: Thu, 13:45 - 15:15 in 44-465
### Content

The lecture will cover the two main cutting edges of probability and algorithms: randomized algorithms and average case

analysis algorithms. Randomized algorithms: algorithms that contain some decisions done at random are called "randomized".

Two benefits of randomization caused a lot of interest and research activities in the last twenty years: simplicity and

speed. for many applications a randomized algorithm ist the simplest algorithm available, or the fastest, or both. The

lecture will present basic concepts in the design and analysis of randomized algorithms. Average case analysis of algorithm:

in practice often algorithm behave better as the worst case situation promises. One way to explain the better behaviour in

practice is to design a stochastic data model and to study expectation value and variance of complexity. The lecture will

give examples of such average case analysis and numerous links to randomization techniques that come up with the complexity

analysis.

### Exercises

Please submit your exercises on tuesdays in class.

- Exercises 1 (03.11.2015)
- Exercises 2 (10.11.2015)
- Exercises 3 (17.11.2015)
- Exercises 4 (24.11.2015)
- Exercises 5 (01.12.2015)
- Exercises 6 (08.12.2015)
- Exercises 7 (15.12.2015)
- Exercises 8 (22.12.2015)
- Exercises 9 (12.01.2016)
- Exercises 10 (19.01.2016)
- Exercises 11 (26.01.2016)
- Exercises 12 (02.02.2016)