Uni-Logo
Algorithms and Complexity
 


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 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

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