Datenstrukturen und Algorithmen (252-0002-00L, 252-0002-AAL)
Course at D-MATH (CSE) of ETH Zürich, Spring Semester 2020 , Felix Friedrich
Course at D-MATH (CSE) of ETH Zürich, Spring Semester 2020 , Felix Friedrich
| Date | Message |
|---|---|
| 25.11.2020 | Added exam 08.2020 including its solution in the Exams section below. |
All lectures and exercise sessions are conducted remotely. You can find all information under the link below (use your ETH login when asked for password).
| Lectures | Monday 10:15 - 12:00 | ML E 12 |
|---|---|---|
| Thursday 08:15 - 10:00 | ML E 12 | |
| Exercises | Friday 08:15-10:00, 10:15-12:00 | Various Rooms (cf below) |
The (German spoken) lectures are recorded. Please find the videos here. Login credentials have been sent by email.
Fundamental algorithms and data structures are presented and analyzed. Firstly, this comprises design paradigms for the development of algorithms such as induction, divide-and-conquer, backtracking and dynamic programming and classical algorithmic problems such as searching and sorting. Secondly, data structures for different purposes are presented, such as linked lists, hash tables, balanced search trees, heaps and union-find structures. The relationship and tight coupling between algorithms and data structures is illustrated with geometric problems and graph algorithms. In the part about parallel programming, parallel architectures are discussed conceptually (multicore, vectorization, pipelining). Parallel programming concepts are presented (Amdahl's and Gustavson's laws, task/data parallelism, scheduling). Problems of concurrency are analyzed (Data races, bad interleavings, memory reordering). Process synchronisation and communication in a shared memory system is explained (mutual exclusion, semaphores, monitors, condition variables). Progress conditions are analysed (freedom from deadlock, starvation, lock- and wait-freedom). The concepts are underpinned with examples of concurrent and parallel programs and with parallel algorithms. The programming model of C++ is discussed in some depth. The RAII (Resource Allocation is Initialization) principle will be explained. Exception handling, functors and lambda expression and generic prorgamming with templates are further examples of this part. The implementation of parallel and concurrent algorithm with C++ is also part of the exercises (e.g. threads, tasks, mutexes, condition variables, promises and futures).
An understanding of the design and analysis of fundamental algorithms and data structures. Knowledge regarding chances, problems and limits of parallel and concurrent programming. Deeper insight into a modern programming model by means of the programming language C++.
Prerequisites: Lecture Series 252-0856 Computer Science or equivalent knowledge in programming with C++.
This is a plan. No plan survives contact with reality. We will constantly update lecture material before the lectures.
| Number | Date | Topic | Lectures | Exercises | PPrerequisites to unlock bonus exercises | BBonus exercises |
|---|---|---|---|---|---|---|
| 1 | MO 17.02. | Overview, Algorithms and Data Structures, Efficiency of Algorithms, Random Access Machine Model, Function Growth, Asymptotics [Cormen et al, Kap. 2.2,3,4.2-4.4 | Ottman/Widmayer, Kap. 1.1] |
Organisation:
[de]
[en]
Slides 1: [de] [en] Handout 1: [de] [en] |
Einschreibung / Enrollment | Skiplist | |
| 2 | DO 20.02. | Correctness and Efficiency of Algorithms by Example: Ancient Egyptian Multiplication, Fast Integer Multiplication, [Ottman/Widmayer, Kap. 1.2.3] Algorithm Design – Maximum Subarray Problem [Ottman/Widmayer, Kap. 1.3], Divide and Conquer [Ottman/Widmayer, Kap. 1.2.2. S.9; Cormen et al, Kap. 4-4.1] |
Slides 2:
[de]
[en]
Handout 2: [de] [en] |
O, Theta and Omega, asymptotic running times and 2d prefix sum Slides: [de] [en] |
||
| 3 | MO 24.02. | Search and Selection Linear Search, Binary Search, (Interpolation Search,) Lower Bounds [Ottman/Widmayer, Kap. 3.2, Cormen et al, Kap. 2: Problems 2.1-3,2.2-3,2.3-5], The Selection Problem, Randomised Selection, Linear Worst-Case Selection [Ottman/Widmayer, Kap. 3.1, Cormen et al, Kap. 9] |
Slides 3:
[de]
[en]
Handout 3: [de] [en] |
--- | ||
| 4 | DO 27.02. |
Algorithm of Blum, Floyd, Pratt, Rivest and Tarjan (Median of Medians) C++ advanced (I) Repetition: vectors, pointers and iterators, range for, keyword auto, a class for vectors, subscript-operator, move-construction, iterators |
Slides 4:
[de]
[en]
Handout 4: [de] [en] |
Induction Proofs, Running Times, Median Algorithms, Vectors Slides: [de] [en] |
||
| 5 | MO 02.03. | Sorting Naive Sorting Algorithms [Ottman/Widmayer, Kap. 2.1, Cormen et al, Kap. 2.1, 2.2, Exercise 2.2-2, Problem 2-2], Mergesort [Ottman/Widmayer, Kap. 2.4, Cormen et al, Kap. 2.3], Quicksort [Ottman/Widmayer, Kap. 2.2, Cormen et al, Kap. 7] |
Slides 5:[de]
[en]
Handout 5:[de] [en] |
--- | Skiplist | |
| 6 | DO 05.03. |
Sorting ctd.
Lower bounds for comparison based sorting [Ottman/Widmayer, Kap. 2.8, Cormen et al, Kap. 8.1], Radixsort, Bucketsort [Ottman/Widmayer, Kap. 2.5, Cormen et al, Kap. 8.3]
|
Slides 6: [de]
[en]
Handout 6:[de] [en] |
Compare Sort Algorithms, Vector Implementation, Master Method Slides: [de] [en] |
||
| 7 | MO 09.03. | C++ advanced (II) Templates. |
Slides 7:[de]
[en]
Handout 7:[de] [en] |
--- | AVL Tree | |
| 8 | DO 12.03. | Fundamental Data Structures Abstract data types stack, queue, implementation variants for linked lists [Ottman/Widmayer, Kap. 1.5.1-1.5.2, Cormen et al, Kap. 10.1.-10.2], Amortized Analyis Aggregate Analysis, Account-Method, Potential-Method [Ottman/Widmayer, Kap. 3.3, Cormen et al, Kap. 17], Dictionaries Self-ordering List, Implementation of Dictionaries with Array / List /Skip lists. [Ottman/Widmayer, Kap. 3.3,1.7, Cormen et al, Kap. Problem 17-5] |
Slides 8:[de]
[en]
Handout 8:[de] [en] |
Amortized Analysis, Dynamic Array, Vector Template Slides: [de] [en] |
||
| 9 | MO 16.03. | Hashing Hash Tables, Pre-Hashing, Hashing, Resolving Collisions using Chaining, Simple Uniform Hashing, Popular Hash Functions, Table-Doubling, Open Addressing: Probing, Uniform Hashing, Universal Hashing, Perfect Hashing [Ottman/Widmayer, Kap. 4.1-4.3.2, 4.3.4, Cormen et al, Kap. 11-11.4] |
Slides 9:[de]
[en]
Handout 9:[de] [en] |
--- | ||
| 10 | DO 19.03. | C++ advanced (III) Functors and Lambda |
Slides 10:[de]
[en]
Handout 10:[de] [en] |
Hashing: Open Hashing, Cockoo Hashing, Division Method, Rabin-Karp Slides: [de] [en] |
||
| 11 | MO 23.03. | Binary Search Trees [Ottman/Widmayer, Kap. 5.1, Cormen et al, Kap. 12.1 - 12.3], Augmented Trees, Heaps and Heapsort [Ottman/Widmayer, Kap. 2.3, Cormen et al, Kap. 6], AVL Trees Balanced Trees [Ottman/Widmayer, Kap. 5.2-5.2.1, Cormen et al, Kap. Problem 13-3] |
Slides 11:[de]
[en]
Handout 11:[de] [en] |
--- | AVL Tree | |
| 12 | DO 26.03. | Quadtrees Quadtrees, Collision Detection, Image Segmentation |
Slides 12:[de]
[en]
Handout 12:[de] [en] |
Binary Search Trees, AVL Trees and Heaps, Functors and Lambdas Slides: [de] [en] |
||
| 13 | MO 30.03. | Dynamic Programming I Memoization, Optimal Substructure, Overlapping Sub-Problems, Dependencies, General Procedure. Examples: Fibonacci, Rod Cutting, Longest Ascending Subsequence, Longest Common Subsequence, Edit Distance, Matrix Chain Multiplication (Strassen) [Ottman/Widmayer, Kap. 1.2.3, 7.1, 7.4, Cormen et al, Kap. 15] |
Slides 13:[de]
[en]
Handout 13:[de] [en] |
--- | Max-Flow Edmonds-Karp | |
| 14 | DO 02.04. | Dynamic Programming II Subset sum problem, knapsack problem, greedy algorithm vs dynamic programming [Ottman/Widmayer, Kap. 7.2, 7.3, 5.7, Cormen et al, Kap. 15,35.5] |
Slides 14:[de]
[en]
Handout 14:[de] [en] |
Dynamic Programming: Mars Rover, Signal Approximation, Palindromes and Edit Distance Slides: [de] [en] |
||
| 15 | MO 06.04. | Dynamic Programming III FPTAS [Ottman/Widmayer, Kap. 7.2, 7.3, Cormen et al, Kap. 15,35.5], Optimal Search Tree [Ottman/Widmayer, Kap. 5.7] |
Slides 15:[de]
[en]
Handout 15:[de] [en] |
--- | ||
| 16 | DO 09.04. |
Greedy Algorithms Fractional Knapsack Problem, Huffman Coding [Cormen et al, Kap. 16.1, 16.3] C++ Advanced (IV) Exceptions |
Slides 16:[de]
[en]
Handout 16:[de] [en] |
DP Slides: [de] [en] |
||
| - | MO 13.04. | -- Easter Break -- | --- | -- Easter Break -- | ||
| - | DO 16.04. | -- Easter Break -- | --- | -- Easter Break -- | ||
| 17 | MO 20.04. | Graphs Notation, Representation, Graph Traversal (DFS, BFS), Topological Sorting , Reflexive transitive closure, Connected components [Ottman/Widmayer, Kap. 9.1 - 9.4,Cormen et al, Kap. 22] |
Slides 17: [de]
[en]
Handout 17:[de] [en] |
--- | ||
| 18 | DO 23.04. | Shortest Paths Motivation, Dijkstra’s algorithm on distance graphs, Bellman-Ford Algorithm, Floyd-Warshall Algorithm [Ottman/Widmayer, Kap. 9.5 Cormen et al, Kap. 24.1-24.3, 25.2-25.3] |
Slides 18:[de]
[en]
Handout 18:[de] [en] |
Graph Traversal, Topological Sorting, Single-Source Shortest Paths Slides: [de] [en] |
||
| 19 | MO 27.04 | Shortest Paths ctd. A* Algorithm, All Pairs Shortest Paths |
Slides 19:[de]
[en]
Handout 19:[de] [en] |
--- | Max-Flow Edmonds Karp | |
| 20 | DO 30.04. |
Minimum Spanning Trees Motivation, Greedy, Algorithm Kruskal, General Rules, ADT Union-Find, Algorithm Jarnik, Prim, Dijkstra, Algorithm Jarnik, Prim, Dijkstra [Ottman/Widmayer, Kap. 9.6, 6.2, 6.1, Cormen et al, Kap. 23, 19] |
Slides 20:[de]
[en]
Handout 20:[de] [en] |
All Pairs Shortest Paths: Closeness Centrality, Minimum Spanning Trees Slides (no exercise lesson): [de] [en] |
||
| 21 | MO 04.05. | Fibonacci Heaps (in slide set 20), Flow in Networks Intro Flow Network, Maximal Flow, Cut |
Slides 21:[de]
[en]
Handout 21:[de] [en] |
--- | Parallel Programming | |
| 22 | DO 07.05. | Flow in Networks: Ford Fulkerson and Applications Residual Network, Max-flow Min-cut Theorem, Ford-Fulkerson Method, Edmonds-Karp Algorithm, Maximal Bipartite Matching [Ottman/Widmayer, Kap. 9.7, 9.8.1], [Cormen et al, Kap. 26.1-26.3] | (slide set 21 continued) |
Manual Max-Flow, Network Reliability, Applying Max-Flow Slides: [de] [en] |
||
| 23 | MO 11.05. | Flow in Networks: Push-Relabel Algorithms |
Slides 22:[de]
[en]
Handout 22:[de] [en] |
--- | 24 | Do 14.05. | Parallel Programming I Moore’s Law and the Free Lunch, Hardware Architectures, Parallel Execution, Flynn’s Taxonomy, Scalability: Amdahl and Gustafson, Data-parallelism, Task-parallelism, Scheduling [Task-Scheduling: Cormen et al, Kap. 27] [Concurrency, Scheduling: Williams, Kap. 1.1 – 1.2] |
Slides 23:[de]
[en]
Handout 23:[de] [en] |
Speedup, Amdahl, Gustavson, Parallel Sum of a Vector, Parallel Merge Sort, Task Parallelism Slides: [de] [en] |
| 25 | MO 18.05. |
Parallel Programming II
C++ Threads, Shared Memory, Concurrency, Excursion: lock algorithm (Peterson), Mutual Exclusion Race Conditions [C++ Threads: Williams, Kap. 2.1-2.2], [C++ Race Conditions: Williams, Kap. 3.1] [C++ Mutexes: Williams, Kap. 3.2.1, 3.3.3]
|
Slides 24:[de]
[en]
Handout 24:[de] [en] |
--- | ||
| - | DO 21.05. | -- Ascension -- | --- |
Race Conditions, Dining Philosophers (Deadlock and Starvation), Bridge (Waiting on Conditions), Concurrent Linked List (Lock Granularity) Slides: [de] [en] |
||
| 26 | Mo 25.05. | Parallel Programming III Deadlock and Starvation Producer-Consumer, The concept of the monitor, Condition Variables [Deadlocks : Williams, Kap. 3.2.4-3.2.5] [Condition Variables: Williams, Kap. 4.1] |
Slides 25:[de]
[en]
Handout 25:[de] [en] --> |
|||
| 27 | Do 28.05. | Parallel Programming IV Futures, Read-Modify-Write Instructions, Atomic Variables, Idea of lock-free programming [C++ Futures: Williams, Kap. 4.2.1-4.2.3] [C++ Atomic: Williams, Kap. 5.2.1-5.2.4, 5.2.7] [C++ Lockfree: Williams, Kap. 7.1.-7.2.1] |
Slides 26:[de]
[en]
Handout 26:[de] [en] Alle Folien dieser Vorlesung / all slides of this course: Overlays: [de] [en] Handout: [de] [en] Handout 2x2:[de] [en] |
Slides: [de] [en] |
The registration to the exercise system is an online process. More information during first lecture.
The exercise groups are assigned as follows
| Time | Location | Assistent | Language |
|---|---|---|---|
| Fr, 08:15 - 10:00 | CAB G 57 | Roger Barton | english |
| Fr, 10:15 - 12:00 | CAB G 59 | Joshua Aurand | deutsch |
| Fr, 10:15 - 12:00 | LFW B 3 | Sebastian Balzer | deutsch |
| Fr, 10:15 - 12:00 | RZ F 21 | Thomas Baumann | deutsch |
In order to download old exams, please agree to the following
The lecture slides of this physical course are offered both in German and English and are reasonably elaborate. The literature hints provided below will help to understand the material but the slides are otherwise intended to be self-contained.
The exercises (offered in English) are also an important part of the course. It is needless to say that we recommend to work through them -- without looking at the solutions in the first place!
If you want to take the real course, you can do so in the spring semester. The course is offered with (German spoken) lectures and (German or English spoken) recitation sessions.
Kind regards, Felix Friedrich.