Datenstrukturen und Algorithmen

Datum	Mitteilung
18.12.2019	published August 2019 exam. See below (Alte Prüfungen). Please find the electronic online part of the exams here
8.1.2020	In order to get access to the master solutions of the moodle mock exams, we have now made the corresponding code-expert course accessible. You can subscribe to this course here .

Vorlesung	Montag 10:15 - 12:00	ML F 36
	Donnerstag 08:15 - 10:00	ML E 12
Übungen	Freitag 08:15-10:00, 10:15-12:00	Verschiedene Räume (s.u.)

Zeitplan, Folien und Übungen

Dies ist ein Plan und als solcher unterliegt er Änderungen -- auch und insbesondere nach Semesterbeginn.

Termin	Datum	Thema	Folien und Handout	Übungen, Lösungsskizzen	PPrerequisites to unlock bonus exercises	BBonus exercises
1	MO 18.02.	Begriff des Algorithmus, Effizienz von Algorithmen, Random Access Machine Modell, Asymptotik: O-Notation, Omega, Theta,	Organisation: [de] [en] Slides 1: [de] [en] Handout 1: [de] [en]	Einschreibung / Enrollment	Skiplist
2	DO 21.02.	Korrektheit und Effizienz von Algorithmen an Beispielen: Altägyptische Multiplikation, Schnelle Multiplikation grosser Zahlen; Entwurf von Algorithmen: Maximum Subarray (naiv, Präfixsummen, Divide and Conquer, linear)	Slides 2: [de] [en] Handout 2: [de] [en]	O, Theta and Omega, asymptotic running times and 2d prefix sum Slides: [de] [en]
3	MO 25.02.	Suchen und Auswählen Lineare Suche, Binäre Suche, untere Schranken für das Suchen, Das Auswahlproblem, Randomisierte Berechnung des Medians, Auswahl in linearer Zeit	Slides 3:[de] [en] Handout 3:[de] [en]	---
4	DO 28.02.	C++ Vertieft (I) Kurzwiederholung (Vektoren, Zeiger und Iteratoren), Bereichsbasiertes for, Schlüsselwort auto, eine Klasse für Vektoren, Subskript-Operator, Move-Konstruktion, Iteration.	Slides 4:[de] [en] Handout 4:[de] [en]	Induction Proofs, Running Times, Median Algorithms, Vectors Slides: [de] [en]
5	MO 04.03.	Sortieren I: Insertion-Sort, Selection-Sort, Bubble-Sort, Shell-Sort Sortieren II: Heapsort: implizite Repräsentation vom Heap im Array, Heapbilden in Linearzeit, Mergesort, Quicksort: Schlüsselvergleiche im besten/schlechtesten Fall.	Slides 5:[de] [en] Handout 5:[de] [en]	---		Skiplist
6	DO 07.03.	Fortsetzung Sortieren II	Slides 6: [de] [en] Handout 6:[de] [en]	Compare Sort Algorithms, Vector Implementation and Heap-Sort Slides: [de] [en]
7	MO 11.03.	Sortieren III: Schlüsselbewegungen und Speicherbedarf beim Quicksort, Quicksort randomisiert, Untere Schranken, Radixsort. C++ II: Templates.	Slides 7:[de] [en] Handout 7:[de] [en]	---	AVL Tree
8	DO 14.03.	Elementare Datenstrukturen Stapel, Warteschlange, Implementationsvarianten der verkettete Liste Amortisierte Analyse beim Multistack Wörterbücher : Amortisierte Analyse Move-To-Front, Skipliste	Slides 8:[de] [en] Handout 8:[de] [en]	Amortized Analysis Dynamic Array, Vector Template Slides: [de] [en]
9	MO 18.03.	Wörterbücher II: Hashing Hashtabellen, Pre-Hashing, Kollisionsauflösung durch Verkettung, Einfaches Gleichmässiges Hashing, Übliche Hashfunktionen,	Slides 9:[de] [en] Handout 9:[de] [en]	---
10	DO 21.03.	Hashing ctd Tabellenvergrösserung, offene Hashverfahren (Sondieren), Gleichmässiges Hashing, Universelles Hashing, Perfektes Hashing.		Hashing: Open Hashing, Cockoo Hashing, Division Method, Rabin-Karp Slides: [de] [en]
11	MO 25.03.	(Perfect Hashing ctd.) C++ III Funktoren und Lambda.	Slides 10:[de] [en] Handout 10:[de] [en]	---		AVL Tree
12	DO 28.03.	Wörterbücher III: Bäume Natürliche Suchbäume, AVL Bäume	Slides 11:[de] [en] Handout 11:[de] [en]	Binary Search Trees, AVL Trees and Heaps, Functors and Lambdas Slides: [de] [en]
13	MO 01.04.	AVL Bäume ctd. Quadtrees Kollisionsdetektion, Bildsegmentierung	Slides 12:[de] [en] Handout 12:[de] [en]	---			Max-Flow Edmonds-Karp
14	DO 04.04.	Quadtrees ctd. Dynamische Programmierung I Fibonacci, Rod-Cutting	Slides 13:[de] [en] Handout 13:[de] [en]	Quadtrees: Image Segmentation, Dynamic Programming: Mars Rover, Signal Approximation Slides: [de] [en]
15	MO 08.04.	Dynamische Programmierung I ctd Längste aufsteigende Teilfolge, Editierdistanz (inkl. Längste Gemeinsame Teilfolge), Matrixkettenmultiplikation, Matrixmultiplikation nach Strassen		---
16	DO 11.04.	Dynamische Programmierung II Subset Sum Problem, Rucksackproblem, Greedy Algorithmus, Lösungen mit dynamischer Programmierung Dynamic Programming III FPTAS	Slides 14:[de] [en] Handout 14:[de] [en]	DP Slides: [de] [en]
17	MO 15.04.	Greedy Algorithmen Dynamic Programming vs. Greedy. Gebrochenes Rucksackproblem, Huffman Coding	Slides 15: [de] [en] Handout 15:[de] [en] [handwritten]	---
18	DO 18.04.	Graphenalgorithmen I Notation, Repräsentationsarten, Traversieren (DFS, BFS), Topologisches Sortieren	Slides 16:[de] [en] Handout 16:[de] [en] [handwritten]	Hufmann Coding, Graph Traversal, Topological Sorting
-	MO 22.04.	-- Ostern --	---	-- Ostern --
-	DO 25.04.	-- Ostern --	---	-- Ostern --
19	MO 29.04	Graphenalgorithmen II: Kürzeste Wege Dijkstras Algorithmus auf Distanzgraphen, Algorithmus von Bellman-Ford	Slides 17:[de] [en] Handout 17:[de] [en] [handwritten]	---	Max-Flow Edmonds Karp
20	DO 02.05.	Graphenalgorithmen II: Kürzeste Wege Algorithmus von Floyd-Warshall, Algorithmus von Johnson		Shortest Paths: Path planning in labyrinths, graph distances, Dijkstra, Closeness Centrality Slides: [de] [en]
21	MO 06.05.	Graphenalgorithmen III: Minimale Spannbäume Greedy, Algorithmus von Kruskal, Allgemeine Regeln, Union-Find Struktur, Algorithmus von Jarnik,Prim,Dijkstra, Fibonacci Heaps	Slides 18:[de] [en] Handout 18:[de] [en] [handwritten]	---		Parallel Programming
22	DO 09.05.	Graphenalgorithmen IV: Flüsse in Graphen Flussnetzwerk, Maximaler Fluss, Schnitt, Restnetzwerk, Max-flow Min-cut Theorem, Ford-Fulkerson Methode, Edmonds-Karp Algorithmus, Maximales Bipartites Matching	Slides 19:[de] [en] Handout 19:[de] [en] [handwritten]	Minimum Spanning Trees, Union Find, Manual Max-Flow Slides: [de] [en]
23	MO 13.05.	Graphenalgorithmen IV: Flüsse in Graphen (ctd.) Flussnetzwerk, Maximaler Fluss, Schnitt, Restnetzwerk, Max-flow Min-cut Theorem, Ford-Fulkerson Methode, Edmonds-Karp Algorithmus, Maximales Bipartites Matching Parallele Programmierung I Moore's Law und The Free Lunch, Parallele Ausführung, Hardware Architekturen,	Slides 20:[de] [en] Handout 20:[de] [en]	---
24	Do 16.05.	Parallele Programmierung I (ctd.) Klassifikation nach Flynn, Multi-Threading, Threads in C++, Parallelität und Nebenläufigkeit, Skalierbarkeit: Amdahl und Gustafson, Daten- und Taskparallelität, Scheduling	[handwritten]	Applying Max Flow, Speedup and Task Parallelism, C++ Threads Slides: [de] [en]
25	MO 20.05.	Parallele Programmierung II Gemeinsamer Speicher, Concurrency, Mutual Exclusion und Race Conditions Data-Race, Interleavings, Memory-Reordering	Slides 21:[de] [en] Handout 21:[de] [en]	---
26	DO 23.05.	Parallele Programmierung III Deadlocks, Deadlock Erkennung und Vermeidung, Producer / Consumer, Monitore und Condition Variablen, Condition Variablen in C++,	Slides 22:[de] [en] Handout 22:[de] [en]	Race Conditions, Deadlock and Starvation, Condition Variables, Lock Granularity Slides: [de] [en]
27	Mo 27.05.	Parallele Programmierung IV C++ Futures, Atomare Register und RMW Operationen, Idee der Lock-freien Programmierung	Slides 23:[de] [en] Handout 23:[de] [en] Alle Folien dieser Vorlesung / all slides of this course: Overlays: [de] [en] Handout: [de] [en] Handout 2x2:[de] [en]	---
-	DO 30.05.	-- Auffahrt --	---	Slides: [de] [en]

