Randomized Algorithms II

Registration is open for this course »
582692
4
Algorithms and machine learning
Advanced studies
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

Information for international students

The lectures and all the material will be 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

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 lecture notes will appear here as the course progresses. Currently available: pages 1–148.

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.

We will cover Chapters 7, 8 and 10 of the textbook, and time permitting also parts of Chapters 11 and 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 at 10:00am)
    problems (from textbook): 7.2, 7.5, 7.12, 7.13, 7.19
    solutions
  2. deadline Wednesday 3 April at 10:00am
    problems (from textbook): 7.14, 7.18, 7.26, 8.2, 8.9
    solutions
  3. deadline Wednesday 10 April at 10:00am
    problems (from textbook): 8.6, 8.13, 8.15, 8.16, 8.19
    In Problem 8.16, the "expressions" you find need not be particularly simple, the main point is to model the situation correctly.

 

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

 

Exercise groups

Group number: 1
Time Room Instructor Date Observe
Thu 10-12 B119 Teppo Niinimäki 18.03.2013-26.04.2013