Uni-Logo
Algorithms and Complexity
 

Algorithm Theory
Graduate Course - Winter Term 2014/15
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, 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

Post-Exam Review: Thursday, October 1, 106-00-015, --> 14:00-16:00

Exam date: August 25 (Tuesday), 2015, 09:00-10:30.
Exam place: 101-01-009/13.
The exam questions will be in English and German. It will be ok to answer the questions in German. Everyone is allowed to bring 5 handwritten A4 pages (corresponds to 5 single-sided A4 sheets!), 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 fall 2012 exam was based was not the same as this time.

Schedule

Lectures

Thursday, Feb. 12: No lecture, question and answer session, discussion of last exercise sheet
  • Monday 14:15-15:00: 101-00-026
  • Thursday 10:15-11:45: 101-00-026

Exercises

Responsible for the exercises are Hamid Ghodselahi and Yannic Maus. Exercise tutorials will (usually) be weekly on Mondays from 15:15-16:00. Any changes to the this schedule will be announced here.

Sign up for Exercises

Exercise tutorials will take place weekly on Monday afternoon 14:15-15:00. In the tutorials the solutions of the previous week are discussed. It is mandatory to hand in hard copied exercise solutions. In order to be admitted to the exam, you need to have 50% of all exercise points. Exercises should be done in groups of 2 students. Please team up with a colleague and send an email (including name and matriculation number of both students) to Hamid Ghodselahi (hghods@cs.uni-freiburg.de) to sign up for the exercises. Please sign up for the exercises by Thursday evening, Oct 23. We might be able to offer German exercise tutorials (there will definitely be English tutorials). In case you'd prefer to have the exercise tutorials in German, please also indicate this in your email when signing up.

Timeline

The new exercise sheet will be released on this website on Wednesdays; your solution is supposed to be handed in (hard copied) until Thursday, 10:00 a.m., in the week following its release date. You can hand it in either before the lecture or in the respective letter box (Algorithm Theory WS 14/15 Group A (German) or B (English)) in building 051, first floor. Your tutor will return the corrected exercise sheet in the tutorial session on the Monday after your submission.

Exercise Material

Problem Set Assigned Due (10:00 a.m) Solution / Additional Material
Exercise 01 (Divide and Conquer) 22.10.2014 30.10.2014 -
Exercise 02 (FFT and DFT) 29.10.2014 6.11.2014 -
Exercise 03 (Greedy TSP and Matroids) 05.11.2014 13.11.2014 -
Exercise 04 (Dynamic Programming) 12.11.2014 20.11.2014 -
Exercise 05 (Edit Distance & Binomial Heap) 19.11.2014 27.11.2014 No Sample Solution
Exercise 06 (Fibonacci Heap & Amortized Analysis) 26.11.2014 4.12.2014 -
Exercise 07 (Union-Find) (updated 8.12.2014) 03.12.2014 11.12.2014 -
Exercise 08 (Amortized Analysis, Ford-Fulkerson) 10.12.2014 18.12.2014 -
Exercise 09 (Network Flows) 17.12.2014 08.01.2015 -
Exercise 10 (Matching & Probability Theory) 07.01.2015 15.01.2015 -
Exercise 11 (Primality Testing, Randomized Min-Cut) 14.01.2015 22.01.2015 -
Exercise 12 (Randomized Min-Cut, Approx. Alg.) 21.01.2015 29.01.2015 -
Exercise 13 (Approximation Algorithms) 29.01.2015 05.02.2015 -
Exercise 14 (Online & Parallel Algorithms) 05.02.2015 12.02.2015 -

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.

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