Randomized Algorithms I

Exam

26.02.2013 16.00 A111
Year Semester Date Period Language In charge
2013 spring 14.01-20.02. 3-3 English Jyrki Kivinen

General

The course has ended, and this page is no longer maintained.  Links to the exam and results are below.  Please remember to give us feedback about the course.

About the contents of the course

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

Results

The course examination was on Tuesday, 26 February, at 16:00 in Exactum A111. The exam and the course have now been graded.

The examination

The course examination will take place on Tuesday, 26 February, at 16:00 in Exactum A111.

The exam area is all the material presented in lectures and in homework, and the related parts of the textbook. See below for details.

Homework

To get credit for homework, you need to turn in your written solutions each week by a given deadline. The homework will be graded on a very coarse scale. More detailed feedback on the homework is given at the weekly homework sessions, attending which is highly recommended but not compulsory. The course assistant will not answer detailed questions about the homework by e-mail.

There was no homework session on the first week.  The deadline for the first set of homework was Tuesday, 22 January, 9:00 am.

Literature and material

The lecture notes will appear here as the course progresses. 

  • The whole set of notes is now available: pages 1–228
  • definition of active packet on p. 98 has been fixed as was discussed during the lecture (3 February)
  • some specific references to the textbook (theorem numbers etc.) have been added (3 February)
  • typos fixed and the definition of dependency graph on p. 212 clarified (20 February)

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.

 

Homework

Homework must be turned in to the course assistant Teppo Niinimäki either by e-mail or on paper (room A338). The dealine is 9:00am on the Tuesday before the session.

Late homework: If you turn your homework in late, but by no more than 24 hours, you'll receive half the points. Homework turned in more than 24 hours after the deadline will not give any points.

  1. deadline: 22 January
    problems (from the textbook): 1.6, 1.15, 2.6, 2.16, 2.26
    solutions
  2. deadline: 29 January
    problems (from the textbook): 2.24, 2.32, 3.18, 3.21, 3.24
    solutions
  3. deadline: 5 February
    problems (from the textbook): 4.3, 4.4, 4.8, 4.13, 4.21
    solutions
  4. deadline: 12 February
    problems (from the textbook): 4.24, 5.5, 5.9, 5.12, 5.14
    Problem 5.14, and the related problem 5.13, contain mistakes; see the errata (first edition, second edition).
    solutions
  5. deadline: 19 February
    problems (from the textbook): 5.21, 5.22, 5.26, 6.4, 6.10
    Problem 6.4(c) is optional, but you get one extra point if you solve it, too. It asks you to use the method of conditional expectations, which will be covered in the lectures on Monday. If you don't want to wait until then or study it on your own, you can just figure out a deterministic strategy without using particular method by just thinking about the situation and how you obtained part (b).
    solutions

 

Progress of the lectures

 

date topics in textbook in lecture notes
14 Jan course organisation; basic probability pp. 1–10 pp. 1–25
16 Jan discrete random variables, expectations, Jensen's Inequality pp. 10–14, 20–28 pp. 26–38
21 Jan geometric distribution with applications; Markov's Inequality pp. 29–38, 44–45 pp. 39–52
23 Jan variance; Chebyshev's Inequality pp. 45–57, 61–62 pp. 53–69
28 Jan Chernoff bounds: proofs and examples pp. 63–72 pp. 70–89
30 Jan randomized routing in hypercube pp. 72–79 pp. 90–108
4 Feb routing in butterfly network; birthday paradox pp. 78–83, 90–91 pp. 109–122
6 Feb balls and bins, Poisson approximation pp. 92–104 pp. 123–148
11 Feb examples of balls and bins models pp. 104–113 pp. 149–167
13 Feb Hamiltonian random graphs; basic probabilistic method pp. 113–119, 126–131 pp. 168–191
18 Feb more techniques for the probabilistic method pp. 131–138 pp. 192–210
20 Feb Lovász Local Lemma; conclusion pp. 138–141; 146–147 pp. 211–228