Algorithm Theory
Graduate Course  Winter Term 2013/14
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
 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
Exam date: Monday August 25, 2014, 14:0015:30In case you want to see your exam, you can do this on Tuesday, Oct 28, 15:00. If you want to do so, please send an email to Sebastian Daum to get an appointment.
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 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.
Schedule
Lectures
 Tuesday 16:1517:00 and 17:0517:50: 10100026
 Thursday 10:1511:00 and 11:1512:00: 10100026
Exercises
Responsible for the exercises are Sebastian Daum, Hamid Ghodselahi, and Oleksii Saukh. Exercise classes take place (roughly) every two weeks (usually) on Tuesdays.
 Tuesday 16:1518:00, roughly every second week
 Next exercise session: Tue Dec 14 (Problem Set 5)
 On Thu Dec 5 there will be only one exercise session, in room 10100026, and it will be held in English
Exercise sessions in English will take place in 10600007 and the suggested assignment of students can be found here: English Group .
Exercise sessions in German will take place in 10100026 and the suggested assignment of students can be found here: German Group.
Sign up for Exercises
Exercise tutorials will take place on Tuesday afternoon 16:1518:00 (roughly) every second week. It is not mandatory to hand in exercise solutions or to attend the exercise tutorials in order to be admitted to the exam. However, it is of course highly recommended to carefully do the exercises! If you plan to attend the exercise tutorials and/or if you plan to hand in your solutions, please send an email to algo1314@informatik.unifreiburg.de with the following information: your last name, first name, email address, matriculation number
 whether you're planning to hand in solutions and/or attend the tutorials
 whether you prefer an English or a German tutorial group
 additional requests: e.g., the names of people with whom you'd like to be in the same group
Old Exams
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
Exercise solutions can be submitted in English or German. Handing in exercise solutions is not mandatory in order to be admitted to the exam. However in order to have your solution corrected by one of the assistants, it has to be submitted in time.
Exercise Material
Problem Set  Assigned  Due  Solution / Additional Material  
Problem Set 1  29.10.2013  07.11.2013  Sample Solution 1  
Problem Set 2  05.11.2013  14.11.2013  Sample Solution 2  
Problem Set 3  19.11.2013  28.11.2013  Sample Solution 3  
Problem Set 4  26.11.2013  05.12.2013  Sample Solution 4  
Problem Set 5  19.12.2013  09.01.2014  Sample Solution 5  
Problem Set 6  21.01.2014  28.01.2014  Sample Solution 6  
Problem Set 7  05.02.2014  13.02.2014  Sample Solution 7 
Literature
 Thomas H. Cormen, Charles E. Leiserson, Robert L. Rivest, and Cliford Stein: Introduction to Algorithms, MIT Press
 Jon Kleinberg and Éva Tardos: Algorithm Design, Addison Wesley
 Thomas Ottmann and Peter Widmayer: Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag