Kaisa_2012_3_photo by Veikko Somerpuro

Enrol
24.9.2019 at 09:00 - 14.10.2019 at 23:59

Timetable

Description

Master's Programme in Computer Science is responsible for the course.

Modules the course belongs to: CSM100000 / Core courses package and Discrete Algorithms (elective) CSM22100

The course is available to students from other degree programmes.

Data Structures and Algorithms course or equivalent knowledge.

Courses in the Discrete Algorithms study module.

Is familiar with the most important principles of algorithm design. Solves simple recurrences. Can derive running time recurrence given a recursive algorithm. Can give examples of advanced recursive algorithms. Describes examples of amortized analysis in deriving worst case complexity of algorithms and amortized complexity of a data structure. Reduces related graph problems to maximum flow and describes the principles of how maximum flows are solved. Applies basic dynamic programming paradigm to shortest paths-alike problems and to variations of other problems used as typical examples during the course. Derives dynamic programming solutions given a recurrence as a hint. Derives the complexity of simple combinatorial algorithms using an appropriate analysis method. Describes some basic theorems related to NP-completeness. Can explain the P=NP problem. Knows many examples of NP-hard problems. Forms simple polynomial reductions between problems. Can give examples of approximation algorithms and randomized algorithms. Can explain the difference between best case, average case, expected case, and worst case complexities.

Recommended time/stage of studies for completion:

First Autumn

Term/teaching period when the course will be offered:

Yearly in Autumn / first period

General design principles of algorithms. Examples of central problems and typical solutions. Design and analysis of recursive algorithms. Amortized analysis. Dynamic programming. Flows. Reductions. NP-completeness. Introduction to other core algorithm design concepts.

Course book: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009.

Chapters 1, 2, 3, 22, 23, 24, 25 of the course book are recommended as background material before (during) attending the course.

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

There will be online lecture material covering the main concepts of each week; this material is assumed to be studied before attending the weekly contact teaching (lecture+study group+exercise).

The weekly contact lecture focuses on examples around the week's topic, and derivations and proofs not suitable for online lectures.

The weekly study groups are mostly online problem solving in small groups; the students teach each other the solutions found.

The weekly exercises work as self-evaluations and test the problem solving and analysis skills acquired. In the first weeks, one can replace problem solving and analysis questions by implementing the studied algorithms; this is aimed at students with insufficient background in the required mathematical skills to catch up.

The following is the current plan for Autumn 2017: assessment practices evolve from year to year.

The grading scale is 1...5.

The course exam has one question that tests general knowledge on the course topics. Points gathered from the exercises can replace this question.

One should obtain 30 points to pass the course with grade 1. Grade 5 is obtained with 50 points out of the maximum 60. A linear scale is applied for other grades.

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

There will be lectures, online lectures, study groups, and exercises, or some subcombination of these and possibly other forms of teaching.

Some activity during the course (e.g. in the form of gathering enough exercise points) is required to attend the course exam.

A separate exam can be taken with independent study.