MAT-72306 Randomized Algorithms, 4 cr
Additional information
No implementation during the academic year 2017-2018
Suitable for postgraduate studies.
The implementation will not be executed during the academic year 2017-2018.
Person responsible
Tapio Elomaa
Lessons
| Implementation | Period | Person responsible | Requirements |
| MAT-72306 2017-01 | - |
Tapio Elomaa |
Exam at the end of the course. Exercises yield extra points. |
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 (0-5)
Partial passing:
Study material
| Type | Name | Author | ISBN | URL | Additional information | Examination material |
| Book | Probability and Computing | Michael Mitzenmacher & Eli Upfal | 521835402 | Yes |
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