Datenstrukturen und Algorithmen

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 find errors in the translation, please provide feedback to me. The translation was done on the fly when preparing the German slides and thus might contain some flaws.

If you want to take the real course, you will have to wait for spring semester. Then the course is offered with (German spoken) lectures and (German or English spoken) recitation sessions again.

Datum	Mitteilung

Termine

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

Lernziel und Überblick

Es werden grundlegende Entwurfsmuster für Algorithmen (z.B. Induktion, divide-and-conquer, backtracking, dynamische Programmierung), klassische algorithmische Probleme (Suchen, Sortieren) und Datenstrukturen (Listen, Hashverfahren, Suchbäume) behandelt. Ausserdem enthält der Kurs eine Einführung in das parallele Programmieren. Das Programmiermodell von C++ wird vertieft behandelt.

Lernziel: Verständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen. Wissen um die Chancen, Probleme und Grenzen der parallelen und nebenläufigen Programmierung. Vertiefter Einblick in ein modernes Programmiermodell anhand der Programmiersprache C++(14).

Vorrausetzung: Vorlesung Informatik I (D-ITET) oder gleichwertige Kenntnisse. Folien und Skript zur Vorlesung Informatik I finden Sie hier

Zeitplan, Folien und Übungen

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

Woche	Datum	Thema	Folien und Handouts	Übungen, Lösungsskizzen	PPrerequisites to unlock bonus exercises	BBonus exercises
1	MO 19.02.	Begriff des Algorithmus, drei Beispiele: Altägyptische Multiplikation, Schnelle Multiplikation grosser Zahlen, Finde den Star	Organisation (english) Folien 1 (en) Handout 1 (en)	Einschreibung Uebungen	Skiplist
1	DO 22.02.	Effizienz von Algorithmen, Random Access Machine Modell, Asymptotik: O-Notation, Omega, Theta, Entwurf von Algorithmen: Maximum Subarray (naiv, Präfixsummen, Divide and Conquer, linear)	Folien 2 (en) Handout 2 (en)	Asymptotics, Prefix Sum in 2D Folien (english)
2	MO 26.02.	Suchen und Auswählen Lineare Suche, Binäre Suche, Interpolationssuche, Exponentielle Suche, untere Schranken, Das Auswahlproblem, Randomisierte Berechnung des Medians, Auswahl in linearer Zeit	Folien 3 (en) Handout 3 (en)
2	DO 01.03.	C++ Vertieft (I) Kurzwiederholung (Vektoren, Zeiger und Iteratoren), Bereichsbasiertes for, Schlüsselwort auto, eine Klasse für Vektoren, Subskript-Operator, Move-Konstruktion, Iteration.	Folien 4 (en) Handout 4 (en) code: Vektoren code: Move Semantik	Induction Proofs, Running Times, Recursion and Selection Algorithms Folien (english)
3	MO 05.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.	Folien 5 (en) Handout 5 (en)			Skiplist
3	DO 08.03.	Fortsetzung Sortieren II C++ II: Templates.	Folien 6 (en) Handout 6 (en) code: Templates (Pair)	Sorting Algorithms, Vector and Heapsort Bonus Exercise: SkipList Folien (english)
4	MO 12.03.	Fortsetzung C++ II Templates Sortieren III: Schlüsselbewegungen und Speicherbedarf beim Quicksort, Quicksort randomisiert, Untere Schranken, Radixsort.	Folien 7 (en) Handout 7 (en)		AVL Tree
4	DO 15.03.	Elementare Datenstrukturen Stapel, Warteschlange, Implementationsvarianten der verkettete Liste, Amortisierte Analyse beim Multistack Wörterbücher II : Array, verkettete Liste, Amortisierte Analyse Move-To-Front, Skipliste	Folien 8 (en) Handout 8 (en)	Amortized Analysis (Dynamic Array), Self-Ordered Lists Folien (english)
5	MO 19.03.	C++ III Funktoren und Lambda. Wörterbücher III Prinzip des Hashing, Hashfunktionen, Kollisionsauflösung durch Verkettung, offene Hashverfahren	Folien 9 (en) Handout 9 (en) code: Funktoren und Lambdas
5	DO 22.03.	Wörterbücker III ctd. C++ IV: Ausnahmen	Folien 10 (en) Handout 10 (en) code: Exceptions and Resources code: Exceptions and Operators code: Exceptions (Expression Parsing)	Open Hashing, Cockoo Hashing and Finding a Subarray Folien (english)
6	MO 26.03.	Wörterbücher IV Natürliche Suchbäume, AVL Bäume	Folien 11 (en) Handout 11 (en)			AVL Tree
6	DO 29.03.	AVL Tress ctd. Quadtrees Kollisionsdetektion, Bildsegmentierung	Folien 12 (en) Handout 12 (en)	Search Trees Bonus Exercise 2: AVL Trees
-	MO 02.04.		-- Ostern --	-- Ostern --
-	DO 05.04.		-- Ostern --	-- Ostern --
7	MO 09.04.	Dynamische Programmierung I Fibonacci, Längste aufsteigende Teilfolge, längste gemeinsame Teilfolge, Editierdistanz, Matrixkettenmultiplikation, Matrixmultiplikation nach Strassen	Folien 13 (en) Handout 13 (en)		Max-Flow Edmonds-Karp
7	DO 12.04.	Dynamische Programmierung II Subset Sum Problem, Rucksackproblem, Greedy Algorithmus, Lösungen mit dynamischer Programmierung	Folien 14 (en) Handout 14 (en)	Dynamic Programming Folien (english) bitmap.ccp, images.ccp
8	MO 16.04.	Dynamic Programming III FPTAS Greedy Algorithmen Dynamic Programming vs. Greedy. Gebrochenes Rucksackproblem, Huffman Coding	Folien 15 (en) Handout 15 (en) Interessante Vorlesung zum Thema NP-Vollständigkeit
8	DO 19.04.	Graphenalgorithmen I Notation, Repräsentationsarten, Graphen und Relationen, Reflexive transitive Hülle, Traversieren (DFS, BFS), Zusammenhangskomponenten, Topologisches Sortieren	Folien 16 (en) Handout 16 (en)	Hufmann Coding und Graphen Folien (english)
9	MO 23.04.	Graphenalgorithmen II: Kürzeste Wege Dijkstras Algorithmus auf Distanzgraphen, Algorithmus von Bellman-Ford, Algorithmus von Floyd-Warshall, Algorithmus von Johnson	Folien 17 (en) Handout 17 (en)
9	DO 26.04.	Graphenalgorithmen III: Minimale Spannbäume Greedy, Algorithmus von Kruskal, Allgemeine Regeln, Union-Find Struktur, Algorithmus von Jarnik,Prim,Dijkstra, Fibonacci Heaps	Folien 18 (en) Handout 18 (en)	Shortest Paths and Minimal Spanning Trees Folien (english)
10	MO 30.04	Graphenalgorithmen III: Minimale Spannbäume Fortsetzung				Max-Flow Edmonds Karp
10	DO 03.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	Folien 19 (en) Handout 19 (en)	Minimal Spanning Trees + MaxFlow Folien (english)
11	MO 07.05.	Flüsse in Graphen (Fortsetzung)			Parallel Programming
11	DO 10.05.	Auffahrt		Application of MaxFlow Folien (english)
12	MO 14.05.	Parallele Programmierung I Moore's Law und The Free Lunch, Parallele Ausführung, Hardware Architekturen, Klassifikation nach Flynn, Multi-Threading, Parallelität und Nebenläufigkeit, Skalierbarkeit: Amdahl und Gustafson, Daten- und Taskparallelität, Scheduling	Folien 20 (en) Handout 20 (en)
12	DO 17.05.	Parallele Programmierung II Threads in C++, Gemeinsamer Speicher, Concurrency, Mutual Exclusion und Race Conditions	Folien 21 (en) Handout 21 (en)	Parallel Programming I Folien (english)

