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, union-find 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:30-10:00 (no break): 101-00-026
- Wednesday 16:15-18:00: 101-00-026, 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 | 16-18 | 051-00-006 | Evis Plaku | English |
| Wednesday | 16-18 | 101-00-026 | Fabian Reiter | German |
| Thursday | 16-18 | 051-00-006 | 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