Advanced Algorithmics (SS 13)

NP-hard problems are relevant in practical situations!

Complexity theory tells us that there are problems that seem to be inherently hard to solve. What can we do when faced which such a problem in practice? Over the decades, some useful techniques for tackling hard problems have emerged, for example

using heuristics to limit search spaces,
accepting wrong outputs with certain probability and
accepting suboptimal but still decent solutions.

We follow these approaches and develop theoretical foundations for solving hard problems sufficiently well and fast in practice.

This is an 8 ECTS advanced-level master course; find details in the official documents (INF-54-54-V-7).

Dates

Lectures and exercise sessions will be held throughout the reading period, that is from April 15th to July 19th. Individual sessions will take place weekly on

Wednesdays, 10:00 - 11:30 in 48-654 (lecture),
Wednesdays, 13:45 - 15:15 in 48-654 (exercises) and
Thursdays, 10:00 - 11:30 in 48-654 (lecture).

Note that we will not meet on public holidays, i.e. May 1st, May 9th, May 30th.

Exercises

There will be weekly exercise sheets with problems relating to the current lecture material. You can hand in your solutions for grading. We will discuss the exercise problems in weekly exercise sessions, provided sufficient participation. Your TA will be Raphael.

Participation is optional. Register in the first lecture or via email to Raphael.

Material

Week	Lectures	Exercises	Hands-On
I	L1	Sheet 1	Sheet 1, Data
II	L2, L3*	Sheet 2⁺	Sheet 2
III	L4	Sheet 3
IV	L5	Sheet 4⁺
V	L6, L7	Sheet 5⁺	Sheet 3
VI	L8, L9	Sheet 6	Sheet 4
VII	L10	Sheet 7
VIII	L11, L12	Sheet 8⁺	Sheet 5
IX	L13*, L14	Sheet 9⁺
X	L15, L16	Sheet 10
XI	L17, L18	Sheet 11
XII	L19, L20	Sheet 12
XIII	L21, L22	Session 11
XIV	L23		Sheet 06

^{* There have been changes since the lecture.}
^{+ There have been changes since hand-in.}

Lecture slides are only available for logged in users; please use the credentials given to you in class.

Exams

Examination procedure will be announced in the first lecture.

Advanced Algorithmics (SS 13)

Dates

Exercises

Material

Exams

Suggested Reading