##
Algorithm Theory

Graduate Course - Winter Term 2015/16

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: Friday, September 23, 2016, 14:00-15:00 in room 106-00-004.**

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 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
- Algorithm Theory Exam Fall 2012

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

- Monday 14:15-15:00 : 101-00-026
- Thursday 10:15-11:45 : 101-00-026

Exercises

Responsible for the exercises are
Mohamad Ahmadi and Oleksii Saukh.

Exercise tutorials will (usually) be weekly on
Mondays from 15:15-16:00. Any changes to the this schedule will be announced here.

- Group A (German Tutorial): Monday 15:15-16:00, 101-00-026

Tutor: Gabriel Kalweit (gabrielkalweit@gmail.com)**The suggested assignment of students can be found here: German Group**

- Group B (English Tutorial): Monday 15:15-16:00, 82-00-006 (Kinohörsaal)

Tutor: Hamid Ghodselahi(hghods@cs.uni-freiburg.de) and Yannic Maus**The suggested assignment of students can be found here: English Group**

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

### Sign up for Exercises

Exercise tutorials will take place weekly on Monday afternoon
15:15-16:00. In the tutorials the solutions of the previous week 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 Hamid Ghodselahi
(hghods@cs.uni-freiburg.de) to
sign up for the exercises. **Please sign up for
the exercises by Thursday evening, Oct 22.** 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 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 15/16 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 tutorial session on the Monday after your submission.

Exercise Material

### Lecture Material

Slides / Recordings