NewsCurrently, no news are available
Algorithm 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, union-find 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 will make it possible to take the course remotely, but the specific modalities are not yet fixed.
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. 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.
This will be a very intensive course. Do not plan on doing anything else serious beside it.
The course requires basic knowledge in algorithms and data structures as covered for example by the introductory course "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
- O-notation, 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 introductory course "Grundzüge von Algorithmen und Datenstrukturen".
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.
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)
- (high-dimensional) geometry
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, McGraw-Hill, 2001 (ISBN: 0262531968)
- [KT] J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005 (ISBN: 0-321-29535-8)
- [Meh] K. Mehlhorn, Data Structures and Algorithms, Vols. 1-3, 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, Addison-Wesley, 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)