Randomized Algorithms II
Exam
Year | Semester | Date | Period | Language | In charge |
---|---|---|---|---|---|
2016 | spring | 16.03-06.05. | 4-4 | English | Mikko Koivisto |
Lectures
Time | Room | Lecturer | Date |
---|---|---|---|
Wed 12-14 | C220 | Mikko Koivisto | 16.03.2016-06.05.2016 |
Fri 12-14 | C220 | Mikko Koivisto | 16.03.2016-06.05.2016 |
Ilmoittautuminen tÃ¤lle kurssille alkaa tiistaina 16.2. klo 9.00.
Registration for this course starts on Tuesday 16th of February at 9.00.
Information for international students
The lectures and the material will be given in English.
General
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
To pass the course, you need about 30 points or more in total. The maximum number of points is 60, of which 12 can be earned by homework and 48 by the course exam. For the best grade you need about 50 points. Attending the lectures and doing homework is not mandatory but strongly recommended.
The lectures consist of 13 two-hour meetings, spanning 7 weeks and scheduled as listed below; note the easter break at the end of March. Each two-hour meeting contains lecturing (including prepared examples), exercises done either individually or in small groups, and time for questions and answers. Compared to the first part in the series (Randomized Algorithms I), we spend significantly less time on the lecture notes and more time on solving exercises (not homework problems though) from the book. Every second week, the first hour of the Wednesday meeting is reserved for discussing the past homework problems. It is recommended that you familiarize yourself with the material of each meeting in advance by reading the book and the lecture notes.
Homework is the key for learning. There are 21 homework problems in total, grouped into 3 sets, each consisting of 7 problems (numbered exercises from the course book). The problems are announced here, here, and here (not later than 13 days before the deadline), and are discussed in the Wednesday meetings on April 6th, April 20th, and May 4th, respectively. To earn homework points, you are required to submit your solutionsto the problems in the PDF format (in writing) by sending email to the lecturer 24 hours prior to the respective meeting. Each submitted solution is graded as 0 (no or poor attempt), 1 (reasonable attempt and something relevant and correct), 2 (largely complete and correct), or 3 (essentially complete and correct) homework points. Dividing the sum of the grades by 4.5 and rounding up yields the number of earned course points. Solutions to the homework problems are revealed here, here, and here about 24 hours prior to the meeting.
In the course exam, you have 2.5 hours to solve 4 problems. The problems are similar to the homework problems. You are allowed to bring with you one 2-sided paper sheet containing any notes of your choice. No smart devices are allowed.
The course exam was held on May 11th. See the exam problems and model solutions. The fourth problem appeared to be quite laborous in relation to the 2.5-hour time limit, which was taken into account in the final grades (24 course points -> 1/5, 45 -> 5/5).
Literature and material
The course follows the textbook
- Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Michael Mitzenmacher and Eli Upfal. Cambridge University Press 2005.
- errata: first edition, second edition.
For additional reading, another very good book on these topics is
- Randomized algorithms. Rajeev Motwani and Prabhakar Raghavan. Cambridge University Press 1995.
As Lecture Notes, we will reuse the notes of the earlier lecture course given by Jyrki Kivinen. The full set of notes in a PDF format.
Schedule
Date | Topics | In Textbook | In Lecture Notes |
---|---|---|---|
16 March | course organisation; Markov chains | pp. 153–161 | pp. 1–20 |
18 March | classification of states, stationary distribution | pp. 161–172 | pp. 21–41 |
23 March | examples of Markov chains; random walks in a graph | pp. 172–181 | pp. 42–59 |
(Easter Break) | |||
1 April | uniform and exponential distributions | pp. 188–198 | pp. 60–78 |
6 April | combining exponential distributions; Poisson processes | pp. 198–205 | pp. 79–95 |
8 April | more about Poisson processesa | pp. 205–209 | pp. 96–106 |
13 April | continuous time Markov processes | pp. 210–218 | pp. 107–122 |
15 April | Monte Carlo for counting problems | pp. 252–259 | pp. 123–137 |
20 April | from sampling to counting; Markov Chain Monte Carlo | pp. 259–266 | pp. 138–156 |
22 April | mixing times, coupling | pp. 271–278 | pp. 157–173 |
27 April | more mixing times with coupling | pp. 278-282 | pp. 174–183 |
29 April | sampling graph colorings; martingales (very superficially) | pp. 282–286, 295–297, 303–308 | pp. 184–204 |
4 May | summary, questions & answers, extra exercises etc. |