ETH Zürich

Datenstrukturen und Algorithmen 252-0002-00L, 252-0002-AAL


Course at D-MATH (CSE) of ETH Zürich, Spring Semester 2021, Felix Friedrich

Announcements Overview Classes Agenda Exercises Material Exams Courses

Announcements

Date Message
1.6.2021 Mock-Exam online
7.6.2021 We have a set up a moodle forum for this course to ask questions during the exam preparation phase.
25.8.2021 Fixed a bug in the master solution of exam 2019.08 (question 1f, position of 27 was incorrect). Fixed a bug in the task description of exam 2018.08 (question 4 max-flow: replaced m <= n by m <= n*n).

Overview

Abstract

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.

Learning Objective

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.

Prerequisites

Lecture Series 252-0856 Computer Science or equivalent knowledge in programming with C++.

Classes

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.

LecturesMonday 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.

Agenda

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]

Exercises

Lessons

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.

TimeLocationZoom LinkAssistantLanguage
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

Backoffice

For questions regarding the exercise management, please contact the chief assistant Aritra Dhar or Julia Chatain.

Bonus Exercises

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.

Literature and Links

Moodle Course and Forum

We have a set up a moodle page for this course including a forum to ask questions here.

Exams

In order to download old exams, please agree to the following

Old exams of OTHER courses

Remarks for Students of the virtual course 252-0002-AAL

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.