University of Konstanz
Prof. Dr. Ulrik Brandes

Design and Analysis of Algorithms (WS 2008/2009)


Design and analysis of efficient algorithms are omnipresent and thus their study is an important topic in computer science and beyond. This course provides a comprehensive overview of algorithmic questions and design techniques. We strive to convey an approach to algorithmics that begins with the systematic analysis of the problem, builds on an understanding of the common techniques to design algorithms, and results in an efficient solution to the problem.

This course is the basis for further studies in the field of algorithmics including graph algorithms. It provides advice on how to identify algorithmic problems in complex issues and how to design efficient and sophisticated algorithms for the resulting problems.

General Information

Lecture (U. Brandes, S. Cornelsen) Tue 10:15 - 11:45 (D 436)
Wed 14:30 - 16:00 (D 436)
Tutorial (M. Badent) Mon 14:05 - 15:35 (F 428)
Oral Exam 1st date: 18 Feb 2009, time: on appointment
2nd date: 16 Apr 2009, time: on appointment

Homework Assignments

Normally, the assignments are made available on this webpage as a PDF-file (in English) every Wednesday at 14:30.

The editing time for each homework is one week, therefore, normally, it is due on the next Wednesday at 14:30. The assignments have to be delivered in written form either in English or German. You can choose to either deposit them in the box for handout marked "Abgabe" in the staircase on E2, in front of the door to the rooms E 209-216, or to submit them electronically to the corresponding teaching assistant (as one PDF only). In the latter case, please follow the naming schema uXX_name1_name2.pdf, where XX indicates the number of the assignment. We will return the corrected and scored assignments in the tutorial. Whatever is not picked up will be placed back into the handout box marked "Rückgabe".

The requirements for the admittance to the final exam are 50 percent of the total score of the assignments, regular attendance at the tutorials, and the presentation of at least two of your solutions of the assignments. In writing up your assignments, be as clear, precise, and concise as possible. Understandability will be an important factor in the scoring of the assignments. There will be approximately twelve written assignments. Regular attendance is considered especially for borderline cases.

You are permitted and encouraged to work in groups of two.

No. Post Date Due Date Tutorial Download
01 22.10.2008 29.10.2008 03.11.2008 Assignment1.pdf
02 29.10.2008 05.11.2008 10.11.2008 Assignment2.pdf
03 05.11.2008 12.11.2008 17.11.2008 Assignment3.pdf
04 12.11.2008 19.11.2008 24.11.2008 Assignment4.pdf
05 19.11.2008 26.11.2008 01.12.2008 Assignment5.pdf
06 26.11.2008 03.12.2008 08.12.2008 Assignment6.pdf
07 03.12.2008 10.12.2008 15.12.2008 Assignment7.pdf
08 10.12.2008 07.01.2009 12.01.2009 Assignment8.pdf
09 17.12.2008 07.01.2009 12.01.2009 Assignment9.pdf
10 07.01.2009 14.01.2009 19.01.2009 Assignment10.pdf
11 14.01.2009 21.01.2009 26.01.2009 Assignment11.pdf
12 21.01.2009 28.01.2009 02.02.2009 Assignment12.pdf

Note that some links are only locally accessible.

Lecture Notes (in German) and Supplemental Course Materials


Further Information (in German)