-	Mo 21.05.	PFINGSTEN				Parallel Programming
13	Do 24.05.	(Parallele Programmierung II ctd.) Data-Race, Interleavings, Memory-Reordering Parallele Programmierung III Deadlocks, Deadlock Erkennung und Vermeidung, Producer / Consumer, Monitore und Condition Variablen, Condition Variablen in C++,	Folien 22 (en) Handout 22 (en) (Counter)Examples from the lectures: Bank_Account_Sequential Thread_Unsafe_Counter	Parallel Programming II Folien (english)
14	MO 28.05.	Parallele Programmierung IV C++ Futures, Atomare Register und RMW Operationen, Idee der Lock-Freien Programmierung	Folien 23 (en) Handout 23 (en) Examples from the lectures: Self-made Future Using C++11 Futures Lock-Free Stack
14	DO 31.05.	Parallele Programmierung V	Folien 24 Alle Folien (en) Alle Handouts (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	Marija Kranjcevic	english
Fr, 10:15 - 12:00	CAB G 59	Anian Ruoss	deutsch
Fr, 10:15 - 12:00	HG D 1.2	Philippe Schlattner	deutsch
Fr, 10:15 - 12:00	RZ F 21	Friedrich Ginnold	deutsch

*: Engl. Übungsgruppe

Kontakt

Alexander Pilz (Chef-Assistent)

Felix Friedrich (Dozent)

Slack Link (Diskussionsforum)

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

Datenstrukturen und Algorithmen
Parallel Programming (nur sehr eingeschränkt anwendbar, zumal mit Java, am ehesten die Theorieteile): (applicable to this course only in a very limited way, old exams with Java)
BP_2017_Winter (Solution)
BP_2016_Summer (Solution)
BP_2015_Winter (Solution)
BP_2015_Summer (Solution)
BP_2014_Winter (English) BP_2014_Winter (German) (Solution)
BP_2014_Summer (English) BP_2014_Summer (German) (Solution)

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