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 at Electures. 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.
The resit will be on September 15, 2008, 2:00 - 4:00 p.m.

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