Algorithm Theory
Graduate Course  Winter Term 2012/13
Fabian Kuhn
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 basic problems and, more generally, investigate advanced design and analysis techniques. Central topics are algorithms and data structures that go beyon what has been considered in the undergraduate course Informatik II. Basic algorithms and data structures knowledge, comparable to what is done in Informatik II, or , is therefore assumed. The topics of the course include (but are not limited to):
 Divide and conquer: geometrical divide and conquer, fast fourier transformation
 Randomization: median, randomized quicksort, probabilistic primality testing, etc.
 Amortized analysis: binomial queues, Fibonacci heaps, unionfind data structures
 Greedy algorithms: minimum spanning trees, bin packing problem, scheduling
 Dynamic programming: matrix chain product problem, edit distance, longest common subsequence problem
 Graph algorithms: network flows, combinatorial optimization problems on graphs
Exam
The exam questions will be in English, however it will be ok to answer the questions in German. Everyone is allowed to bring 5 handwritten A4 pages, a pocket calculator, and a dictionary to the exam. No other material is allowed!To get a feeling for the type of questions, here are the last two exams: Note however that the set of topics of the 2011/12 lecture on which the second exam was based was not the same as this time.
Course Evaluation
Please fill out the online course evaluation form.Schedule
Lectures
 Tuesday 08:3010:00 (no break): 10100026
 Wednesday 16:1518:00: 10100026, every second week
Wednesday lecture dates: 24.10., 31.10., 14.11., 28.11., 12.12., 9.1., 23.1., 6.2.
Exercises
The exercises are supervised by Hamid Ghods. Exercise classes take place every two weeks in the weeks where there is no lecture.
Day  Time  Room  Teaching Assistant  Language 
Wednesday  1618  05100006  Evis Plaku  English 
Wednesday  1618  10100026  Fabian Reiter  German 
Thursday  1618  05100006  Hamid Ghods  English 
(Here is a list of the tutorial groups (Update November 20). The password is the last name of the lecturer)
Lecture Material
Slides / Recordings

All slides and recordings can be found on our webserver.
Partly, the slides are modifications of earlier versions of Prof. Dr. T. Ottmann and Prof. Dr. S. Albers.
Exercises
Problem Set  Assigned  Due  Solution / Additional Material  
Problem Set 1  24.10.2012  31.10.2012  
Problem Set 2  31.10.2012  14.11.2012  
Problem Set 3  14.11.2012  28.11.2012  
Problem Set 4  28.11.2012  12.12.2012  
Problem Set 5  12.12.2012  9.1.2013  
Problem Set 6  9.1.2013  23.1.2013  
Problem Set 7  24.1.2013  6.2.2013  
Literature
 Thomas H. Cormen, Charles E. Leiserson, Robert L. Rivest, and Cliford Stein: Introduction to Algorithms, MIT Press
 Thomas Ottmann and Peter Widmayer: Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag
 Jon Kleinberg and Éva Tardos: Algorithm Design, Addison Wesley
 lecture of last year: Alex Souza: Graduate Course "Algorithm Theory", Winter Term 2011/12