Randomized Algorithms II

582692
4
Algorithms and machine learning
Advanced studies
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.

Exam

29.04.2013 16.00 A111
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

Group: 1
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.

 

  1. (deadline was Wednesday 20 March)
    problems (from textbook): 7.2, 7.5, 7.12, 7.13, 7.19
    solutions
  2. (deadline was Wednesday 3 April)
    problems (from textbook): 7.14, 7.18, 7.26, 8.2, 8.9
    solutions
  3. (deadline was Wednesday 10 April)
    problems (from textbook): 8.6, 8.13, 8.15, 8.16, 8.19
    solutions
  4. (deadline was Wednesday 17 April)
    problems (from textbook): 8.20, 8.22, 8.23, 10.3, 10.5
    solutions
  5. (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