Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Data Structures and Algorithms, Self-study course

Short course description

Certain Master students may take the exam based on self-study (e.g., for Computational Biology and Bioinformatics Master). If you are not sure whether you are eligible, then please contact your study administration office for details.

In order to prepare for the exam, we provide a course summary and literature, as well as the exercises of FS2016. We also provide a list of previous exams in English (where available) and German.
The course was taught once a year during the spring semester (until FS2016); the covered material is relevant for both exams offered after the spring and fall semester.

Contact

Peter Widmayer, peter.widmayer "A.T." inf.ethz.ch
Thomas Tschager, thomas.tschager "A.T." inf.ethz.ch

Lecture Topics Literature
1

Introduction and Algorithm Design.

  • Introduction and Algorithm Design. Role of algorithms in computer science.
  • An example for the design of algorithms: fast multiplication of integers, Karatsuba/Ofman 1962. Finding a star by asking questions.
  • Uniform cost model. Growth of functions: big O notation, Omega, Theta.
 Cormen et al.:
Chapter 1–3
2

Algorithm Design by Induction.

  • Maximum subarray problem: naı̈ve algorithm, precomputation of prefix sums, divide and conquer, linear scan.
 Cormen et al.:
Chapter 4.1
3

Searching I: Searching. Computing the Median.

  • Linear search, binary search, interpolation search, upper and lower bounds.
  • Randomized median computation. Blum’s algorithm for computing the median.
 Cormen et al.:
Problem 2.1-3, 2.2-3, 2.3-5
Chapter 9
4

Searching II: Hashing.

  • Hash tables, hash functions, universal hashing.
  • Collision resolution by chaining, open hashing, probing.
 Cormen et al.:
Chapter 11
5

Sorting I: Elementary Sorting Methods. Heapsort.

  • Bubblesort, odd-even transposition sort, selection sort, insertion sort.
  • Heapsort, implicit representation of the heap, creating a heap in linear time.
 Cormen et al.:
Chapter 2, Problem 2.2-2, 2-2,
Chapter 6
6

Sorting II: Mergesort, Quicksort.

  • Mergesort.
  • Quicksort: key comparisons: best case, worst case; Movements: worst case; Additionally required memory. Key comparisons for randomized quicksort.
 Cormen et al.:
Chapter 2.3.1 and 7
7

Sorting III: Lower bounds. Radix sort. Dictionaries I: Basic concepts.

  • Lower bound for decision-based sorting: decision tree, average height of a leaf in a binary tree. Radix Exchange Sort.
  • Dictionaries: Array, linear list, skip list.
 Cormen et al.:
Chapter 8.1, 8.3, 10.2
8

Dictionaries II: Binary Search Trees, AVL Trees.

  • Binary search tree: traversal,searching, insertion, deletion.
  • AVL trees: height of the tree, insertion.
 Cormen et al.:
Chapter 12.1-12.3

Goodrich et al.:
Chapter 3.2
9

Dictionaries III: AVL Trees. Amortized Analysis. Self-Organizing Linear Lists.

  • AVL trees: Amortized analysis of the insert operation.
  • Self-organizing linear lists, move-to-front rule (with analysis).
 Goodrich et al.:
Chapter 3.2

Cormen et al.:
Chapter 17, esp. Problem 17-5
10

Dynamic Programming 1

  • Longest increasing subsequence
  • Edit distance.
  • Matrix chain multiplication.
 Cormen et al.:
Chapter 15
11

Dynamic Programming 2

  • Subset sum.
  • Knapsack problem.
  • FPTAS.
 Cormen et al.:
Chapter 35.5

Vazirani:
Chapter 8.1 and 8.2
12

Algorithm design: divide-and-conquer, dynamic programming, greedy

  • Matrix multiplication by Strassen.
  • Optimal search trees, construction with dynamic programming.
  • Huffman Coding.
 Cormen et al.:
Chapter 4.2, 15.5 and 16.3
13

