Randomized Algorithms II
Exam
Year | Semester | Date | Period | Language | In charge |
---|---|---|---|---|---|
2013 | spring | 11.03-24.04. | 4-4 | English | Jyrki Kivinen |
Lectures
Time | Room | Lecturer | Date |
---|---|---|---|
Mon 10-12 | B119 | Jyrki Kivinen | 11.03.2013-24.04.2013 |
Wed 10-12 | B119 | Jyrki Kivinen | 11.03.2013-24.04.2013 |
Exercise groups
Time | Room | Instructor | Date | Observe |
---|---|---|---|---|
Thu 10-12 | 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 e-mail 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. 278-282 | pp. 174–183 |
24 April | sampling graph colorings; martingales (very superficially) | pp. 282–286, 295–297, 303–308 | pp. 184–204 |