Datenstrukturen und Algorithmen 252-0002-00L, 252-0002-AAL
Course at D-MATH (CSE) of ETH Zürich, Spring Semester 2022, Felix Friedrich
Course at D-MATH (CSE) of ETH Zürich, Spring Semester 2022, Felix Friedrich
| Date | Message |
|---|---|
| 22.2.2022 | Exercise sessions take place in physical presence. We have an additional assistant for the course for Friday 14-16h in presence (English spoken group in CHN G 22). Those who want to go to an ONLINE group: if you don't find free space in online groups any more, please register in any physical group and then go to the online session. Reason: balancing of exercise feedback. |
| 11.3.2022 |
corrected a copy-and-paste bug in the exercise slides of week 3 (page 6) |
| 18.3.2022 |
improved the binary counter slides |
| 1.5.2022 |
improved the slides on computational geometry |
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++.
| Lectures | Monday 10:15 - 12:00 | HG G 3 | Stream |
|---|---|---|---|
| Friday 08:15 - 10:00 | HG G 3 | Stream |
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 21.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]
Lecture Recording: Lecture Video Alternative Videos (2021, English): Organisation , Introduction , Asymptotics |
Organisation:
[de]
[en]
Slides 1: [de] [en] Handout 1: [de] [en] Code Example: Sorting Runtimes |
Einschreibung / Enrollment
Exercise 01: Big O Notation, Asymptotic Growth, The Set Theta(g), Code Snippets Running Times, Some Proofs, Prefix Sum in 2D |
| 2 | Fr 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]
Lecture Recording: Lecture Video Alternative Videos (2021, English): EgyptianMultiplication , KaratsubaOfman , Karatsuba:Appendix(Runtime) , Maximum-Subarray |
Slides 2:
[de]
[en]
Handout 2: [de] [en] |
Slides 01: [de] [en] |
| 3 | Mon 28.02. |
C++ advanced (I): RAII
vectors, pointers and iterators, range for, keyword auto, a class for vectors, subscript-operator, move-construction and rule of five, iterators
Lecture Recording: Lecture Video Alternative Videos (2021, English): ToolsAndMemoryManagement , EfficientMemoryManagement |
Slides 3:
[de]
[en]
Handout 3: [de] [en] |
Exercise 02: Improving Sorting, Vector Template, Nested Vectors, Sliding Window, Proofs by Induction |
| 4 | Fr 04.03. |
C++ advanced (II) Templates. templates of classes, function templates, concepts, specialisation
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] Lecture Recording: Lecture Video Alternative Videos (2021, English, concepts and specialisation not covered): Templates , Searching |
Slides 4:
[de]
[en]
Handout 4: [de] [en] |
Slides 02: [de] [en] |
| 5 | Mon 07.03. |
Search and Selection
The Selection Problem, Randomised Selection, Linear Worst-Case
Selection [Ottman/Widmayer, Kap. 3.1, Cormen et al, Kap. 9]
Algorithm of Blum, Floyd, Pratt, Rivest and Tarjan (Median of Medians) Sorting Naive Sorting Algorithms [Ottman/Widmayer, Kap. 2.1, Cormen et al, Kap. 2.1, 2.2, Exercise 2.2-2, Problem 2-2], Lecture Recording: Lecture Video Alternative Videos: QuickSelect , Blum , NaiveSorting |
Slides 5:[de]
[en]
Handout 5:[de] [en] |
Exercise 03: Recursive Function Analysis, Throwing Eggs, The Master Method, Quick-Select, Mergesort |
| 6 | Fr 11.03. |
Sorting
Mergesort [Ottman/Widmayer, Kap. 2.4, Cormen et al, Kap. 2.3], Quicksort [Ottman/Widmayer, Kap. 2.2, Cormen et al, Kap. 7]
Lecture Recording: Lecture Video Alternative Videos: Merge Sort and Quick Sort , MasterTheorem |
Slides 6: [de]
[en]
Handout 6:[de] [en] Handwritten: Master Theorem |
Slides 03: [de] [en] |
| 7 | Mon 14.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]
Lecture Recording: Lecture Video Alternative Videos: , LowerBoundsOnSorting , RadixAndBucketSort |
Slides 7:[de]
[en]
Handout 7:[de] [en] Dancing Quicksort The Sound of Sorting |
Exercise 04: Comparing Sorting Algorithms, Stable and In-Situ Sorting, Amortized Analysis: Dynamic Array, Double Ended Queue |
| 8 | Fr 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]
Lecture Recording: Lecture Video Alternative Videos: Fundamental Datastructures , Amortized Analysis , Move To Front , Skip Lists |
Slides 8:[de]
[en]
Handout 8:[de] [en] |
Slides 04: [de] [en] |
| 9 | Mon 21.03. |
Hashing Hash Tables, Pre-Hashing, Hashing, Resolving Collisions using Chaining, Simple Uniform Hashing, Popular Hash Functions,
Table-Doubling, Open Addressing: Probing, Uniform Hashing, Lecture Recording: Lecture Video Alternative Videos: Hashing 1: Closed Addressing , Hashing 2: Open Addressing |
Slides 9:[de]
[en]
Handout 9:[de] [en] |
Exercise 05: Division Method and Powers of Two, Cuckoo hashing, Open Addressing, Finding A Sub-Array (Rabin-Karp) |
| 10 | Fr 25.03. |
C++ advanced (III) Functors and Lambda
Lecture Recording: Lecture View Alternative Videos: Functors/Lambda |
Slides 10:[de]
[en]
Handout 10:[de] [en] |
Slides 05:[de] [en] |
| 11 | Mon 28.03. |
Binary Search Trees [Ottman/Widmayer, Kap. 5.1, Cormen et al, Kap. 12.1 - 12.3],
Heaps and Heapsort [Ottman/Widmayer, Kap. 2.3, Cormen et al, Kap. 6],
Lecture Recording: Lecture Video Alternative Videos: Search Trees Heaps |
Slides 11:[de]
[en]
Handout 11:[de] [en] |
Exercise 06: Binary Search Trees, AVL Trees and Heaps, Concatenating Heaps, Heaps k-smallest elements, Map/Filter/Reduce |
| 12 | Fr 01.04. |
Augmented Trees,AVL Trees Balanced Trees [Ottman/Widmayer, Kap. 5.2-5.2.1, Cormen et al, Kap. Problem 13-3]
Lecture Recording: Lecture Video Alternative Videos: AVL Trees Fibonacci (Generating Functions) |
Slides 12:[de]
[en]
Handout 12:[de] [en] |
Slides 06: [de] [en] |
| 13 | Mon 04.04 |
Quadtrees Quadtrees, Collision Detection, Image Segmentation
Dynamic Programming I Memoization, Optimal Substructure, Overlapping Sub-Problems, Dependencies, General Procedure. Examples: Fibonacci, Rod Cutting Lecture Recording: Lecture Video Alternative Videos: Quadtrees DP Intro DP Rod Cutting |
Slides 13:[de]
[en]
Handout 13:[de] [en] |
Exercise 07: Quadtrees, DP: Maximum Sum Increasing Subsequence, Piecewise Constant Approximation, Mars Mission |
| 14 | Fri 08.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]
Lecture Recording: Lecture Video Alternative Videos: Rabbits Longest Ascending Subsequence Editing Distance Matrix Chain Multiplication |
Slides 14:[de]
[en]
Handout 14:[de] [en] |
Slides 07: [de] [en] |
| 15 | Mon 11.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]
Lecture Recording: Lecture Video Alternative Videos: Subset Sum Input Sizes NP-Completeness Knapsack |
Slides 15:[de]
[en]
Handout 15:[de] [en] |
Exercise 08: Autocorrection, Enumerating Palindromes, Throwing Eggs (DP), Traveling Salesman |
| - | Fr 15.04. | -- Easter Break -- | --- | -- Easter Break -- |
| - | Mon 18.04. | -- Easter Break -- | --- | -- Easter Break -- |
| - | Thu 22.04. | -- Easter Break -- | --- | -- Easter Break -- |
| 16 | Mo 25.04. |
Dynamic Programming III Lecture Recording: Lecture Video Alternative Videos: Optimal Search Trees Huffman Coding |
Slides 16:[de]
[en]
Handout 16:[de] [en] |
Exercise 09: Huffman Code, Convex Hull, Closest Point Pair |
| 17 | Fr 29.04. |
Geometric Algorithms Properties of Line Segments, Intersection of Line Segments, Convex Hull,
Closest Point Pair [Ottman/Widmayer, Kap. 8.2,8.3,8.8.2, Cormen et al, Kap.
33]
Lecture Recording: Lecture Vide |
Slides 17:[de]
[en]
Handout 17:[de] [en] |
Slides 08: [de]
[en]
Slides 09: [de] [en] |
| 18 | Mo 02.05. |
Graphs Notation, Representation, Graph Traversal (DFS, BFS), Topological Sorting
[Ottman/Widmayer, Kap. 9.1 - 9.4,Cormen et al, Kap. 22]
Lecture Recording: Lecture Video Alternative Videos: Graphs: Intro Traversal Topological Sorting Transitive Closure |
Slides 18: [de]
[en]
Handout 18:[de] [en] |
Exercise 10: Graph traversal, topological sorting, Dijkstra. |
| 19 | Fr 06.05. |
Shortest Paths Motivation, Dijkstra’s algorithm on distance graphs, Bellman-Ford Algorithm [Ottman/Widmayer, Kap. 9.5 Cormen et al, Kap. 24.1-24.3, 25.2-25.3]
Lecture Recording: Lecture Video Alternative Videos: Shortest Paths and Dijkstra Shortest Paths with negative weights |
Slides 19:[de]
[en]
Handout 19:[de] [en] |
Slides 10: [de] [en] |
| 20 | Mo 09.05. |
Shortest Paths A*-Algorithm, Transitive Closure, All Pairs Shortest Paths: Floyd-Warshall Algorithm, Lecture Recording: Lecture Video Alternative Videos: A* Algorithm All Pairs Shortest Paths |
Slides 20:[de]
[en]
Handout 20:[de] [en] |
Exercise 11:
All Pairs Shortest Paths: Closeness Centrality, Union-Find, Minimum Spanning Trees |
| 21 | Fr 13.05 |
Minimum Spanning Trees Motivation, Greedy, Algorithm Kruskal, ADT Union-Find, Algorithm Jarnik/Prim/Dijkstra [Ottman/Widmayer, Kap. 9.6, 6.2, 6.1, Cormen et al, Kap. 23, 19] Fibonacci Heaps
Lecture Recording: Lecture Video Alternative Videos: Minimum Spanning Trees Fibonacci Heaps |
Slides 21:[de]
[en]
Handout 21:[de] [en] |
Slides 11:[de] [en] |
| 22 | Mo 16.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: Lecture Video Alternative Videos: Max-Flow Intro Max-Flow Min-Cut Ford Fulkerson and Edmonds Karp Maximum Matching |
Slides 22:[de]
[en]
Handout 22:[de] [en] |
Exercise 12:
Manual Max-Flow, Applying Max-Flow, Min-Cut Problems, Speeup, Amdahl Gustavson, Sum of a Vector, Parallel Sorting |
| 23 | Fr 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: TBA Alternative Videos: Parallelism and Concurrency C++ Threads Task Parallelism Scalability |
Slides 23:[de]
[en]
Handout 23:[de] [en] |
Slides 12: [de] [en] |
| 24 | Mo 23.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: TBA Alternative Videos: Race Conditions |
Slides 24:[de]
[en]
Handout 24:[de] [en] |
Exercise 13: |
| 25 | Fr 27.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: TBA Alternative Videos: Deadlocks And Monitors |
Slides 25:[de]
[en]
Handout 25:[de] [en] |
Slides 13: [de] [en] |
| 26 | Mo 30.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]
Lecture Recording: TBA Alternative Videos: Futures, RMW And Lock-Free Programming |
Slides 26:[de]
[en]
Handout 25:[de] [en] |
(Exercise 14:) |
| 27 | Fr 03.06. |
TBD
Lecture Recording: TBA |
Alle Folien dieser Vorlesung / all slides of this course:
Overlays: [de] [en] Handout: [de] [en] Handout 2x2:[de] [en] |
Slides 14: [de] [en] |
Exercise sessions are conducted in physical presence, with the exception of the two sessions marked as ONLINE. The zoom links of the online sessions can be found here
| Time | Location | Zoom Link | Assistant | Language |
|---|---|---|---|---|
| Friday 10:15 - 12:00 | CAB G 59 | Bastian Seifert | deutsch | |
| Friday 10:15 - 12:00 | LFW B 2 | Ciril Humbel | deutsch | |
| Friday 10:15 - 12:00 | NO C 6 | Kamelia Ivanova | english | |
| Friday 10:15 - 12:00 | RZ F 21 | Nicholas Engel | deutsch | |
| Friday 10:15 - 12:00 | ONLINE | link | Vedran Mihal | english |
| Friday 14:15 - 16:00 | CAB G 57 | Ivana Klasovitá | english | |
| Friday 14:15 - 16:00 | CHN D 42 | Leonard Knirsch | deutsch | |
| Friday 14:15 - 16:00 | CHN D 48 | Felix Vittori | deutsch | |
| Friday 14:15 - 16:00 | CHN G 22 | Mohamed-Hicham Leghettas | english | |
| Friday 14:15 - 16:00 | ONLINE | link | Harun Mustafa | english |
For questions regarding the exercise management, please contact the chief assistant Julia Chatain (English or French only).
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.