Randomized Algorithms I
Exam
Year | Semester | Date | Period | Language | In charge |
---|---|---|---|---|---|
2016 | spring | 20.01-04.03. | 3-3 | English | Mikko Koivisto |
Lectures
Time | Room | Lecturer | Date |
---|---|---|---|
Wed 10-12 | C220 | Mikko Koivisto | 20.01.2016-04.03.2016 |
Fri 12-14 | C220 | Mikko Koivisto | 20.01.2016-04.03.2016 |
Information for international students
The course will be given in English.
General
The two courses Randomized algorithms I–II cover a variety of probabilistic techniques useful in designing and analysing algorithms. Loosely speaking, Randomized algorithms I deals mainly with calculations using discrete random variables, whereas in Randomized algorithms II there is more emphasis on stochastic processes (Markov chains, Poisson processes). More practically, the two courses follow the same textbook, with the earlier chapters covered in the first course.
It is possible to take either one of the courses separately (in particular, Randomized algorithms I is not a prerequisite for Randomized algorithms II), but taking them together is generally recommended.
There will be a quick refresher on basic probability theory in the beginning of Randomized algorithms I, but the students are expected to have at least some background knowledge about probability theory. Also some basic calculus etc. may be needed during the course, but any more advanced mathematical tools will be introduced as needed.
Basic knowledge of design and analysis of algorithms is also needed. There is little if any need for any advanced data structures etc. What is mainly needed is more general problem solving skills.
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 14 two-hour meetings, spanning 7 weeks and scheduled as listed below; note the winter break at the end of February. Each two-hour meeting contains lecturing (including prepared examples), exercises done either individually or in small groups, and time for questions and answers. Every second week, the first hour of the Friday 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. NOTE: There are no meetings on Wednesday 24nd and Friday 26th February (Winter Break).
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, and are discussed in the Friday meetings on Jan 29th, Feb 12th, and Mar 4th, respectively. To earn homework points, you are required to submit your solutions to 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. Diving 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 March 8. See the exam problems and example solutions (corrected/graded March 16, 2016). The grade distribution among those that have passed the course so far: 1*** 2 3* 4 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 |
---|---|---|---|
20 Jan | course organisation; basic probability | pp. 1–10 | pp. 1–25 |
22 Jan | discrete random variables, expectations, Jensen's Inequality | pp. 10–14, 20–28 | pp. 26–38 |
27 Jan | geometric distribution with applications; Markov's Inequality | pp. 29–38, 44–45 | pp. 39–52 |
29 Jan | variance; Chebyshev's Inequality | pp. 45–57, 61–62 | pp. 53–69 |
3 Feb | Chernoff bounds: proofs and examples | pp. 63–72 | pp. 70–89 |
5 Feb | randomized routing in hypercube | pp. 72–79 | pp. 90–108 |
10 Feb | routing in butterfly network; birthday paradox | pp. 78–83, 90–91 | pp. 109–122 |
12 Feb | balls and bins, Poisson approximation | pp. 92–104 | pp. 123–148 |
17 Feb | examples of balls and bins models | pp. 104–113 | pp. 149–167 |
19 Feb | Hamiltonian random graphs; basic probabilistic method | pp. 113–119, 126–131 | pp. 168–191 |
(Winter Break) | |||
2 Mar | more techniques for the probabilistic method | pp. 131–138 | pp. 192–210 |
4 Mar | Lovász Local Lemma; conclusion | pp. 138–141; 146–147 | pp. 211–228 |