MAT-72306 Randomized Algorithms, 4 cr
Additional information
Next implementation round in Spring 2017
Suitable for postgraduate studies
Will not be lectured year 2015-2016
Person responsible
Tapio Elomaa
-->Learning Outcomes
After completion of the course the student will comprehend the probabilistic background of randomized algorithms and will grasp the general usefulness of randomization in algorithm design.
Content
| Content | Core content | Complementary knowledge | Specialist knowledge |
| 1. | Discrete random variables and expectation | Bernoulli and binomial random variables | |
| 2. | Moments and deviations | Markov's inequality, Chebyshev's inequality | |
| 3. | Chernoff bounds | Moment generating functions | |
| 4. | Balls, bins, and random graphs | The Poisson distribution | |
| 5. | The probabilistic method | Derandomization using conditional expectations | |
| 6. | Markov chains and random walks |
Instructions for students on how to achieve the learning outcomes
The assessment is based on an exam.
Assessment scale:
Numerical evaluation scale (1-5) will be used on the course
Partial passing:
Study material
| Type | Name | Author | ISBN | URL | Additional information | Examination material |
| Book | Probability and Computing | Mitzenmacher and Upfal | 0-521-83540-2 | No |
Prerequisites
| Course | Mandatory/Advisable | Description |
| MAT-02500 Todennäköisyyslaskenta | Mandatory | |
| MAT-02650 Algoritmimatematiikka | Mandatory | |
| TIE-02200 Ohjelmoinnin peruskurssi | Advisable |
Correspondence of content
There is no equivalence with any other courses