Übungen

Einschreibung für die Übungen

Die Einschreibung zum Übungssystem erfolgt online. Weitere Informationen während der ersten Vorlesung.

Orte und Zeiten

Die Übungsgruppen sind derzeit wie folgt zugeteilt:

Zeit	Ort	Assistent	Sprache
Fr, 08:15 - 10:00	CAB G 57	Philippe Schlattner	english
Fr, 10:15 - 12:00	CAB G 59	Jan Stratmann	deutsch
Fr, 10:15 - 12:00	HG D 1.2	Robin Worreby	deutsch
Fr, 10:15 - 12:00	RZ F 21	Robin Vogtland	deutsch

*: Engl. Übungsgruppe

Kontakt

Felix Friedrich (Dozent)

Diskussionsforum: Slack Link (invite link)

Zur Prüfung

Prüfungsstoff für die Endprüfung, welche in der Prüfungssession Sommer 2017 stattfinden wird, schliesst Vorlesungsinhalt und Übungsinhalte ein.

Die Prüfung ist schriftlich. Erlaubte Hilfsmittel: Vier A4 Seiten (zwei A4 Blätter), handgeschrieben oder min. Fontgrösse 11 Pkt.

Alte Prüfungen

Zum Einsehen alter Prüfungen, erklären Sie bitte Ihr Einverständnis: In order to download old exams, please agree to the following

