Algorithmen und Datenstrukturen, WS 2022/23

News

Quick links

• Videos
• Ilias
• Einteilung der Übungsgruppen

Wann, wo, wie

• Vorlesung (Prof. U. von Luxburg): Mo 14:15 - 16:00, Hörsaal N06, Hörsaalzentrum Morgenstelle; Fr 10:15-12:00, Hörsaal N06, Hörsaalzentrum Morgenstelle; Erste Vorlesung ist am 17.10.2022
• Übungsgruppen werden koordiniert von Sebastian Bordt. Es wird viele Termine geben. Sie müssen Ihre Terminpräferenzen und einen Abgabepartner angeben: Link zur Übungsgruppenanmeldung
• Fragestunde/Hausaufgabenbetreuung: Freitags 13-15 Uhr, Raum B9N22, Morgenstelle

Materialien zur Vorlesung

Folien

• Aktuelle Version der Folien (updated 2023-01-09)

Übungsblätter

• Übungsblatt 1 (Abgabe am 31.10. in der Vorlesung)
• Übungsblatt 2 (Abgabe am 7.11. in der Vorlesung)
• Übungsblatt 3 (Abgabe am 14.11. in der Vorlesung)
• Übungsblatt 4 (Abgabe am 21.11. in der Vorlesung), Small Graph, Big Graph
• Übungsblatt 5 (Abgabe am 28.11. in der Vorlesung)
• Übungsblatt 6 (update vom 28.11) (Abgabe am 5.12. in der Vorlesung)
• Übungsblatt 7 (Abgabe am 12.12. in der Vorlesung)
• Übungsblatt 8 (Abgabe am 23.12. per Mail) sorting.ipynb
• Probeklausur. Bearbeitung freiwillig. Die Klausur enthaelt einfach ein paar Beispielaufgaben zu dem Stoff, den wir bisher in der Vorlesung behandelt haben.
• Übungsblatt 9 (Abgabe am 16.1. in der Vorlesung)
• Übungsblatt 10 (Abgabe am 23.1. in der Vorlesung)
• Übungsblatt 11 (Abgabe am 30.1. in der Vorlesung). Das ist das letzte offizielle Übungsblatt. Eventuell gibt es in der Woche drauf noch ein Blatt, das aber nur Bonuspunkte enthaelt.
• Übungsblatt 12 (Bonusblatt) (Abgabe am 6.2. PER MAIL AN IHREN TUTOR).

Videos der Vorlesung

... hier

Video 1, Einleitung
Video 2, Fibonacci, O-Notation,
Video 3, O-Notation, Laufzeitanalyse,
Video 4, Master-Theorem (Aussage)
video 5, Master-Theorem (Beweis)
Video 6, Array, Listen, Bäume, Stacks, Queues
Video 7, Heaps,
Video 8, Heaps und Hashing
Video 9, Hashing with chaining, Hashing with open adressing,
Video 10, Bloom filters,
Video 11 graphs
Video 12 dfs
Video 13 und 14, strongly connected components, topological sort (by Sebastian Bordt)
Video 15 BFS, shortest path intro (by Sebastian Bordt),
Video 16 Shortest path intro, Belman-Ford (by Sebastian Bordt)
Video 17, Belman-Ford
Video 18, Dijkstra
Video 19, floyd warshall, bidirectional dijkstra
Video 20, Astar search
Video 21: Minimal spanning tree,cut property, Kruskal
Stnde 22: Union-find data structure (ohne Beweis)
Video 23: Union-find-Beweis; Prims algorithmus
Video 24: Sortieren: selection, insertion, bubble
video 25 merge sort, heap sort
video 26 median problem (beginning)
video 27 median problem: proof;
video 28 quicksort;
video 29, stable sorting, lower bound, counting sort
video 30, radix sort
video 31, sortieren zu ende (bucket sort etc)
video 32, binaere suche
video 33 google page rank
video 34 google pagre rank
video 35 suchbaeume,
video 36 avl baeume, inverted index
video 37 und 38 Komplexitaetstheorie (P vs NP)
video 39 greedy algs
video 40 local search
video 41 dynamic programming
video 42 exhaustive search
video 43 branch and bound
video 44 approximation algorithms: set cover
video 45 approximation algorithms: vertex cover
video 46 approximation algorithms: TSP, Knapsack
video 47 Online algorithms: rental problem
video 47 Online algorithms: secretary problem
video 49 Closest pair of points: determinstic algorithms
video 50 Closest pair of points: randomized algorithms
video 51 KD trees and nearest neibhbor search
video 52 KD trees and nearest neighbor search
video 53 Nearest neighbors in high dimensions: Random projections
video 53 Nearest neighbors in high dimensions: locality sensitive hashing

