Uni-Logo
Algorithms and Complexity
 


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.


Exercise courses

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

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