Theoretische Informatik 1: Algorithmen und Datenstrukturen, WS 2025/26

Wann, wo, wie

  • Vorlesung (Prof. U. von Luxburg): Mo 14:15 - 16:00, Hörsaal XXX, Hörsaalzentrum Morgenstelle; Fr 10:15-12:00, Hörsaal XXX, Hörsaalzentrum Morgenstelle; Erste Vorlesung ist am XXX
  • Übungsgruppen werden koordiniert von Sebastian Bordt.
  • Fragestunde/Hausaufgabenbetreuung: XXX

Semester-Anfangs-FAQ

  • Frage: Bis wann muss ich mich registrieren und wo?
    Antwort: Link und genaue Deadline kommen noch. Es gibt genug Plaetze fuer alle, die teilnehmen wollen.
  • Frage: Gibt es auch Videos zur Vorlesung oder muss ich in Person da sein?
    Antwort: Die Vorlesung findet in Person statt und wird nicht gestreamt. Es gibt noch die Videos von 2022.
  • Frage: Ich habe in einem frueheren Jahr die Klausurzulassung erhalten. Gilt die Zulassung noch, oder muss ich alles neu machen?
    Antwort: Falls Ihre Zulassung aus dem letzten Jahr kommt, also der Vorlesung von WS 2024/25, dann gilt die Zulassung noch. Wenn ihre Zulassung aus früheren Jahren ist, dann müssen Sie sie neu erwerben. In jedem Fall beachten Sie bitte, dass die Vorlesungen von mir und Lena Schlipf und Michael Kaufmann zwar ähnlich sind, aber nicht komplett gleich. Es lohnt sich also in jedem Fall, die Übungen nochmal mit zu machen.
  • Frage: Ich habe noch eine Frage, wem kann ich sie stellen?
    Antwort: bitte, bitte, schicken Sie uns nicht alle Ihre Fragen per E-Mail. Sie können ihre Fragen nach der Vorlesung oder in den Uebungsgruppen stellen.

Registrierung

Sie muessen sich bis Semesteranfang in Ilias zur Vorlesung anmelden. Link kommt noch, und Sie muessen keine Angst haben, keinen Platz zu kriegen.

Tutorien

Die Tutorien beginnen in der zweiten Semesterwoche, weitere Infos zu Terminen und Anmeldung kommen noch. Ihre Tutorinnen und Tutoren sind:

For non-German students

The lectues are in German, the slides are in english. We might try to establish 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

Folien

Übungsblätter

  • kommen hier

Lehrbücher

  • Mein Lieblingsbuch: Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms. McGraw-Hill, 2008. pdf.
  • Ein anderes Buch, das ich gut finde: Jon Kleinberg, Eva Tardos: Algorithm Design. 2005.
  • Ein Standard-Lehrbuch (nicht besonders inspirierend, aber alles drin), gibt es auf deutsch und english: Cormen, Leiserson, Rivest, Stein: Introduction to algorithms and data structures. 3rd edition. MIT Press, 2009.
  • Ein deutsches Buch (ich mag es nicht so arg): K. Mehlhorn, P. Sander, M. Dietzfelbinger: Algorithmen und Datenstrukturen. Springer, 2014. (English Version: Alorithms and Data structures: a basic toolbox)

Videos der Vorlesung

Es gibt Videos der Vorlesung von 2022: hier Ganz unten auf dieser Seite ist ein Ueberblick, was in welchem Video dran ist.

Spezielle Gruppen von Studierenden

  • Non-german students: The lectues are in german, the slides are in english. We might try to establish one tutorial group that is being taught in english. The written exam is provided in german language (but you can answer in english).
  • 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
  • Fehlt hier was? Bitte sprechen Sie mich an, ich ergänze die links gerne

Klausuren

Die Klausurzulassung müssen Sie dieses Semester durch Teilnahme an wöchentlichen Online-Quizzes erwerben. Mehr dazu in der ersten Vorlesung und im Informationsblatt zur Vorlesung.
Die Termine der Klausuren stehen noch nicht fest, sie werden in einem zentralen Prozess vergeben. Es wird zwei Klausuren geben, eine Ende Februar und eine Anfang April.
  • Sie muessen sich in Alma zur Klausur anmelden. Deadline: jeweils eine Woche vor der Klausur.
  • Sie werden nach Anmeldeschluss in verschiedene Raeume zugewiesen (alle auf der Morgenstelle).
  • Bitte seien Sie mindestens 15 Minuten früher da, so dass wir pünktlich anfangen können.
  • Bitte Ausweis und Studierendenausweis mitbringen.
  • Erlaubte Unterlagen: eine handgeschriebene (!) Seite A4 mit Notizen (einseitig, Rückseite leer). Diese Seite muss mit abgegeben werden (wird aber natürlich nicht bewertet). Ansonsten nichts, auch kein Taschenrechner.

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.


Inhalte der Videos

Link

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