Graduate Course
"Algorithms Theory"
Winter term 2007/08
Prof. Dr. Susanne Albers
Sonja Lauer
Information on the exam
The results of the resit are now available in the online system. The bonus is already included where applicable.
On Wednesday, September 24, 14 - 15 h, students may view their exam papers (room 00 019, building 79).
Lectures
Monday, 14-16, HS 00-036, building 101, and Thursday, 14-16 , HS 00-036, building 101.
The Thursday lecture will be held every two weeks.
Course description
The design and analysis of algorithms is fundamental to computer science. In this course, we will study efficient algorithms for a variety of very basic problems and, more generally, investigate advanced design and analysis techniques. Central topics are some algorithms and data structures which have not at all or not sufficiently extensive been discussed in the undergraduate course Informatik II. These include, but are not limited to:
- Divide and conquer: geometrical divide and conquer, fast Fourier transform
- Randomization: randomized quicksort, probabilistic primality testing, RSA, univeral and perfect hashing
- Amortized analysis: binomial queues, Fibonacci heaps, union-find data structures
- Greedy procedures: shortest path, minimum spanning trees, bin packing problem, scheduling
- Graph algorithms
- Dynamic programming: matrix chain product problem, edit distance, longest common subsequence problem
- String matching and text compression: Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm, suffix trees, Huffman coding, Lempel-Ziv-Welch data compression algorithm
The knowledge of algorithms and data structures described in chapters 1 to 6 of the book "Algorithmen und Datenstrukturen" by Th. Ottmann und P. Widmayer is a prerequisite for understanding the topics of this course.
The exercise courses are supervised by Sonja Lauer and take place every two weeks at the following times:
- Mon 4 p.m. - 6 p.m.: SR 01-018, building 101
- Mon 4 p.m. - 6 p.m.: SR 02-017, building 052
- Tue 2 p.m. - 4 p.m.: SR 03-026, building 051 (English)
- Thu 11 a.m. - 1 p.m.: SR 00-034, building 051
- Thu 11 a.m. - 1 p.m.: SR 00-010/14, building 101
- Thu 4 p.m. - 6 p.m.: SR 00-034, building 051
Grouping for the exercise courses is no longer available
| Exerice Sheets | Release | Hand in by | |
| Assignment 1 | October 22, 2007 | November 5, 2007 | |
| Assignment 2 | November 5, 2007 | November 19, 2007 | |
| Assignment 3 | November 19, 2007 | December 3, 2007 | |
| Assignment 4 | December 3, 2007 | December 17, 2007 | |
| Assignment 5 | December 17, 2007 | January 14, 2008 | |
| Assignment 6 | January 14, 2008 | January 28, 2008 | |
| Assignment 7 | January 28, 2008 | February 11, 2008 | |
Please write down the solutions to the assignments and make sure to add your name, your matriculation number and the number of your group (or the name of the tutor) at the head of each sheet. Drop it into the box in building 051 (ground floor) which is labeled with the number of your exercise group.
Schedule
The schedule for the new year:| Week 10 (Jan. 7 - Jan. 11) | Mon: Lecture | Exercises | |
| Week 11 (Jan. 14 - Jan. 18) | Mon: Lecture | Thu: Lecture | |
| Week 12 (Jan. 21 - Jan. 25) | ------------- | Exercises | Thu: Lecture |
| Week 13 (Jan. 28 - Feb. 1) | Mon: Lecture | Thu: Lecture | |
| Week 14 (Feb. 4 - Feb. 8) | Mon: Lecture | Exercises | Thu: Lecture |
| Week 15 (Feb. 11 - Feb. 15) | ------------- | Thu: Exercise | |
Literature
The course is based on the following books. Further readings will be announced during the term.
- T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms. Second Edition MIT Press, 2001.
- Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen. 4. Auflage, Spektrum Akademischer Verlag, Heidelberg, 2002
Further material
The slides and the recordings of the lecture are available on our webserver.
The slides were developped in collaboration with Prof. Dr. Th. Ottmann.
Credit points
Successful participation in the course gives 6 credit points.
Final exam
The final exam will take place on March 19, 2008, 10:00 a.m. - 12:00 p.m. (Date and time of the resit will soon be announced.)
Students are eligible to participate in the final exam if they have
- completed 50 % of the exercises
- presented one exercise during the exercise sessions
The final grade will be upgraded by
- 1/3 grade if the student has achieved 50 % of the points attainable in the exercises
- 2/3 grade if the student has achieved 80 % of the points attainable in the exercises