Algorithm Theory
Graduate Course - Winter Term 2016/17
Fabian Kuhn

 

Exam Spring 2017

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.2017, 9:00-11:00
Exam place: Building 101, Room 026

The exam questions will be in English. 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:

• Algorithm Theory Exam Spring 2017
• Algorithm Theory Exam Fall 2016
• Algorithm Theory Exam Spring 2016
• Algorithm Theory Exam Fall 2015
• Algorithm Theory Exam Spring 2015
• Algorithm Theory Exam Fall 2014
• Algorithm Theory Exam Spring 2014
• Algorithm Theory Exam Fall 2013
• Algorithm Theory Exam Spring 2013

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.

Schedule

Lectures

• Monday 14:15-16:00 : 101-00-026
• Thursday 10:15-12:00 : 101-00-026

Exercises

Responsible for the exercises are Mohamad Ahmadi and Philipp Bamberger.

Exercise classes take place (roughly) every second week (usually) on Mondays (tentative).

• Group A (German Tutorial): Monday 14:15-16:00, 101-00-026
  Tutor: Philipp Bamberger (Philipp.Bamberger@cs.uni-freiburg.de)
  
• Group B (English Tutorial): Monday 14:15-16:00, 51-00-006
  Tutor: Mohamad Ahmadi (mahmadi@cs.uni-freiburg.de)
  

Sign up for Exercises

Exercise tutorials will take place on Mondays afternoon 14:15-16:00 (roughly) every second week. In the tutorials the solutions that have been handed in are discussed. In order to be admitted to the exam, you need to have 50% of all exercise points. Exercises could be done in groups of 2 students. Please send an email (including name and matriculation number of both students) to Mohamad Ahmadi (mahmadi@cs.uni-freiburg.de) to sign up for the exercises. Please sign up for the exercises by Thursday evening, Oct. 20. Please indicate in your email when signing up whether you prefer an English or a German tutorial group.

Timeline

The new exercise sheet will be released on this website on Thursdays every second week; your solution is supposed to be handed in until Thursday, 10:00 a.m., in the week in which the solution is due. You can hand it in either before the lecture or in the respective letter box (Algorithm Theory WS 16/17 Group A (German) or B (English)) in building 051, first floor. You could also send it by E-mail to your tutor. Your tutor will return the corrected exercise sheet in the next tutorial session when the corresponding solutions are discussed.

Exercise Material

	Problem Set	Assigned	Due (10:15)	Solution / Additional Material
	Problem Set 1 (Landau-Notation - Divide & Conquer)	20.10.2016	27.10.2016	Sample Solution
	Problem Set 2 (Divide & Conquer - FFT - Greedy)	27.10.2016	10.11.2016	Sample Solution
	Problem Set 3 (D&C - Greedy - Dynamic Programming)	10.11.2016	24.11.2016	Sample Solution
	Problem Set 4 (Amortized Analysis, Data Structures)	24.11.2016	08.12.2016	Sample Solution
	Problem Set 5 (Network Flow)	08.12.2016	22.12.2016	Sample Solution
	Problem Set 6 (Matching, Probability Theory)	22.12.2016	19.01.2017	Sample Solution
	Problem Set 7 (Randomized Algorithms)	19.01.2017	30.01.2017	Sample Solution
	Problem Set 8 (Approximation and Online Algorithms)	30.01.2017	06.02.2017	Sample Solution

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