Randomized Algorithms I

582691
4
Algoritmit ja koneoppiminen
Syventävät opinnot
The course introduces a variety of tools from probability theory for designing and analysing randomized algorithms, and for analysing other probabilistic problems in computer science. Techniques include basic properties of discrete random variables, large deviation bounds, and balls and urns models. Applications include counting, distributed algorithms, and average case analysis. Prerequisites: Design and analysis of algorithms and a basic course in probabilities, or equivalent. Course book: M. Mitzenmacher, E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press 2005.

Koe

08.03.2016 16.00 A111
Vuosi Lukukausi Päivämäärä Periodi Kieli Vastuuhenkilö
2016 kevät 20.01-04.03. 3-3 Englanti Mikko Koivisto

Luennot

Aika Huone Luennoija Päivämäärä
Ke 10-12 C220 Mikko Koivisto 20.01.2016-04.03.2016
Pe 12-14 C220 Mikko Koivisto 20.01.2016-04.03.2016

Information for international students

The course will be given in English.

Yleistä

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.

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 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 herehere, 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***.

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
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