Self-organizing search trees: Splay trees

  • Splay Trees.
 Goodrich and Tamassia:
Chapter 3.4
14

Graph Algorithms I

  • Reflexive and transitive closure.
  • Graph traversal: BFS, DFS.
  • Connected components.
  • Topological sorting.
 Cormen et al.:
Chapter 22
15

Graph Algorithms II

  • Minimum spanning trees: introduction, greedy algorithms, Kruskal’s algorithm with union find structure.
 Cormen et al.:
Chapter 23
16

Graph Algorithms III

  • Minimum spanning trees with Prim/Dijkstra.
  • Fibonacci heaps (w/o analysis)
 Cormen et al.:
Chapter 19 and 23
17

Graph Algorithms IV

  • Analysis of Fibonacci heaps
  • Shortest paths from a single source. Algorithm of Dijkstra, Ford, Bellman
 Cormen et al.:
Chapter 19 and 24.1–24.3
18

Graph Algorithms V - Shortest paths

  • One-to-all shortest paths: Bellman; Bellman-Ford.
  • All-to-all shortest paths: Floyd-Warshall; Johnson.
  • Heuristiken: Bidirectional, A^*.
 Cormen et al.:
Chapter 24.1, 25.2 and 25.3
19

Wunderbare Welt der Algorithmen.

  • Online algorithms (lost-cow problem)
  • Streaming algorithms (majority element)
  • Distributed algorithms (Chang's echo, two generals)
  • Approximation algorithms (Christofides)

20

Backtracking, Branch-and-Bound.

  • Backtracking. Examples 4 Damen, SAT.
  • Branch-and-Bound. Examples MAX SAT, Knapsack, TSP.
Skiena: Chapter 7.1
Wolsey, Ch. 7.1–7.2
21

Flows in Networks I.

  • Augmenting path algorithm by Ford and Fulkerson.
  • Max-flow min-cut theorem.
Cormen et al.:
Chapter 26.1 and 26.2
22

Flows in Networks II.

  • Augmenting path by capacity scaling; shortest augmenting paths (Edmonds and Karp), Dinic
  • Matchings in bipartite graphs.
Ahuja, Chapter 7.5
Cormen et al.:
Chapter 26.2 – 26.3, Problem 26.3-4
23

Geometric Algorithms I.

  • Convex hull of points in the plane: Jarvis, Graham, linear scan.
  • Intersection of orthogonal line segments
deBerg, Ch. 1.1 – 1.2

Cormen et al.: Chapter 33.1 – 33.3
24

Geometric Algorithms II.

  • Intersection of arbitrarily oriented line segments.
  • Intervals as 2-dimensional points
deBerg, Ch. 5.3, 10.1 – 10.3

Cormen et al.: Chapter 33.2
25

Geometric Algorithms III.

  • Intersection of axis-parallel rectangles: 2-dimensional range trees; segment trees; tile trees/interval trees, and priority trees

deBerg, Ch. 5.3, 10.1 – 10.3
26

External Memory Structures.

  • B-Trees

Cormen et al.:
Chapter 18

Literature

Exercise sheets

Exercise sheets Example Solutions (in german)
Exercise sheet 1 Solution 1 (german)
Exercise sheet 2 Solution 2 (german)
Exercise sheet 3 Solution 3 (german)
Solution 3 - Programming Exercise
Exercise sheet 4 Solution 4 (german)
Solution 4 - Programming Exercise
Exercise sheet 5 Solution 5 (german)
Exercise sheet 6 Solution 6 (german)
Exercise sheet 7 Solution 7 (german)
Exercise sheet 8 Solution 8 (german)
Solution 8 - Programming Exercise
Exercise sheet 9 Solution 9 (german)
Exercise sheet 10 Solution 10 (german)
Exercise sheet 11 Solution 11 (german)
Exercise sheet 12 Solution 12 (german)
Exercise sheet 13 Solution 13 (german)
Exercise sheet 14 Solution 14 (german)