Algorithm Theory
Graduate Course - Winter Term 2017/18
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 beyond 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
- Amortized analysis: Fibonacci heaps, union-find data structures
- Greedy algorithms: minimum spanning trees, scheduling, matroids
- Dynamic programming: matrix chain product problem, edit distance, longest common subsequence problem
- Graph algorithms: network flows, combinatorial optimization problems on graphs
Exam
Exam date: 28.03.2018, 9:00-11:00
Exam place: Building 101, Room 026
Reminder: Please remember to bring your student ID with you to the exam!
The exam questions will only be given in English (it is OK to write the answers in German). Everyone is allowed to bring a summary consisting of at most 5 A4 pages (corresponds to 5 single-sided A4 sheets!) and a dictionary to the exam. No other material is allowed!
Here you find a list of previous exams.
Sample solutions of previous exercise sheets are now available from the websites of previous years.
Forum
If you have a question to the lecture or the exercises, please use the forum instead of writing an email. Then all of us and also your colleagues see the question and can answer to it. Feel free to also use the forum to discuss anything related to the topics and organization of the lecture.
Announcements
If you would like to have a look at the corrected 7th exercise sheet, you can pick it up (together with any other exercise sheets you did not pick up in the class yet) at one of our offices (see tutorial section below).
Schedule
- Monday 14:15-16:00 (lecture and tutorials alternating weekly)
- Lecture: 101-00-026
- Exercises: 101-00-026 (German) 051-00-006 (English)
- Thursday 10:15-12:00
- Lecture: 101-00-026
Tutorials
- German tutorial: Monday 14:15-16:00, 101-00-026
Tutor: Philipp Schneider (Philipp.Schneider@cs.uni-freiburg.de)
Tutorial Website - English tutorial: Monday 14:15-16:00, 51-00-006
Tutor: Mohamad Ahmadi (mahmadi@cs.uni-freiburg.de)
Exercise Material
Submit your exercise solutions via one of the following options:
- Hand in as hard copy on Thursday 10.15 am in lecture.
- Drop hard copy into the Algorithm Theory [German/English] box in building 051.
- Send a digital version per mail to your tutor (see above) with the subject 'AlgoTheo1718_[SheeetNumber]' (Latex preferred, Word is ok, Scans must be readable, check before).
Regarding the exercise sheets and sample solutions: If you spot any ambiguities or erros or simply feel that some steps need more explanation, please contact us and we will try to correct or improve the according passages.
Exercise sheet | Assigned | Due | Solution | |
Exercise Sheet 1 (Landau-Notation - Divide & Conquer) | 23.10.2017 | 02.11.2017 | Solution Sheet 1 | |
Exercise Sheet 2 (Divide & Conquer - FFT - Greedy) | 02.11.2017 | 16.11.2017 | Solution Sheet 2 | |
Exercise Sheet 3 (Dyn. Programming - Amort. Analysis) | 16.11.2017 | 30.11.2017 | Solution Sheet 3 | |
Exercise Sheet 4 (Data Structures - Graph Algorithms) | 30.11.2017 | 14.12.2017 | Solution Sheet 4 | |
Exercise Sheet 5 (Matching - Probability Theory) | 11.12.2017 | 11.01.2018 | Solution Sheet 5 | |
Exercise Sheet 6 (Randomized Algorithms) | 11.01.2018 | 25.01.2018 | Solution Sheet 6 | |
Exercise Sheet 7 (Approximation - Online Algorithms) | 25.01.2018 | 05.02.2018 | Solution Sheet 7 |
Lecture Material
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.
Literature
- Jon Kleinberg and Éva Tardos: Algorithm Design, Addison Wesley
- 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