Randomized Algorithms II

582692
4
Algoritmit ja koneoppiminen
Syventävät opinnot
Design and analysis of randomized algorithms with emphasis on basic Markov chain techniques. Prerequisites: Design and analysis of algorithms and a basic course in probabilities, or equivalent. Randomized algorithms I is not a prerequisite, but is highly recommended. Course book: M. Mitzenmacher, E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press 2005.

Koe

11.05.2016 16.00 CK112
Vuosi Lukukausi Päivämäärä Periodi Kieli Vastuuhenkilö
2016 kevät 16.03-06.05. 4-4 Englanti Mikko Koivisto

Luennot

Aika Huone Luennoija Päivämäärä
Ke 12-14 C220 Mikko Koivisto 16.03.2016-06.05.2016
Pe 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.

Yleistä

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.

Kurssin suorittaminen

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 herehere, 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 (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).

Kirjallisuus ja materiaali

The course follows the textbook

  • Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Michael Mitzenmacher and Eli Upfal. Cambridge University Press 2005.
  • errata: first editionsecond 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.