Randomized Algorithms II
Exam
Year  Semester  Date  Period  Language  In charge 

2013  spring  11.0324.04.  44  English  Jyrki Kivinen 
Lectures
Time  Room  Lecturer  Date 

Mon 1012  B119  Jyrki Kivinen  11.03.201324.04.2013 
Wed 1012  B119  Jyrki Kivinen  11.03.201324.04.2013 
Exercise groups
Time  Room  Instructor  Date  Observe 

Thu 1012  B119  Teppo NiinimÃ¤ki  18.03.2013—26.04.2013 
Information for international students
The lectures and all the material will be in English.
General
The course has been graded. The results are in the department intranet.
The course will take off where Randomized algorithms I ended. We will continue with the same textbook, and the approach will remain similar.
Randomized algorithms I is not a prerequisite for this course, and you are welcome to this course even if you were not on the former. However, we will not spend any more time refreshing background knowledge from probability calculus, so you are expected to be familiar with basic manipulations involving discrete random variables. Having a quick look through the material for Randomized algorithms I (either the lecture notes, or Chapters 1–6 of the textbook) might be useful.
This second course will have more emphasis on stochastic processes such as Markov chains, where in some sense time is explicitly modeled. We will also have more to say about continuous random variables. Besides applications to algorithms, we also consider some applications more generally related to computer science, such as simple queue systems.
Completing the course
The exam will be on Monday, 29 April, at 16:00 in A111. It will cover all the material presented in the course, except for martingales. This means Chapters 7, 8, 10 and 11 of the textbook, excluding Section 11.6.
The course consists of lectures, homework and the course examination.
Grading is based on the exam (80%) and homework (20%).
The practices on this course will be more or less the same as on Randomized algorithms I.
Literature and material
The lectures have ended and all the notes are now available: pages 1–204.
The course followed the textbook
 Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Michael Mitzenmacher and Eli Upfal. Cambridge University Press 2005.
 errata: first edition, second edition.
We covered Chapters 7, 8, 10 and 11 (excluding 11.6) of the textbook and had a very brief look into Chapter 12.
For additional reading, another very good book on these topics is
 Randomized algorithms. Rajeev Motwani and Prabhakar Raghavan. Cambridge University Press 1995.
Homework
Homework needs to be turned in in writing a few days before the exercise session. The written solutions will be graded. Participation in the exercise session is optional but highly recommend. The deadline for homework is 10:00am on the Wednesday before the exercise session. Turn in your homework to Teppo Niinimäki by email or on paper.

(deadline was Wednesday 20 March)
problems (from textbook): 7.2, 7.5, 7.12, 7.13, 7.19
solutions 
(deadline was Wednesday 3 April)
problems (from textbook): 7.14, 7.18, 7.26, 8.2, 8.9
solutions 
(deadline was Wednesday 10 April)
problems (from textbook): 8.6, 8.13, 8.15, 8.16, 8.19
solutions 
(deadline was Wednesday 17 April)
problems (from textbook): 8.20, 8.22, 8.23, 10.3, 10.5
solutions 
(deadline was Wednesday 24 April)
problems (from textbook): 10.6, 10.10, 10.12, 11,11, 11.14
solutions
Progress of the lectures
date  topics  in textbook  in lecture notes 

12 March  course organisation; Markov chains  pp. 153–161  pp. 1–20 
13 March  classification of states, stationary distribution  pp. 161–172  pp. 21–41 
18 March  examples of Markov chains; random walks in a graph  pp. 172–181  pp. 42–59 
20 March  uniform and exponential distributions  pp. 188–198  pp. 60–78 
25 March  combining exponential distributions; Poisson processes  pp. 198–205  pp. 79–95 
28 March  more about Poisson processes  pp. 205–209  pp. 96–106 
(Easter break)  
8 April  continuous time Markov processes  pp. 210–218  pp. 107–122 
10 April  Monte Carlo for counting problems  pp. 252–259  pp. 123–137 
15 April  from sampling to counting; Markov Chain Monte Carlo  pp. 259–266  pp. 138–156 
17 April  mixing times, coupling  pp. 271–278  pp. 157–173 
22 April  more mixing times with coupling  pp. 278282  pp. 174–183 
24 April  sampling graph colorings; martingales (very superficially)  pp. 282–286, 295–297, 303–308  pp. 184–204 