### Tidsschema

### Beskrivning

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

The grading scale is 1...5.

One can earn up to 12 points from homework problems and up to 48 points from the course exam, up to 60 points in total. Alternatively, one can earn up to 60 points from a separate exam, offered outside the course's contact teaching periods.

One needs 24 points to pass the course with grade 1 and 48 points to get grade 5. A linear scale is applied for other grades.

Deviations from the scheme are possible depending on the difficulty of the exam.

By collecting a sufficient amount of points from homework assignments and course exam. Attending contact teaching activities is voluntary.

A separate exam can be taken with independent study.