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