Exact Algorithms (WS 2010/11)
Contact:
| Joachim Kneis (kneis@informatik.rwth-aachen.de) |
| Somath Sikdar (sikdar@informatik.rwth-aachen.de) |
Language
The lecture will be held in English.Area
Theoretical Computer ScienceTime and Place
| Monday | 15:45 -- 17:15 | 5056 |
| Wednesday | 11:45 -- 13:15 | AH VI |
Weekly Tutorial
| Tuesday | 15:45 -- 17:15 | Room 6103, E2, Hörn |
- Sheets: 1 PS PDF - 2 PS PDF - 3 PS PDF - 4 PS PDF - 5 PS PDF - 6 PS PDF - 7 PS PDF - 8 PS PDF - 9 PS PDF - 10 PS PDF - 11 PS PDF - 12 PS PDF - 13 PS PDF - 14 PS PDF - Exam I - Exam II
- Solutions: 1 PS PDF - 2 PS PDF - 3 PS PDF - 4 PS PDF - 5 PS PDF - 6 PS PDF - 7 PS PDF - 8 PS PDF - 9 PS PDF - 10 PS PDF - 11 PS PDF - 12 PS PDF - 13 PS PDF - 14 PS PDF - Exam I - Exam II
Exam
The second exam took take place from 9:00 - 11:00 at Wednesday, Mar 23rd, 2011, in room 2350|009 (AH I).
Preliminary results:
Mat-Nr Points Grade 2????6 38 1.0 2????9 34 1.7 3????0 26 3.0 3????6 26 3.0If you want to take a look at your exam ("Klausureinsicht), just come to our office no later than April, 7th, 2011.
Slides
The slides (PDF) can be found here.Content
An introduction into exact algorithms für NP-hard problems, e.g.,- Branching
- Dynamic Programming
- Inclusion-exclusion
- Measure & Conquer
- Subset Convolution