Design and Analysis of Algorithms
(An English-language class)
This course is over.
Lectures and Tutorials (6 SWS/9 ECTS)
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.
Times
| Lectures: | Tuesday, 18:45-20:15, F 420 (Ulrik Brandes, Sven Kosub) |
| Wednesday 18:45-20:15, F 420 (Ulrik Brandes, Sven Kosub) | |
| Tutorials: | Friday 13:30-15:00, P 603 (Sabine Cornelsen, Natalie Indlekofer) |
| Oral exams: | 20 February 2013 (1st date) |
| 10 April 2013 (2nd date) |
Homework Assignments
Normally, the assignments are made available on this webpage as a PDF-file (in English) every Wednesday at 16:00.
The editing time for each homework is almost one week. 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 "Design and Analysis of Algorithms" in front of E 202 or to submit them electronically to the 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.
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 thirteen written assignments. Regular attendance is considered especially for borderline cases.
You are permitted and encouraged to work in groups of two.
- Assignment 1 - Post date: 10/24/12 - Due date: 10/31/12 (PDF, 130 KB)
- Assignment 2 - Post date: 10/31/12 - Due date: 11/07/12 (PDF, 145 KB)
- Assignment 3 - Post date: 11/07/12 - Due date: 11/14/12 (PDF, 120 KB)
- Assignment 4 - Post date: 11/14/12 - Due date: 11/21/12 (PDF, 140 KB)
- Assignment 5 - Post date: 11/21/12 - Due date: 11/28/12 (PDF, 122 KB)
- Assignment 6 - Post date: 11/28/12 - Due date: 12/05/12 (PDF, 210 KB)
- Assignment 7 - Post date: 12/05/12 - Due date: 12/12/12 (PDF, 142 KB)
- Assignment 8 - Post date: 12/12/12 - Due date: 12/19/12 (PDF, 148 KB)
- Assignment 9 - Post date: 12/19/12 - Due date: 01/09/13 (PDF, 130 KB)
- Assignment 10 - Post date: 01/09/13 - Due date: 01/16/13 (PDF, 148 KB)
- Assignment 11 - Post date: 01/16/13 - Due date: 01/23/13 (PDF, 113 KB)
- Assignment 12 - Post date: 01/23/13 - Due date: 01/30/13 (PDF, 102 KB)
- Assignment 13 - Post date: 01/30/13 - Due date: 02/06/13 (PDF, 135 KB)
Lecture Notes and Supplemental Course Material in German
- Lecture notes from the same course long time ago (PDF, 1 MB)
- Asymptotic order of growth 1 (lecture notes of Discrete Structures) (PDF, 95 KB)
- Asymptotic order of growth 2 (lecture notes of Algorithms and Data Structures) (PDF, 446 KB)
- Prüfer sequence (lecture notes of Discrete Structures) (PDF, 46 KB)
- Network flows (PDF, 264 KB)
Lecture Notes from a Previous Course and Supplemental Course Material in English
- On the algorithm of Goldberg and Tarjan (PDF, 419 KB)
- On string matching (PDF, 298 KB)
- On how to compute Boyer-Moore shifts (PDF, 62 KB)
- On pivoting (Linear Programming) (PDF, 34 KB)
- Mechtild Stoer, Frank Wagner: A Simple Min-Cut Algorithm. Journal of the ACM, 44(4):585-591, 1997
- Joseph Cheriyan and Kurt Mehlhorn: An Analysis of the Highest-Level Selection Rule in the Preflow-Push Max-Flow Algorithm. Information Processing Letters, 69:239-242, 1999
Textbooks
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2nd edition, McGraw-Hill, 2001.
- Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen. BI-Wissenschaftsverlag, 1993.
- Dieter Jungnickel: Graphen, Netzwerke und Algorithmen. BI-Wissenschaftsverlag, 1994.
- Jon M. Kleinberg, Eva Tardos: Algorithm Design. Addison-Wesley, 2006.
- Michael T. Goodrich, Roberto Tamassia: Algorithm Design. Wiley, 2002.