News
01.02.2023

Exam RegistrationYou can now check on your personal status page weither you qualified for the exam. The release of the detailed points and feedback of assingment 7 may take some more time. Remember to register for the exam in the LSF (HISPOS) until friday 03.02.23. Also... Read more You can now check on your personal status page weither you qualified for the exam. The release of the detailed points and feedback of assingment 7 may take some more time. Remember to register for the exam in the LSF (HISPOS) until friday 03.02.23. Also register on the course site until wednesday.
Assignment 8 and the sample solution of assignment 7 are available now.

Algorithms and Data Structures
The course will cover some basic and advanced data structures & algorithms along with their performance 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
The lectures will take place in lecture hall 002 in building E1 3 Mondays and Wednesdays in the slot 16:00  18:00.
The tutorial will take place also in lecture hall 002 on Thursdays and Fridays 8:30  10:00. Your are free in the choice of the tutorial.
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.
Prerequisites
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
 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)
Registration
For participation in this course you must register also on this website, and this must happen until Wednesday, November 9.
Exercises
Exercise sheets will be given out typically on Mondays and are due on the following Monday before the lecture. Your solutions are to be uploaded as a PDF to this course website. You can produce a PDF by writing in LaTeX, writing in a common word processor like Word, or by taking a scan or a photo of your handwritten solution (if you take a photo, take special care that the PDF is readable).
You may collaborate on solving the exercises, but every student must hand in a writeup in their own words. You are required to state your collaborators and all sources (books, papers, course notes, web pages, etc.) that you use to arrive at your solutions.
The solutions to these exercises are presented in the tutorial. You are free to choose the Thursday or Friday tutorial.
There will be approximately 12 exercise sheets. 6 clearly specified exercise sheets will be graded. You must have achieved at least 50% of the at that time possible points to qualify for an exam.
Mockup Midterm Exam
On Wednesday, December 21st, we will offer a mockup midterm exam in the afternoon instead of the usual lecture. The campus will be closed during that week. So you can take the exam at home. It is up to you to simulate the usual onsite exam conditions, in particular that you refrain from using illicit help or use too much time. The exam will be graded but the results will not count towards the final grade.
Exams
Your final grade will be determined solely by your performance on the final exam or the repeat exam. Admittance to the exams requires 50% of the exercise sheet points, as explained above. The dates will be as follows:
Endterm: Friday, Febraruy 10th 2023, 14:1516:45 lecture hall 002 in building E1 3.
ReExam: Friday, March 24th 2023, 14:1516:45 lecture hall 002 in building E1 3.
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
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)