Course at DMATH (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:1510:00, 10:1512: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, divideandconquer, 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 unionfind 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 waitfreedom). 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 2520856 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.24.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. 44.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.13,2.23,2.35], The Selection Problem, Randomised Selection, Linear WorstCase 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, subscriptoperator, moveconstruction, 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.22, Problem 22], 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.11.5.2, Cormen et al, Kap. 10.1.10.2], Amortized Analyis Aggregate Analysis, AccountMethod, PotentialMethod [Ottman/Widmayer, Kap. 3.3, Cormen et al, Kap. 17], Dictionaries Selfordering List, Implementation of Dictionaries with Array / List /Skip lists. [Ottman/Widmayer, Kap. 3.3,1.7, Cormen et al, Kap. Problem 175] 
Slides 8:[de]
[en]
Handout 8:[de] [en] 
Amortized Analysis, Dynamic Array, Vector Template Slides: [de] [en] 

9  MO 16.03.  Hashing Hash Tables, PreHashing, Hashing, Resolving Collisions using Chaining, Simple Uniform Hashing, Popular Hash Functions, TableDoubling, Open Addressing: Probing, Uniform Hashing, Universal Hashing, Perfect Hashing [Ottman/Widmayer, Kap. 4.14.3.2, 4.3.4, Cormen et al, Kap. 1111.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, RabinKarp 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.25.2.1, Cormen et al, Kap. Problem 133] 
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 SubProblems, 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] 
  MaxFlow EdmondsKarp  
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, BellmanFord Algorithm, FloydWarshall Algorithm [Ottman/Widmayer, Kap. 9.5 Cormen et al, Kap. 24.124.3, 25.225.3] 
Slides 18:[de]
[en]
Handout 18:[de] [en] 
Graph Traversal, Topological Sorting, SingleSource 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] 
  MaxFlow Edmonds Karp  
20  DO 30.04. 
Minimum Spanning Trees Motivation, Greedy, Algorithm Kruskal, General Rules, ADT UnionFind, 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, Maxflow Mincut Theorem, FordFulkerson Method, EdmondsKarp Algorithm, Maximal Bipartite Matching [Ottman/Widmayer, Kap. 9.7, 9.8.1], [Cormen et al, Kap. 26.126.3]  (slide set 21 continued) 
Manual MaxFlow, Network Reliability, Applying MaxFlow Slides: [de] [en] 

23  MO 11.05.  Flow in Networks: PushRelabel 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, Dataparallelism, Taskparallelism, Scheduling [TaskScheduling: 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.12.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 ProducerConsumer, The concept of the monitor, Condition Variables [Deadlocks : Williams, Kap. 3.2.43.2.5] [Condition Variables: Williams, Kap. 4.1] 
Slides 25:[de]
[en]
Handout 25:[de] [en] > 

27  Do 28.05.  Parallel Programming IV Futures, ReadModifyWrite Instructions, Atomic Variables, Idea of lockfree programming [C++ Futures: Williams, Kap. 4.2.14.2.3] [C++ Atomic: Williams, Kap. 5.2.15.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 selfcontained.
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.