How can randomization make your algorithms faster? Learn basic design and analysis techniques as well as some classical results.

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.

NEW: Instructions for separate exams added (see the corresponding section).

### Interaction

All "official" interaction takes place at the regular meetings and by email with the instructor.

Students may organize other "unofficial" forms of interaction. However, neither the instructor nor university recommends any particular medium, platform, or tool, but rather want to raise the awareness that some tools, such as WhatsApp and Telegram, may not ensure complete privacy.

This page lists the media for interaction created/suggested by students in the course.

### Timetable

NOTE
No meetings on February 6 - 14 (the lecturer is travelling).

SCHEDULE
Date: Topics (Pages In Textbook, MU 1st Ed) [Pages In Lecture Notes]
15 Jan: course organization; basic probability (1–10) [4–25]
17 Jan: discrete random variables, expectations, Jensen's Inequality (10–14, 20–28) [26–38]
22 Jan: geometric distribution with applications; Markov's Inequality (29–38, 44–45) [39–52]
24 Jan: variance; Chebyshev's Inequality (45–57, 61–62) [53–69]
29 Jan: Chernoff bounds: proofs and examples ( 63–72) [70–89]
31 Jan: randomized routing in hypercube (72–79) [90–108]
5 Feb: routing in butterfly network; birthday paradox (78–83, 90–91) [109–122]
(Break, lecturer travelling)
19 Feb balls and bins, Poisson approximation (92–104) [123–148]
21 Feb: examples of balls and bins models (104–113) [149–167]
26 Feb: Hamiltonian random graphs; basic probabilistic method (113–119, 126–131) [168–191]
28 Feb: more techniques for the probabilistic method (131–138) [192–210]
28 Feb: Lovász Local Lemma; conclusion (138–141, 146–147) [211–228]

DateTimeLocation
Wed 15.1.2020
10:15 - 12:00
Fri 17.1.2020
10:15 - 12:00
Wed 22.1.2020
10:15 - 12:00
Fri 24.1.2020
10:15 - 12:00
Wed 29.1.2020
10:15 - 12:00
Fri 31.1.2020
10:15 - 12:00
Wed 5.2.2020
10:15 - 12:00
Fri 7.2.2020
10:15 - 12:00
Wed 12.2.2020
10:15 - 12:00
Fri 14.2.2020
10:15 - 12:00
Wed 19.2.2020
10:15 - 12:00
Fri 21.2.2020
10:15 - 12:00
Wed 26.2.2020
10:15 - 12:00
Fri 28.2.2020
10:15 - 12:00

### Material

EXERCISES SOLVED IN CLASS MEETINGS
- MU (1st ed.): 1.21, 2.4, 2.7(a, b), 2.20, 3.21, 4.11, 4.22, 5.6, 5.13, 6.1(a)

MATERIALS IN PDF
- Lecture Notes for the course Randomized Algorithms I, Spring 2020
- Errata to the course book
- Homework problems (coming gradually; tentative schedule: set I Jan 15, set II Jan 31, set III Feb 19)
- Solutions to homework problems (coming gradually, about 21 hours prior to the discussion session)
- Solution to course exam problem 4

## Other

### Separate exams

Forthcoming separate exams (including the renewal exam) for this course may be cancelled due to the coronavirus outbreak. Please consult the teacher for instructions on alternative ways to conduct the course.

See the Material section for an example of an exam question and a model solution.

### Conduct of the course

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

COMPLETING THE COURSE
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 in the TIMETABLE section; note the break at the begin 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 Thursday 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 will be no meetings on February 6 - 14 (lecturer travelling).

Homework is the key for learning. There will be 21 homework problems in total, grouped into 3 sets, each consisting of 7 problems (numbered exercises from the course book). The problems are announced on the MATERIAL section and discussed in the Friday meetings on Jan 24th, Feb 21st, and Feb 28th. 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 22 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. Dividing the sum of the homework grades by 4.5 and rounding up yields the number of earned course points. Solutions to the homework problems are revealed on the MATERIAL section about 20 hours prior to the meeting.

An example of time usage per week (for an average Joe, for an average grade): read the material 6 hours, attend the meetings 4 hours, solve homework problems 6 hours.

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.

### Results

In case the results will not get automatically published in WebOodi, the results for passed students (with student numbers) are in an attached PDF file. Contact mikko.koivisto@helsinki.fi if you want to know more about the grading.

### Description

• Master's programme in Computer Science is responsible for the course
• Tieteenalan syventävät opinnot CSM100000 / Core courses package and Discrete Algorithms (elective) CSM22100
• The course is available to students from other degree programmes

Algorithm Design and Analysis or equivalent knowledge.

Courses in the Discrete Algorithms study module. Courses in mathematics and statistics, especially in stochastic processes. Courses in statistical physics.

Can apply basic concepts of probability calculus in algorithmic context. Derives good upper bounds for the expected running time of simple randomized algorithms. Designs simple randomized algorithms that run fast or that return the correct output with high probability. Can apply the probabilistic method to show the existence of certain combinatorial objects.

First or second Spring of Master studies

The course is offered every second year in third period

The course introduces a variety of tools from probability theory for designing and analyzing randomized algorithms, and for analyzing 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.

Course book: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Michael Mitzenmacher and Eli Upfal. Cambridge University Press 2005. Chapters 1–6.

Recommended (optional) further reading: Randomized algorithms. Rajeev Motwani and Prabhakar Raghavan. Cambridge University Press 1995.

The following is the current plan for Spring 2018: teaching methods evolve from year to year.

There will be online lecture material covering the main concepts of each week; it is assumed the student has studied the material before attending the weekly contact teaching (2 x 2 hours).

The weekly contact teaching consists of two 2-hour meetings, during which the teacher gives brief lectures and answers questions from the students, example problems are solved together, and solutions to homework problems are discussed.

Students are given homework problems which students are supposed to solve individually, write down the solutions, and submit to the teacher before a given deadline. The teacher will grade the solutions and give individual (written) feedback.

The following is the current plan for Spring 2018: assessment practices evolve from year to year.