as announced during the lecture, the exam dates are:
as announced during the lecture, the exam dates are:
Algorithms and Data Structures
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 consists of two lectures per week (Tuesday + Friday, 10:15 - 12:00) plus tutorials once a week. The first lecture is on November 3.
You must register on this website until Sunday, November 8, so that we can assign you to a tutorial. You do not need to register to attend the first two lectures.
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".
Exercise sheets will be handed out on Tuesday and are due on the next Tuesday before the lecture. As an experiment, this course will have optional programming content. Every exercise sheet will consist of 3-4 regular exercises and 1-2 programming exercises. This means that you may choose to ignore the programming exercises, or you may focus on the programming exercises and only do few regular exercises.
Regular exercises are theory questions that must be answered by uploading a PDF on 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).
An exercise that asks you to design an algorithm is to be answered by (1) your algorithm in pseudocode, (2) a correctness proof, and (3) a running time analysis.
You may collaborate on solving the regular exercises in groups of up to 4 students, but every student must hand in a write-up 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. We will assign you to one of the following tutorial slots (when registering you can give your preferences): Wednesday 16-18 (Jasper), Thursday 10-12 (Hannaneh), Thursday 14-16 (Alejandro), Friday 14-16 (Sergei). Tutorials start in the week November 9-13.
Solutions to the the programming exercises will be submitted to an online judge. You are required to solve these exercises on your own.
For questions regarding programming aspects there is an office hour Monday 10-12, and you can ask questions on Discord. On November 5, 14:00-16:00 there will be a general introduction to the online judge and efficient coding in C++ given by Julian and Marian (a recording will be made available).
To be admitted to the exam, you need to achieve 50% of the points on the exercise sheets (where 100% means solving 4 exercises completely on each exercise sheet). There is no midterm exam.
There is an opportunity to obtain up to 15 % bonus points for the exam via a bonus sheet of regular and programming exercises (solutions need to be handed by 11:59 am on Sunday, February 7).
You can bring a cheat sheet to the exam (handwritten, A4 format, two-sided).
Endterm: Friday, February 26. 14:00-17:00, Günter-Hotz lecture hall E 2 2 (written, non-virtual exam)
Re-exam: Tuesday, March 30. 9:00-12:00, Günter-Hotz lecture hall E 2 2 (written, non-virtual exam)
Important: If you cannot be physically present for the exam, please contact us as soon as possible and provide proof/reason (e.g., entry into Germany from your current place of residence is not allowed).
Tentative List of Topics
|03 Nov||MK||Model + O-Notation + basic data structures|
|06 Nov||MK||Greedy + Dynamic Programming|
|10 Nov||MK||Divide and Conquer I: basic examples, master theorem|
|13 Nov||MK||Divide and Conquer II: Karatsuba, Toom-Cook|
|17 Nov||MK||Divide and Conquer III: FFT|
|20 Nov||KB||Randomized I: model, quicksort, rank select|
|24 Nov||KB||Randomized II: randomized search trees, treaps|
|27 Nov||KB||Randomized III: hashing|
|01 Dec||KB||Randomized IV: more hashing + Amortization I: intro|
|04 Dec||KB||Amortization II: splay trees|
|08 Dec||KB||Amortization III: Fibonacci heaps|
|11 Dec||KB||Amortization IV: union find|
|15 Dec||MK||Strings I: longest common subsequence, intro to string matching|
|18 Dec||MK||Strings II: string matching: Rabin-Karp, Knuth-Morris-Pratt|
|05 Jan||MK||Strings III: tries, suffix trees|
|08 Jan||KB||Graphs I: intro, depth first search, breadth first search, shortest paths|
|12 Jan||KB||Graphs II: more shortest paths|
|15 Jan||MK||Graphs III: maxflow: intro, maxflow mincut, Ford-Fulkerson|
|19 Jan||MK||Graphs IV: maxflow: further algorithms|
|22 Jan||MK||Graphs V: maximum matching|
|26 Jan||KB||Geometry I: intro, degeneracies, convex hull|
|29 Jan||KB||Geometry II: orthogonal range searching, segment trees|
|02 Feb||KB||Geometry III: sweep line, linear programming|
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)