MAT-72306 Randomized Algorithms, 4 cr

Prof. Tapio Elomaa

Spring 2015, period III

Lectures: Jan. 13 - Mar. 5
Weekly exercises: M.Sc. Juho Lauri, Mon 10 - 12 TC315
Course exam: Wed. Mar. 11, 2015 (next Apr. 28)

- News

- General Information

- Lectures

The course is based on the textbook:

WeekDatesSlidesExercises Chapters in the Book
1 Jan. 13 & 15 1 - 74 n/a 1 Events and Probability
2 Jan. 20 & 22 75 - 116 + 122 - 123 Jan. 19 2 Discrete Random Variables and Expectation
3 Jan. 27 & 29 117 - 169 Jan. 26 3 Moments and Deviations
4 Feb. 3 & 5 170 - 206 Feb. 2 4 Chernoff Bounds
5 Feb. 10 & 12 207 - 257 Feb. 9 5 Balls, Bins, and Random Graphs
6 Feb. 17 & 19 258 - 305 Feb. 16 6 The Probabilistic Method
7 Feb. 24 & 26 306 - 359 Feb. 23 7 Markov Chains and Random Walks
8 Mar. 3 & 5 360 - 400 Mar. 2 9 Entropy, Randomness, and Information

- Contents

  1. Events and Probability
  2. Discrete Random Variables and Expectation
  3. Moments and Deviations
  4. Chernoff Bounds
  5. Balls, Bins, and Random Graphs
  6. The Probabilistic Method
  7. Markov Chains and Random Walks
  8. Continuous Distributions and the Poisson Process
  9. Entropy, Randomness, and Information
  10. The Monte Carlo Method


Mar. 5, 2015 http://www.cs.tut.fi/~elomaa/