Datenstrukturen und Algorithmen 252-0002-00L, 252-0002-AAL
Course at D-MATH (CSE) of ETH Zürich, Spring Semester 2021, Felix Friedrich
Course at D-MATH (CSE) of ETH Zürich, Spring Semester 2021, Felix Friedrich
| Date | Message |
|---|---|
| 1.6.2021 | Mock-Exam online |
| 10.1.2022 | Exam from August 2021 is online (moddle link, the paper part can also be opened from the moodle page): link (Exam password is "Informatik") |
| 20.1.2022 | August Exam 2021 link corrected (previous version could not be accessed) link (Exam password is "Informatik") |
The course provides the foundations for the design and analysis of algorithms. Classical problems ranging from sorting up to problems on graphs are used to discuss common data structures, algorithms and algorithm design paradigms. The course also comprises an introduction to parallel and concurrent programming and the programming model of C++ is discussed in some depth. All required mathematical tools above high school level are covered, including a basic introduction to graph theory. Exercises are carried out in Code-Expert, an online IDE and exercise management system.
An understanding of the analysis and design of fundamental and common algorithms and data structures. Deeper insight into a modern programming model by means of the programming language C++. Knowledge regarding chances, problems and limits of parallel and concurrent programming.
Lecture Series 252-0856 Computer Science or equivalent knowledge in programming with C++.
All lectures and exercise sessions are conducted remotely until further notice. You find Zoom meeting links for classes in the table. The sessions are scheduled at the usual time (Switzerland time), simply join the session few minutes before it starts.
| Lectures | Monday 10:15 - 12:00 | ML E 12 | Zoom |
|---|---|---|---|
| Thursday 08:15 - 10:00 | ML E 12 | Zoom |
The (German spoken) lectures are recorded. Videos will be made available in the agenda below.
This is a plan. No plan survives contact with reality. We will constantly update lecture material before the lectures.
| Number | Date | Topic, Videos and Recordings | Lecture Material | Exercises |
|---|---|---|---|---|
| 1 | Mon 22.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]
Videos: Organisation , Introduction , Asymptotics Lecture Recording: DA_2021_01 |
Organisation:
[de]
[en]
Slides 1: [de] [en] Handout 1: [de] [en] Code Example: [ipynb] [pdf] |
Einschreibung / Enrollment |
| 2 | Thu 25.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]
Videos: EgyptianMultiplication , KaratsubaOfman , Karatsuba:Appendix(Runtime) , Maximum-Subarray Lecture Recording: DA_2021_02 |
Slides 2:
[de]
[en]
Handout 2: [de] [en] |
O, Theta and Omega, asymptotic running times and 2d prefix sum Slides: [de] [en] |
| 3 | Mon 01.03. | 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]
Videos: Searching , QuickSelect , Blum Lecture Recording: DA_2021_03 |
Slides 3:
[de]
[en]
Handout 3: [de] [en] |
--- |
| 4 | Thu 04.03. |
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 Videos: ToolsAndMemoryManagement , EfficientMemoryManagement Lecture Recording: I have forgotten to record the lecture today. Please watch the English video or recordings from last year: here. We have not yet covered iterators and efficient memory management. |
Slides 4:
[de]
[en]
Handout 4: [de] [en] |
Induction Proofs, Running Times, Median Algorithms, Vectors Slides: [de] [en] |
| 5 | Mon 08.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]
Videos: NaiveSorting , DivideAndConquerSort Lecture Recording: DA_2021_05 |
Slides 5:[de]
[en]
Handout 5:[de] [en] |
--- |
| 6 | Thu 11.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]
Videos: MasterTheorem , LowerBoundsOnSorting , RadixAndBucketSort Lecture Recording: DA_2021_06 |
Slides 6: [de]
[en]
Handout 6:[de] [en] |
Compare Sort Algorithms, Vector Implementation, Master Method Slides: [de] [en] |
| 7 | Mon 15.03. | C++ advanced (II) Templates.
Videos: Templates , Smart Pointers Lecture Recording: DA_2021_07 |
Slides 7:[de]
[en]
Handout 7:[de] [en] |
--- |
| 8 | Thu 18.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]
Videos: Fundamental Datastructures , Amortized Analysis , Move To Front , Skip Lists Lecture Recording: DA_2021_08 |
Slides 8:[de]
[en]
Handout 8:[de] [en] |
Amortized Analysis, Dynamic Array, Vector Template
Slides: [de] [en] |
| 9 | Mon 22.03. |
Hashing Hash Tables, Pre-Hashing, Hashing, Resolving Collisions using Chaining, Simple Uniform Hashing, Popular Hash Functions,
Table-Thuubling, 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]
Videos: Hashing 1: Closed Addressing , Hashing 2: Open Addressing Lecture Recording: DA_2021_09 |
Slides 9:[de]
[en]
Handout 9:[de] [en] |
--- |
| 10 | Thu 25.03. |
C++ advanced (III) Functors and Lambda
Videos: Functors/Lambda Lecture Recording: DA_2021_10 |
Slides 10:[de]
[en]
Handout 10:[de] [en] |
Hashing: Open Hashing, Cockoo Hashing, Division Method, Rabin-Karp Slides: [de] [en] |
| 11 | Mon 29.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]
Videos: Search Trees Heaps AVL Trees Fibonacci (Generating Functions) Lecture Recording: DA_2021_11 |
Slides 11:[de]
[en]
Handout 11:[de] [en] |
--- |
| 12 | Thu 01.04. |
(Lecture 11 ctd.)
Lecture Recording: DA_2021_12 |
Binary Search Trees, AVL Trees and Heaps, Functors and Lambdas Slides: [de] [en] -- Easter Break -- |
|
| - | Mon 05.04. | -- Easter Break -- | --- | -- Easter Break -- |
| - | Thu 08.04. | -- Easter Break -- | --- | -- Easter Break -- |
| 13 | Mon 12.04 |
Quadtrees Quadtrees, Collision Detection, Image Segmentation
Videos: Quadtrees Dynamic Programming I Memoization, Optimal Substructure, Overlapping Sub-Problems, Dependencies, General Procedure. Examples: Fibonacci, Rod Cutting Videos: DP Intro DP Rod Cutting Lecture Recording: DA_2021_13 |
Slides 12:[de]
[en]
Handout 12:[de] [en] Slides 13:[de] [en] Handout 13:[de] [en] |
--- |
| 14 | Thu 15.04. |
Dynamic Programming I ctd. 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]
Videos: Rabbits Longest Ascending Subsequence Editing Distance Matrix Chain Multiplication Lecture Recording: DA_2021_14 |
Quadtrees: Image Segmentation, DP: Piecewise Constant Approximation, Mars Mission and Edit Distance Slides: [de] [en] |
|
| 15 | Mon 19.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]
Videos: Subset Sum Input Sizes NP-Completeness Knapsack Lecture Recording: DA_2021_15 |
Slides 14:[de]
[en]
Handout 14:[de] [en] |
--- |
| 16 | Thu 22.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]
Videos: FPTAS Optimal Search Trees Lecture Recording: DA_2021_16 |
Slides 15:[de]
[en]
Handout 15:[de] [en] |
DP Slides: [de] [en] |
| 17 | Mon 26.04. |
Greedy Algorithms Fractional Knapsack Problem, Huffman Coding [Cormen et al, Kap. 16.1, 16.3] Videos: Fractional Knapsack Huffman Coding Lecture Recording: DA_2021_17 |
Slides 16:[de]
[en]
Handout 16:[de] [en] |
--- |
| 18 | Thu 29.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]
Videos: Graphs: Intro Traversal Topological Sorting Transitive Closure Lecture Recording: DA_2021_18 |
Slides 17: [de]
[en]
Handout 17:[de] [en] |
Graph Traversal, Topological Sorting Slides: [de] [en] |
| 19 | Mon 03.05 |
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]
Lecture Recording: DA_2021_19 Videos: Shortest Paths and Dijstra Shortest Paths with negative weights All Pairs Shortest Paths |
Slides 18:[de]
[en]
Handout 18:[de] [en] |
--- |
| 20 | Thu 06.05. |
Shortest Paths ctd. A* Algorithm, All Pairs Shortest Paths
Lecture Recording: DA_2021_20 Videos: A* Algorithm |
Slides 19:[de]
[en]
Handout 19:[de] [en] |
All Pairs Shortest Paths: Closeness Centrality, Dijkstra by Hand, Amazing mazes (Dijkstra and A-Star) [de] [en] |
| 21 | Mon 10.05. |
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] Fibonacci Heaps
Lecture Recording: DA_2021_21 Videos: Minimum Spanning Trees Fibonacci Heaps |
Slides 20:[de]
[en]
Handout 20:[de] [en] |
--- |
| -- | Thu 13.05. | -- Ascension -- | --- |
Minimum Spanning Tree, Union-Find, TSP Apprximation, Manual Max-Flow Slides: [de] [en] |
| 22 | Mon 17.05. |
Flow in Networks: Flow-Network, Max-Flow-Min-Cut, 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]
Lecture Recording: DA_2021_22 Videos: Max-Flow Intro Max-Flow Min-Cut Ford Fulkerson and Edmonds Karp Maximum Matching |
Slides 21:[de]
[en]
Handout 21:[de] [en] |
--- |
| 23 | Thu 20.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]
Lecture Recording: DA_2021_23 Videos: Parallelism and Concurrency C++ Threads Task Parallelism Scalability |
Slides 22:[de]
[en]
Handout 22:[de] [en] |
Applying Max-Flow, Network Reliability, Parallel Sum, Parallel Merge-Sort, Amdahl/Gustafson Slides: [de] [en] |
| -- | Mon 24.05. | -- Pentecost -- | --- | |
| 24 | Thu 27.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]
Lecture Recording: DA_2021_24 Videos: Race Conditions |
Slides 23:[de]
[en]
Handout 23:[de] [en] |
Race Conditions, Dining Philosophers (Deadlock and Starvation), Bridge (Waiting on Conditions) Slides: [de] [en] |
| 25 | Mon 31.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]
Lecture Recording: DA_2021_25 Videos: Deadlocks And Monitors |
Slides 24:[de]
[en]
Handout 24:[de] [en] |
|
| 26 | Thu 03.06. |
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]
Lecture Recording: DA_2021_26 Videos: Futures, RMW And Lock-Free Programming |
Slides 25:[de]
[en]
Handout 25:[de] [en] Alle Folien dieser Vorlesung / all slides of this course: Overlays: [de] [en] Handout: [de] [en] Handout 2x2:[de] [en] |
Slides: [de] [en] |
Exercise sessions are conducted remotely until further notice. You find Zoom meeting links for each of the exercise sessions in the table. The sessions are scheduled at the usual time (Switzerland time), simply join the session few minutes before it starts.
| Time | Location | Zoom Link | Assistant | Language |
|---|---|---|---|---|
| Friday 08:15 - 10:00 | CAB G 57 | Zoom | Sebastian Balzer | english |
| Friday 10:15 - 12:00 | CAB G 59 | Zoom | Christoph Grötzbach | deutsch |
| Friday 10:15 - 12:00 | LFW B 3 | Zoom | Ivana Klasovita | deutsch |
| Friday 10:15 - 12:00 | RZ F 21 | Zoom | Stanislav Piasecki | deutsch |
For questions regarding the exercise management, please contact the chief assistant Aritra Dhar or Julia Chatain.
There will be 3 bonus exercises during the semester. By solving these exercises you will get up to 0.25 grade points added on top of your exam grade. In order to access the bonus exercises you need to unlock them in Code Expert by solving assignments from previous weeks and earning sufficiently many experience points (XP). Slide set 0 (Organisational) contains more information.
We have a set up a moodle page for this course including a forum to ask questions here.
Past exams can be accessed on the Past Exams Collection Website.
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.