Kaisa_2012_3_photo by Veikko Somerpuro

Anmäl dig
22.5.2019 kl. 09:00 - 16.6.2019 kl. 23:59



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

Describes several known results of approximation algorithms, including a few inapproximability results. Applies basic design principles to simple problems. Proves approximation guarantees for algorithms derived using basic design principles. Proves inapproximability (assuming P is not NP) results using simple polynomial-time reductions

First or second Spring of Master studies

The course is offered every second year / third period

Design techniques of approximation algorithms: greedy algorithms and local search, rounding data and dynamic programming, linear programming relaxations. Example problems: Vertex Cover, Set Cover, Metric Steiner Tree and TSP, Knapsack, Bin Packing.

Course book: D. P. Williamson, D. B. Shmoys: The design of Approximation Algorithms. Cambridge University Press, 2011. Chapters 1–7, excluding Chapter 6.

Chapters 1–5 and 7 of the course book are covered, except for Sections 2.6-7, 5.10-12, and 7.7, which are treated as recommended (optional) further reading.

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

It is assumed the student has studied the designated material in the course book in advance 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.

Erilliskokeiden luetteloissa käytetään seuraavia merkintöjä: (U): Koe on (ensimmäinen kurssia seuraava) erilliskoe ja samalla kurssikokeen/kurssikokeiden uusintakoe. Uusintakoesuorituksessa harjoituspisteet tms. otetaan huomioon. (HT): Kokeeseen voivat osallistua vain ne, jotka ovat suorittaneet kurssiin kuuluvat pakolliset harjoitustyöt (tms.). (HT/U): Kuten (U), mutta osallistumisoikeus on rajoitettu HT-kokeen tapaan. (ei erityismerkintää): Koe on erilliskoe; osallistumista ei ole rajoitettu, mutta kurssin vaatimat esitiedot on syytä ottaa huomioon.

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