---

Graduate Course on Algorithms Theory
Winter Term 2001/02
Prof. Dr. Susanne Albers

---

Lectures

Location and time: Monday, 15-17, HS00-006, building 082 and Wednesday, 14-16, HS00-036, building 101. The Wednesday lecture will be held every two weeks.

Problem Sessions

Location and time: Wednesday, 14-16, HS00-036, building 101 and Wednesday, 9-11, SR01-016, building 101. The problem sessions will be held every two weeks.

Friday, April 5, 2002, 10-12, SR01-016, building 101.

Final Exam

Monday, February 18, 2002, 15-17, HS00-026, building 101.

Results Final Exam (Repetition)

Matrikel-No.	Grade	Status
1216517	5,0	not passed
1302249	5,0	not passed
1342803	2,0	passed
9316434	1,7	passed
9901679	1,0	passed

Results Final Exam

Matrikel-No.	Grade	Status
1216517	5,0	not passed
1302249	5,0	not passed
1314192	2,3	passed
1342803	5,0	not passed
1343760	3,0	passed
1347295	2,0	passed
9307251	1,0	passed
9316434	5,0	not passed
9328763	4,0	passed
9539977	5,0	not passed
9603105	5,0	no show
9701202	2,0	passed
9710247	4,0	passed
9716701	2,3	passed
9724356	2,0	passed
9900030	1,0	passed
9901657	2,0	passed
9902069	4,0	passed
9933393	5,0	not passed
9938616	3,0	passed

Course Description

The design and analysis of algorithms is a fundamental area of 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. We will concentrate on the following topics:

• Shortest paths algorithms
  
• Fibonacci heaps, amortized analysis
  
• Union-Find data structures
  
• Minimum spanning trees
  
• Universal and perfect hashing
  
• Skip lists and treaps
  
• Maximum flows; maximum matchings
  
• Minimum cuts
  
• Design techniques: Greedy algorithms, dynamic programming. divide-and-conquer
  
• Fast Fourier Transform
  
• RSA public-key cryptosystem
  
• String matching
  
• Online algorithms
  

Readings

• A.V. Aho, J.E. Hopcroft and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
• T.H. Cormen, C.E. Leiserson and R.L. Rivest. Introduction to Algorithms. MIT Press and McGraw-Hill, 1990.
• K. Mehlhorn. Data Structures and Algorithms, Volumes 1-3, Springer, 1984.
• T. Ottmann and P. Widmayer. Algorithmen und Datenstrukturen. Wissenschaftsverlag, 1990.

Credit Points

6 credit points can be earned for this course.

Exams

To earn credit points, students must complete successfully 50% of the homework assignments, present their solutions twice in the problem sessions and pass a final exam.

Slides

Shortest Paths
Amortized Analysis
Maximum Flow, Part 1
Maximum Flow, Part 2
Minimum Cuts

Recorded lectures (AOF)

Maximum Flow - Part 1 (Monday, Feb 04, 2002) Download (52 MB)
Maximum Flow - Part 2a (Wednesday, Feb 06, 2002) Download (19 MB)
Maximum Flow - Part 2b (Wednesday, Feb 06, 2002) Download (22 MB)
Minimum Cuts (Monday, Feb 11, 2002) Download (74 MB)

The recordings can be watched directly from the local computer pools or downloaded (ZIP). For watching the recordings at home, you will need the Lecturnity Player. (Please note that due to conversion problems, the audio quality is rather poor.)

Homework Assignments

Problem Set 1 , Problem Set 2 , Problem Set 3 , Problem Set 4 , Problem Set 5 , Problem Set 6 , Problem Set 7

Problem Sessions

Wednesday 9-11am

Baumgartner, Rafael
Bendig, Niels
Buerfent, Cedric
Busl, Sandra
Dragoaevic, Diana
Eppler, Jochen
Erhardt, Katharina
Exner, Mathias
Fischer, Joerg
Ganzert, Sven
Goetz, Georg
Goldschmidt, Bernd
Haag, Stefan
Hacker, Nadine
Huang, Chun
Jung, Dennis
Kalinnik, Natalija
Kavsek, Thomas
Keller, Christoph
Kemmerer, Steffen
Knapp, Markus
Krause, David
Kuhn, Jochen
Lange, Thorsten
Lu, Meng
Mueller, Marianne
Nold, Eveline
Pigorsch, Florian
Raufiz, Djamila
Reisert, Marco
Rottmann, Axel
Triebel, Tonio
Schmidt, Katharina
Schmidt, Thorsten
Stiefvater, Andreas
Ulisch, Pierre
Wagner, Michael
Wehr, Daniel
Wolf, Christoph
Wolf, Karsten
Yassin, Ashraf
Zeisberger, Uwe
Zuther, Sebastian

Wednesday 14-16pm

Abdel-Rahman, Atef
Anton, Konrad
Bauer, Matthias
Bender, Thomas
Deutschmann, Niklas
Dischinger, Paul-Stefan
Drescher, Michael
Fehr, Janis
Gontermann, Philipp
Greuel, Bastian
Hirth, Daniel
Jabbar, Shahid
Jacobs, Tobias
Jarvers, Philipp
Kelle, Sebastian
Kimmig, Angelika
Knur, Stefan
Koppa, Robert
Kuhland, Timo
Kupferschmid, Stefan
Kupriyenko, Wladimir
Löffler, Christoph
Meyer, Joachim
Munshey, M. Salman
Peng, Li
Pfaff, Patrick
Schulz, Janina
Song, Zhenyu
Staudenmaier, Armin
Wilhelm, Eva
Witte, Johannes