NewsCurrently, no news are available
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, 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
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.
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)
For participation in this course you must register also on this website, and this must happen until Wednesday, November 9.
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 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. 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.
Mock-up Midterm Exam
On Wednesday, December 21st, we will offer a mock-up 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 on-site 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.
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: 10.02.2022 2pm
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)