Uni-Logo
Algorithms and Complexity
 

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, 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

Exam date: Monday August 25, 2014, 14:00-15:30

In 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:15-17:00 and 17:05-17:50: 101-00-026
  • Thursday 10:15-11:00 and 11:15-12:00: 101-00-026

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:15-18: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 101-00-026, and it will be held in English

Exercise sessions in English will take place in 106-00-007 and the suggested assignment of students can be found here: English Group .

Exercise sessions in German will take place in 101-00-026 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:15-18: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.uni-freiburg.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
Exercise solutions can be handed in either electronically to algo1314@informatik.uni-freiburg.de or on paper in the lecture of the day when the exercise solutions are due.

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