Ich habe verstanden, dass neue Prüfungen in Form und Inhalt von alten Prüfungen abweichen können. Lernen alter Prüfungen ersetzt nicht das Verständnis der Vorlesungs- und Übungsinhalte. I have understood that new exams can differ in both form and content from previous exams. Learning from old exams does not replace the comprehension of lecture and exercise contents

Ich habe verstanden, dass das Hinzuziehen einer Musterlösung während des Probelösens eine Prüfung einfacher erscheinen lässt und keine realistische Prüfungssituation widerspiegelt.I have undestood that looking at the master solution while test-solving an exam makes the exam look much simpler and thus does not reflect a realistic exam conditions.

Alte Prüfung ANDERER Vorlesungen Old exams of OTHER courses

Ich habe verstanden, dass es sich um Prüfungen anderer Vorlesungen handelt und die Themen der Vorlesungen nur in Teilen überlappen.I have undestood that these are exams of other courses and the topics do only partially overlap.

Literatur

Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011, auch online / download.
Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein: Algorithmen - Eine Einführung, Oldenbourg, 2010
Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009. ISBN 978-0-262-03384-8 (recommended english text book)
Maurice Herlihy, Nir Shavit, The Art of Multiprocessor Programming, Elsevier, 2012.
Anthony Willians, C++ Concurrency in Action, Manning, 2012
B. Stroustrup, The C++ Programming Language (4th Edition) Addison-Wesley, 2013.
Genaue Behandlung der zugrundeliegenden Mathematik im Buch Concrete Mathematics von Graham, Knuth und Patashnik. [Geht weit über die benötigten Mittel der Vorlesung hinaus].

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.

Kind regards, Felix Friedrich.