**26.07.2017**: The second oral exam will take place on**Monday, 16 October 2017**, from**14:00–16:00**in my office, room 112. If you would like to participate, please sign up until Friday, 13 October 2017, 16:00, using the Sign-up tool in KVV. The slots are assigned on a first come first serve basis.**07.07.2017**: The thirteenth problem set is available. This is the last problem set.**30.06.2017**: The twelfth problem set is available. This is the penultimate problem set.**23.06.2017**: The eleventh problem set is available.**16.06.2017**: The tenth problem set is available.**09.06.2017**: The ninth problem set is available.**02.06.2017**: The eighth problem set is available.**26.05.2017**: The seventh problem set is available.**22.05.2017**: The oral exam will take place on**Friday, 21 July 2017**, from**9:00–15:00**in my office, room 112. If you would like to participate, please sign up until Friday, July 14 2017, 15:00, using the Sign-up tool in KVV. The slots are assigned on a first come first serve basis. There will also be a make-up exam in October.**19.05.2017**: The sixth problem set is available.**12.05.2017**: The fifth problem set is available.**05.05.2017**: The fourth problem set is available.**28.04.2017**: The third problem set is available.**26.04.2017**: The second problem set is now also available in English.**22.04.2017**: The second problem set is available.**01.04.2017**: The first problem set is available.**02.02.2017**: The website is online. The first class will take place on**Friday, 21.04.2017****10:15 ct**. The exercise sessions will begin in the second week of classes.

The **problem sets will be available online**,
on this page.

- randomized algorithms
- algorithms for strings
- numerical algorithms
- approximation algorithms
- linear programming
- parametric search
- hashing
- complexity theory and lower bounds

**Friday, 21.04.2017**- Administrativa
- Introduction
- Recap linear programming
- Duality of linear programs

**Monday, 24.04.2017 (lecture given by Katharina Klost)**- Ellipsoid-algorithm

**Friday, 28.04.2017 (lecture given by Katharina Klost)**- Ellipsoid-Algorithm
- Duality
- Proof of strong duality using Farkas Lemma

**Fiday, 05.05.2017**- Fourier-Motzkin elimination
- Proof of Farkas Lemma via Fourier-Motzkin elimination

**Monday, 08. May 2017**- Two Player-Zero Sum Games and von Neumann's Minimax-Theorem

**Friday, 12. May 2017**- The complexity class PPAD
- Randomized Algorithms: MST

**Monday, 15. May 2017**- Randomized Algorithms: MST

**Friday, 19. May 2017**- KKT-algorithm for MST: Analysis
- Notes

**Monday, 22. May 2017**- Cuckoo-Hashing

**Friday, 26. May 2017**- Encoding Arguments
- Analysis of Cuckoo-Hashing

**Monday, 29. May 2017 (lecture given by Katharina Klost)**- Approximation algorithms
- Set Cover
- Inapproximability of the TSP

**Friday, 02. June 2017**- Cuckoo-Hashing: Addendum
- Metric TSP: Tree heuristic

**Tuesday, 06. June 2017**- Metric TSP: Christofides
- Euclidean TSP: Arora's PTAS

**Monday, 12. June 2017**- Euclidean TSP: Arora's PTAS
- Nice instances
- Portal-respecting tours
- Portal-respecting tours with at most two crossings

- Euclidean TSP: Arora's PTAS
**Friday, 16. June 2017**- Euclidean TSP: Arora's PTAS
- Portal-respecting tours using each portal at most twice
- Plane portal-respecting tours using each portal at most twice
- Finding an optimal portal-respecting tour
- Transformation of an optimal tour into a portal-respecting tour

- Euclidean TSP: Arora's PTAS
**Tuesday, 20. June 2017**- Euclidean TSP: Arora's PTAS
- Transformation of an optimal tour into a portal-respecting tour
- Random shifting
- Wrap-up of the analysis

- Euclidean TSP: Arora's PTAS
**Friday, 23. June 2017**- Parametrized algortihms
- A singly exponential algorithm for vertex cover
- Problems on trees and tree-like graphs

**Monday, 26. June 2017**- Tree-width: definition and properties

**Friday, 30. June 2017**- Tree-width: algorithmic applications

**Monday, 03. July 2017**- k-linked sets and tree-width

**Friday, 07. July 2017**- finding a tree decomposition of a graph

**Monday, 10. July 2017**- Complexity theory inside P: SETH and OV

**Friday, 14. July 2017**- SETH-hardness of Fréchet distance

**Monday, 17. July 2017**- SETH-hardness of Fréchet distance (continued)

**Friday 21. July 2017 (09:00–12:00, Room 112)**- oral exam

**Monday 16. October 2017 (plan, 14:00–16:00, Room 112)**- second oral exam

- T. H. Cormen, C. Leiserson, R. Rivest, C. Stein.
*Introduction to Algorithms, MIT Press 2009* - J. Kleinberg, E. Tardos.
*Algorithm Design, Addison-Wesley 2005.* - research papers.

- Basic knowledge of discrete mathematics and algorithms,
- "Advanced Algorithms", "Algorithms, Data Structures and Data Abstraction" or a comparable class,
- four successful semesters of BSc studies.

- participate regularly in the exercise sessions (at least 80% of the meetings);
- obtain at least 60% of all credit on the problem sets and present the solution to at least two problems in the exercise session; and
- pass the final exam.

The successful participation in the exercises and passing the final exam are independent of each other.

This class is graded. The final grades are based exclusively on the final exam. There will be an oral exam at the end of the semester, and a make up exam in October. The oral exam takes place on Friday, July 21, 9:00–15:00 in room 112. Please sign up one week in advance.

The class takes place **Monday, 10–12, in SR 005** and
**Friday, 10–12, in SR 046**, the exercises take place
**Tuesday, 16–18, SR 051**.
The exercises are conducted by Katharina Klost.

Office hours: Tuesday, 14–15, in room 112 and by appointment.

The problem sets are published on this site on a weekly basis. They
will appear **only online**.
The regular period for solving the problems is from Friday to Monday,
10 days later.
The solutions have to returned in class.
Please work in groups of two.

**Problem sets that are handed in after the due date receive no
credit.
**

No. | Out | Due | tex | Remarks | |
---|---|---|---|---|---|

1 | 01.04.2017 | 26.04.2017 | |||

2 | 22.04.2017 | 02.05.2017 | English version: [pdf] [tex] | ||

3 | 28.04.2017 | 08.05.2017 | |||

4 | 05.05.2017 | 15.05.2017 | |||

5 | 12.05.2017 | 22.05.2017 | |||

6 | 19.05.2017 | 29.05.2017 | |||

7 | 26.05.2017 | 06.06.2017 | Problem 1b) has been updated. | ||

8 | 02.06.2017 | 12.06.2017 | |||

9 | 09.06.2017 | 19.06.2017 | |||

10 | 16.06.2017 | 26.06.2017 | Problem 3 has been updated. | ||

11 | 23.06.2017 | 03.07.2017 | |||

12 | 30.06.2017 | 10.07.2017 | penultimate problem set | ||

13 | 07.07.2017 | 17.07.2017 | last problem set |