Kaisa_2012_3_photo by Veikko Somerpuro

Enrol
22.5.2019 at 09:00 - 16.6.2019 at 23:59

Timetable

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

Separate exams last 3 hours and 30 minutes. Renewal exam (marked with "(U)") is the first separate exam after the course and also a renewal exam of course exam(s). In a renewal exam the points student has earned during the course are taken into account. Exams marked with "(HT)" are allowed only to students who have completed the obligatory projects or other exercises included in those courses. Exams marked with "(HT/U)" are renewals to students who have completed the obligatory projects during the course. Separate exams might cover different area than the lectured course. Check the course web page and contact the responsible teacher if in doubt.

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.