Algorithms and Data Structures (block course)

Algorithms 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 also make it possible to take the course remotely, see Information->Virtual Guide.

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 (tutorial). 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.

The lecture will usually take place in room HS II in building E2 5. However, on some exceptions we change to different rooms, for details see Information->Timetable or see the list of topics below.

The tutorial will take place at 12:00 and at 17:00 in seminar room 014 in building E1 3. The seminar rooms 014 and 015 in building E1 3 are reserved throughout the whole lecture period as working spaces.

For information how to join the lecture or tutorial virtually, see Information->Virtual Guide.

This will be a very intensive course. Do not plan on doing anything else serious beside it.

Exams

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.

Midterm: 11.3. 14:00-17:00 GHH lecture hall

Endterm: 31.3. 16:30-19:00 GHH lecture hall

Re-Exam: 13.4. 16:00-19:00 HS002 E1 3

Prerequisites

The course requires basic knowledge in algorithms and data structures as covered for example by the course "Introduction to Algorithms and Data Structures" ("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 course "Introduction to Algorithms and Data Structures", see Information->Materials.

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

Date	Lecturer	Topic	Comment
28.2. 9am	RS	Intro: machine model, O-notation
28.2. 2pm	RS	Divide and Conquer I: basic examples, master theorem
1.3. 9am	RS	Divide and Conquer II: Strassen, Karatsuba
1.3. 2pm	RS	Divide and Conquer III: Toom-Cook, FFT
2.3. 9am	RS	Divide and Conquer IV: applications of FFT
3.3. 9am	KB	Randomized I: model, quicksort, rank select	room change: HS002 E1 3
3.3. 2pm	KB	Randomized II: dictionaries, randomized search trees, treaps	room change: HS III E2 5
4.3. 9am	KB	Randomized III: hashing	room change: HS002 E1 3
4.3. 2pm	KB	Randomized IV: more on hashing
7.3. 9am	RS	Amortization I: intro	room change: HS III E2 5
7.3. 2pm	RS	Amortization II: Fibonacci heaps / hollow heaps
8.3- 9am	RS	Amortization III: splay trees
8.3. 2pm	RS	Amortization IV: union find
9.3. 9am	KB	Strings I: DP for LCS
10.3. 9am	KB	Strings II: string matching: Rabin-Karp, Knuth-Morris-Pratt
10.3. 2pm	KB	Strings III: string matching continued, tries
11.3. 9am	KB	Strings IV: suffix trees
11.3. 2pm		Midterm Exam	GHH lecture hall
14.3. 9am	RS	Graphs I: intro, BFS+DFS, Dijkstra
14.3. 2pm	RS	Graphs II: shortest path: Bellman-Ford, Floyd-Warshall, Johnson, ...
15.3. 9am	RS	Graphs III: more shortest paths
15.3. 2pm	RS	Graphs IV: minimum spanning tree
16.3. 9am	KB	Graphs V: maxflow: intro, maxflow mincut
17.3. 9am	KB	Graphs VI: maxflow: Ford-Fulkerson
17.3. 2pm	KB	Graphs VII: maxflow: blocking flows
18.3. 9am	KB	Graphs VIII: maximum matching
18.3. 2pm	KB	Graphs IX: global mincut
21.3. 9am	RS	Geometry I: orthogonal range searching
21.3. 2pm	RS	Geometry II: sweep
22.3. 9am	RS	Geometry III: point sets viewed globally
22.3. 2pm	RS	Geometry IV: point sets viewed locally
23.3. 9am	RS	Geometry V: arrangements, duality	room change: HS002 E1 3
24.3. 9am	KB	SAT Algorithms	room change: HS001 E1 3
24.3. 2pm	KB	Teaser: Fine-Grained Complexity
25.3. 9am	KB	Teaser: Streaming and Sketching I	room change: HS002 E1 3
25.3. 2pm	KB	Teaser: Streaming and Sketching II

Literature