Algorithms and Data Structures (block course)

Algorithms and Data Structures (block course)

The course will cover basic and advanced data structures and algorithms, as well as their analysis. Examples of data structures are perfect 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, and Format

This core course will be offered in an intensive block version between February 28 and March 26. The course can be taken only in presence.

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 Wednesdays, which will have only the morning unit. As an exception, the first lecture happens on February 28 at 14:00. See Information→Timetable for details.

The lecture will take place in room HS003 in building E1 3.

The tutorial will take place at 12:00 and at 17:00 in seminar room 106 in building E1 1. The room 016 in building E1 3 is also reserved throughout the lecture period as working space.

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

Registration

You need to register on this webpage to get access to exercise sheets and other course material.

Exams

You grade will be determined by a written exam. Admittance to the exams requires active participation in the course.

Endterm:  28.03. 2pm-4pm, HS I in E2 5

Re-Exam:  11.04. 2pm-4pm, HS 002 in 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, 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 videos 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, suffix arrays)
• graphs (e.g. shortest paths, maxflow, matching)
• computational geometry

Date	Lecturer	Topic	Comment
28.2. 2pm	PW	Intro: machine model, O-notation
29.2. 9am	PW	Strings I: string matching	Morris-Pratt (see [CR])
29.2. 2pm	PW	Strings II: edit distance and approximate string matching	Needleman-Wunsch
1.3. 9am	PW	Strings III: approximate string matching (cont), suffix array	Landau-Vishkin
1.3. 2pm	PW	Strings IV: suffix array construction, lcp array construction	Kärkkäinen-Sanders, Kasai et al.
4.3. 9am	PW	Strings V: lcp array construction (cont), range minimum queries	Kasai et al. (cont)
4.3. 2pm	PW	Advanced Dynamic Programming: LIS, segment trees
5.3. 9am	EK	Amortization I: intro
5.3. 2pm	EK	Amortization II: Fibonacci heaps
6.3. 9am	EK	Amortization III: splay trees
7.3. 9am	EK	Amortization IV: union find
7.3. 2pm	KB	Randomized I: model, rank select
8.3. 9am	KB	Randomized II: randomized search trees
8.3. 2pm	KB	Randomized III: hashing
11.3. 9am	KB	Randomized IV: more on hashing
11.3. 2pm	KB	Randomized V: Monte Carlo algorithms
12.3. 9am	PW	Divide and Conquer I: Recurrences (I), Karatsuba
12.3. 2pm	PW	Divide and Conquer II: Recurrences(II), Master Theorem, Strassen
13.3. 9am	PW	Polynomials I: Introduction
14.3. 9am	PW	Polynomials II: FFT
14.3. 2pm	PW	Polynomials III: Polynomial division, Schönhage-Strassen
15.3. 9am	EK	Graphs I: intro, BFS+DFS, Dijkstra
15.3. 2pm	EK	Graphs II: shortest path: Bellman-Ford, Floyd-Warshall, Johnson, ...
18.3. 9am	EK	Graphs III: minimum spanning tree
18.3. 2pm	EK	Graphs IV: maxflow: intro, maxflow mincut
19.3. 9am	EK	Graphs V: maxflow: Ford-Fulkerson
19.3. 2pm	EK	Graphs VI: maxflow: blocking flows
20.3. 9am	EK	Graphs VII: maximum matching
21.3. 9am	EK	Graphs VIII: global mincut
21.3. 2pm	KB	Geometry I: intro, convex hull
22.3. 9am	KB	Geometry II: convex hull ctd., linear programming
22.3. 2pm	KB	Geometry III: orthogonal range searching
25.3. 9am	KB	Geometry IV: sweep line, Voronoi diagrams
25.3. 2pm	KB	Geometry V: Voronoi diagrams ctd. + intro to models of computation
26.3. 9am	KB	Models of Computation: cache hierarchy, IO model
26.3. 2pm	KB	Models of Computation: IO model ctd.

Literature