Tutorien

Die Tutorien beginnen in der zweiten Semesterwoche. Ihre Tutorinnen und Tutoren sind:

• Sebastian Bordt (koordiniert den Übungsbetrieb)
• Nico Sarink, nico.sarink@student.uni-tuebingen.de
• Marcel Harter, marcel.harter@student.uni-tuebingen.de
• Georg Tirpitz, georg.tirpitz@student.uni-tuebingen.de
• Pascal Lutz, pascal.lutz@student.uni-tuebingen.de
• Osane Hackel, osane.hackel@student.uni-tuebingen.de
• Frieder Wizgall, frieder.wizgall@student.uni-tuebingen.de
• Rinor Kelmendi, rinor.kelmendi@student.uni-tuebingen.de
• Long Nguyen, long.nguyen@student.uni-tuebingen.de
• Genc Ahmeti, genc.ahmeti@student.uni-tuebingen.de
• Deborah Kornwolf, deborah.kornwolf@student.uni-tuebingen.de
• Luca Dreiling, luca.dreiling@student.uni-tuebingen.de
• Sara-Sofia Gorriz, sara-sofia.gorriz@student.uni-tuebingen.de
• Madeleine Heike, madeleine.heike@student.uni-tuebingen.de
• Steven Kraemer, steven.kraemer@student.uni-tuebingen.de

Lehrbücher

• Mein Lieblingsbuch: Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms. McGraw-Hill, 2008. Link zum pdf..
• Ein Standard-Lehrbuch (nicht besonders inspirierend, aber alles drin): Cormen, Leiserson, Rivest, Stein: Introduction to algorithms and data structures. 3rd edition. MIT Press, 2009. Gibt es auf deutsch und englisch.
• Schon etwas inspirierender (english only): Jon Kleinberg, Eva Tardos: Algorithm Design. 2005. I like it more than Cormen.
• Ein deutsches Buch (ich mag es nicht so arg): K. Mehlhorn, P. Sander, M. Dietzfelbinger: Algorithmen und Datenstrukturen. Springer, 2014. (Englische Version: Alorihtms and Data structures: a basic toolbox)

Registrierung

Sie muessen sich bis 19.10. in Ilias zur Vorlesung anmelden. Hier ist der Link.
Sie muessen sich bis 19.10. auf folgender Webseite fuer den Uebungsbetrieb anmelden: Link zur Übungsgruppenanmeldung

For non-German students

The lectues are in German, the slides are in english. We will try to install one tutorial group that is being taught in english. The written exam is provided in German language (but you can answer in english).

Allgemeine Informationen

...zur Vorlesung und zum Übungsbetrieb entnehmen Sie bitte dem folgenden Informationsblatt

Spezielle Gruppen von Studierenden

• Studierende mit Kindern
• Beratung fuer chronisch kranke oder beeinträchtigte Studierende
• Studierende mit Höreinschränkung: bitte sprechen Sie mich an, es gibt spezielle Ausrüstung in den Hörsälen
• Spitzensportler*innen
• Fehlt hier was? Bitte sprechen Sie mich an, ich ergänze die links gerne

Fragen? Kommentare? Anregungen?

Wir wollen wissen, was Ihnen an der Veranstaltung gefällt und was Ihnen nicht gefällt. Wenn Sie uns nicht persönlich ansprechen wollen, können Sie auch unser anonymes Feedback-Formular benutzen. Je konstruktiver die Kritik, desto höher die Chance, dass wir darauf eingehen.