News
18.11.2020

New Tutorial LinksThe links to the tutorial meetings have changed! Please see the Virtual Guide section of the course website for the updated links (you need to be logged in to access it). 
09.11.2020

Tutorials and Zoom's link for Lecture The link for tomorrow's lecture can be found in the Virtual Guide Section of the course website (you need to be logged in to access it).  The tutorial slots have been assigned, we will post the links for the tutorials soon. 
03.11.2020

Important notice for students of the programs Embedded Systems and CuKStudents of the programs Embedded Systems and Computer und Kommunikationstechnik, please note: This course counts as Advanced Lecture for Master students, and as Vorlesung für den Wahlpflichtbereich for Bachelor students. 
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, 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 consists of two lectures per week (Tuesday + Friday, 10:15  12:00) plus tutorials once a week. The first lecture is on November 3.
Registration
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.
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)
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
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 34 regular exercises and 12 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
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 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. We will assign you to one of the following tutorial slots (when registering you can give your preferences): Wednesday 1618 (Jasper), Thursday 1012 (Hannaneh), Thursday 1416 (Alejandro), Friday 1416 (Sergei). Tutorials start in the week November 913.
Programming Exercises
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 1012, and you can ask questions on Discord. On November 5, 14:0016: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).
Exam
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 will be an opportunity to obtain up to 15 % bonus points for the exam via a bonus sheet of regular and programming exercises towards the end of the lecture (solutions need to be handed in within 48 h).
Endterm: tba. (written, nonvirtual exam)
Reexam: tba. (written, nonvirtual exam)
Tentative List of Topics
03 Nov  MK  Model + ONotation + 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, ToomCook 
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  Amortization I: intro 
04 Dec  KB  Amortization II: splay trees 
08 Dec  KB  Amortization III: Fibonacci heaps / hollow heaps 
11 Dec  KB  Amortization IV: union find 
15 Dec  MK  Strings I: longest commons subsequence, rolling hashes 
18 Dec  MK  Strings II: string matching: RabinKarp, KnuthMorrisPratt 
05 Jan  MK  Strings III: tries, suffix trees 
08 Jan  KB  Graphs I: intro, BFS+DFS, Dijkstra 
12 Jan  KB  Graphs II: shortest path: BellmanFord, FloydWarshall, ... 
15 Jan  MK  Graphs III: maxflow: intro, maxflow mincut, FordFulkerson 
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 
05 Feb  MK  Outlook 
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)