|
|
|||||||||||||||||
Course Catalog 2014-2015
MAT-72306 Randomized Algorithms, 4 cr |
Additional information
Suitable for postgraduate studies
Person responsible
Tapio Elomaa
Lessons
| Study type | P1 | P2 | P3 | P4 | Summer | Implementations | Lecture times and places |
|
|
|
|
|
|
|
|
|
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 | Edition, availability, ... | Examination material | Language |
| Book | Probability and Computing | Mitzenmacher and Upfal | 0-521-83540-2 | No | English |
Prerequisites
| Course | Mandatory/Advisable | Description |
| MAT-02500 Todennäköisyyslaskenta | Mandatory | |
| MAT-02650 Algoritmimatematiikka | Mandatory | |
| TIE-02200 Ohjelmoinnin peruskurssi | Advisable |
Prerequisite relations (Requires logging in to POP)
Correspondence of content
There is no equivalence with any other courses
More precise information per implementation
| Implementation | Description | Methods of instruction | Implementation |
| Spring 2015 |
Contact teaching: 0 % Distance learning: 0 % Self-directed learning: 0 % |