News
21.04.2022

Reexam ResultsThe results of the reexam are now visible after logging into this course webpage. If you want to inspect your reexam, please contact Prof. Bringmann. 
Algorithms and Data Structures (block course)
The course will cover basic and advanced data structures & algorithms and their analysis. Examples of data structures are cuckoo hashing, splay trees, randomized search trees, unionfind structures. In terms of problem domains, we cover graphs, strings, polynomials, and geometry. Furthermore, we discuss algorithm analysis techniques such as amortization and randomization, and general algorithm design principles.
Time & Date & Format
This core course will be offered in an intensive block version between February 28 and March 25. We strongly recommend that you participate in this course being present in the classroom. However, we also make it possible to take the course remotely, see Information>Virtual Guide.
The format of the course will be as follows: A "unit" consists of a 70 minute lecture, followed by 2 hours of group work on an exercise sheet, followed by a short discussion section with a tutor (tutorial). Typically we will have two units a day, the first starting at 9am, the second at 2pm, Monday through Friday, except for all Wednesdays, which will have only the morning unit.
The lecture will usually take place in room HS II in building E2 5. However, on some exceptions we change to different rooms, for details see Information>Timetable or see the list of topics below.
The tutorial will take place at 12:00 and at 17:00 in seminar room 014 in building E1 3. The seminar rooms 014 and 015 in building E1 3 are reserved throughout the whole lecture period as working spaces.
For information how to join the lecture or tutorial virtually, see Information>Virtual Guide.
This will be a very intensive course. Do not plan on doing anything else serious beside it.
Exams
Your final grade will be determined by your performance on a midterm exam (35%) and a final exam (65%). There will be a repeat exam for the final. Admittance to the exams requires active participation in the course.
Midterm: 11.3. 14:0017:00 GHH lecture hall
Endterm: 31.3. 16:3019:00 GHH lecture hall
ReExam: 13.4. 16:0019:00 HS002 E1 3
Prerequisites
The course requires basic knowledge in algorithms and data structures as covered for example by the course "Introduction to Algorithms and Data Structures" ("Grundzüge von Algorithmen und Datenstrukturen"). In particular, you should be familiar with correctness proofs of algorithms. Specific concepts that you should have basic familiarity with and should be able to apply include:
 pseudocode notation
 Onotation, running time analysis
 binary search
 basic sorting algorithms (e.g. mergesort)
 arrays, linked lists
 stacks, queues
 heaps / priority queues
 binary search trees, balanced binary search trees (e.g. AVL trees)
 definition of a graph
 graph traversal (e.g. depth first search / breadth first search)
In case you want to read up on these topics we recommend the script of the course "Introduction to Algorithms and Data Structures", see Information>Materials.
Tentative List of Topics
 greedy algorithms
 dynamic programming
 divide and conquer (e.g. master theorem, integer multiplication, FFT)
 randomized algorithms (e.g. quicksort, randomized search trees, hashing)
 amortization (e.g. Fibonacci heaps, union find)
 strings (e.g. pattern matching, tries)
 graphs (e.g. shortest paths, maxflow, matching)
 (highdimensional) geometry
Date  Lecturer  Topic  Comment 

28.2. 9am  RS  Intro: machine model, Onotation  
28.2. 2pm  RS  Divide and Conquer I: basic examples, master theorem  
1.3. 9am  RS  Divide and Conquer II: Strassen, Karatsuba  
1.3. 2pm  RS  Divide and Conquer III: ToomCook, FFT  
2.3. 9am  RS  Divide and Conquer IV: applications of FFT  
3.3. 9am  KB  Randomized I: model, quicksort, rank select  room change: HS002 E1 3 
3.3. 2pm  KB  Randomized II: dictionaries, randomized search trees, treaps  room change: HS III E2 5 
4.3. 9am  KB  Randomized III: hashing  room change: HS002 E1 3 
4.3. 2pm  KB  Randomized IV: more on hashing  
7.3. 9am  RS  Amortization I: intro  room change: HS III E2 5 
7.3. 2pm  RS  Amortization II: Fibonacci heaps / hollow heaps  
8.3 9am  RS  Amortization III: splay trees  
8.3. 2pm  RS  Amortization IV: union find  
9.3. 9am  KB  Strings I: DP for LCS  
10.3. 9am  KB  Strings II: string matching: RabinKarp, KnuthMorrisPratt  
10.3. 2pm  KB  Strings III: string matching continued, tries  
11.3. 9am  KB  Strings IV: suffix trees  
11.3. 2pm  Midterm Exam  GHH lecture hall  
14.3. 9am  RS  Graphs I: intro, BFS+DFS, Dijkstra  
14.3. 2pm  RS  Graphs II: shortest path: BellmanFord, FloydWarshall, Johnson, ...  
15.3. 9am  RS  Graphs III: more shortest paths  
15.3. 2pm  RS  Graphs IV: minimum spanning tree  
16.3. 9am  KB  Graphs V: maxflow: intro, maxflow mincut  
17.3. 9am  KB  Graphs VI: maxflow: FordFulkerson  
17.3. 2pm  KB  Graphs VII: maxflow: blocking flows  
18.3. 9am  KB  Graphs VIII: maximum matching  
18.3. 2pm  KB  Graphs IX: global mincut  
21.3. 9am  RS  Geometry I: orthogonal range searching  
21.3. 2pm  RS  Geometry II: sweep  
22.3. 9am  RS  Geometry III: point sets viewed globally  
22.3. 2pm  RS  Geometry IV: point sets viewed locally  
23.3. 9am  RS  Geometry V: arrangements, duality  room change: HS002 E1 3 
24.3. 9am  KB  SAT Algorithms  room change: HS001 E1 3 
24.3. 2pm  KB  Teaser: FineGrained Complexity  
25.3. 9am  KB  Teaser: Streaming and Sketching I  room change: HS002 E1 3 
25.3. 2pm  KB  Teaser: Streaming and Sketching II 
Literature
The course will not follow a particular book. The following is a list of literature that could be useful.
 [MS] K. Mehlhorn, P. Sanders: Algorithms and Data Structures  The Basic Toolbox, Springer, 2008 (ISBN: 9783540779773)
 [CLRS] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms  Second Edition, McGrawHill, 2001 (ISBN: 0262531968)
 [KT] J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005 (ISBN: 0321295358)
 [Meh] K. Mehlhorn, Data Structures and Algorithms, Vols. 13, Springer Verlag, 1984
 [Koz] D. Kozen, The Design and Analysis of Algorithms, Springer Verlag, 1991
 [GKP] R. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, AddisonWesley, 1994
 [CR] M. Crochemore, W. Rytter, Text Algorithms, Oxford University Press, 1994
 [Sch] A. Schrijver, A Course in Combinatorial Optimization, 2013
 [BKOS] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry, Springer Verlag, 2000
 [Eri] J. Erickson, Algorithms, 2019 (Free electronic version)