Graduate Course
"Algorithms Theory"
Winter term 2009/10
Junior-Prof. Dr. Robert Elsässer
Lectures
Tuesday, 16-18, HS 00-026, building 101, and Wednesday, 16-18 , HS 00-026, building 101.
The Wednesday lecture will be held every two weeks.
student evaluations of the course
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.
Exercise courses
The exercise courses are supervised by Phillip Heidegger and
Marco Muñiz and take place every two weeks at the following times:
- Mon 9 - 11: SR 00-006, building 051 Jonas
- Mon 14 - 16: SR 00-031, building 051 Martin
- Mon 14 - 16: SR 02-017, building 052 Alexander
- Thu 11 - 13: SR 02-017, building 052 Bente
- Thu 16 - 18: SR 00-014, building 078 Alexander
The registration to one of the courses ended on Thursday 22.10.2009 15:00.
Grouping for the exercise courses
The assignments will follow the schedule:
| Exercice Sheets | Release | Hand in by | Sample Solution | |
| Assignment 0 | Solution 0 | |||
| Assignment 1 | October 29, 2009 | November 05, 2009 | Solution 1 | |
| Assignment 2 | November 12, 2009 | November 19, 2009 | Solution 2 | |
| Assignment 3 | November 26, 2009 | Dezember 03, 2009 | Solution 3 | |
| Assignment 4 | Dezember 10, 2009 | Dezember 17, 2009 | Solution 4 | |
| Assignment 5 | Dezember 23, 2009 | January 14, 2010 | Solution 5 | |
| Assignment 6 | January 21, 2010 | January 28, 2010 | Solution 6 | |
| Assignment 7 | February 04, 2010 | February 15, 2010 | Solution 7 | |
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. You can hand in your solution by mail, too. Please ask your tutor for his/her mail address.
Schedule
| Week 1 (19. - 23. Oct.) | Tue Lecture | Wed Lecture |
| Week 2 (26. - 30. Oct.) | Tue Lecture | exercise session (Sheet 0, no points) |
| Week 3 (2. - 6. Nov.) | Tue Lecture | Wed Lecture |
| Week 4 (9. - 13. Nov.) | Tue Lecture | exercise session (Sheet 1) |
| Week 5 (16. - 20. Nov.) | Tue Lecture | Wed Lecture |
| Week 6 (23. - 27. Nov.) | Tue Lecture | exercise session (Sheet 2) |
| Week 7 (30. - 4. Dec.) | Tue Lecture | Wed Lecture |
| Week 8 (7. - 11. Dec.) | Tue Lecture | exercise session (Sheet 3) |
| Week 9 (14. - 18. Dec.) | Tue Lecture | Wed Lecture |
| Week 10/1 (21. - 23. Dec.) | Tue Lecture | exercise session (Sheet 4, first half) |
| Week 10/2 (7. - 8. Jan.) | --- | exercise session (Sheet 4, second half) |
| Week 11 (11. - 15. Jan.) | Tue moved to 2010/01/20 | Wed Lecture |
| Week 12 (18. - 22. Jan.) | Tue Lecture | Wed Lecture / exercise session (Sheet 5) |
| Week 13 (25. - 29. Jan.) | Tue Lecture | Wed Lecture |
| Week 14 (1. - 5. Feb.) | Tue moved to 2010/02/03 | Wed Lecture / exercise session (Sheet 6) |
| Week 15 (8. - 12. Feb.) | Tue Lecture | Wed Lecture |
| Week 16 (15. - 19. Feb.) | --- | Wed exercise session (Sheet 7) |
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 were developped in collaboration with Prof. Dr. Th. Ottmann.
Credit points
Successful participation in the course gives 6 credit points.
Final exam
Date and time of the exam will be announced.
Students are eligible to participate in the final exam if they have
- 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