MAT-72306 Randomized Algorithms, 4 cr

Additional information

Suitable for postgraduate studies.

Person responsible

Tapio Elomaa

Lessons

Implementation Period Person responsible Requirements
MAT-72306 2016-01 3 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:

Completion parts must belong to the same implementation

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

Updated by: Ikonen Suvi-Päivikki, 13.04.2016