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

Wann, wo, wie

  • Vorlesung (Prof. U. von Luxburg):
    Mo 14:15 - 16:00, Hörsaal N7, Hörsaalzentrum Morgenstelle
    Fr 10:15-12:00, Hörsaal N6, Hörsaalzentrum Morgenstelle
    Erste Vorlesung ist am 13.10.2025
  • Übungsgruppen starten in der zweiten Semesterwoche und werden koordiniert von Sebastian Bordt.
  • Fragestunde/Hausaufgabenbetreuung: Freitag Nachmittags, Hörsaal N11
➤ Link zu Ilias (Registrierung)

Semester-Anfangs-FAQ

  • Bis wann muss ich mich zur Vorlesung registrieren und wo?
    Link siehe oben. Deadline: Montag, 13.10. Es gibt genug Plätze für alle, die teilnehmen wollen.
  • Bis wann muss ich mich zu den Übungsgruppen registrieren, und wo?
    Die Registrierung findet während (!) der ersten Vorlesung statt, also bitte teilnehmen.
  • Gibt es auch Videos zur Vorlesung oder muss ich in Person da sein?
    Die Vorlesung findet in Person statt und wird nicht gestreamt. Es gibt noch die Videos von 2022, siehe unten.
  • Ich habe in einem früheren Jahr die Klausurzulassung erhalten. Gilt die Zulassung noch, oder muss ich alles neu machen?
    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.
  • I am very interested in attending this course, but I am slightly concerned about my German language level. How likely is it that there is an english tutorial group, and will the exam questions also be provided in english?
    We will be able to tell you at the end of the first week about the tutorial. In particular, please do attend the first lecture, in which we try to distribute students to tutorial groups. If there are enough students for the english one, we will establish one. If we have one english tutorial group, we will also offer the exam in english as well.
  • Ich habe noch eine Frage, wem kann ich sie stellen?
    Bitte schicken Sie uns nicht alle Ihre Fragen per E-Mail, das skaliert nicht. Sie können ihre Fragen nach der Vorlesung oder in den Übungsgruppen an uns persönlich stellen.

Registrierung

  • Sie müssen sich bis Semesteranfang in Ilias zur Vorlesung anmelden. Link zur Ilias-Veranstaltung.
  • Die Anmeldung zu den Übungsgruppen wird während (!) der ersten Vorlesung freigeschaltet und muss bis Mittwoch, 15.10. abgeschlossen sein. Die Anmeldung erfolgt über Ilias.

Informationsblatt

Alles zur Organisation der Vorlesung können Sie hier nachlesen.

Tutorien

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

Übungsgruppe Tag Uhrzeit Raum Tutor Email
Übungsgruppe 1 (in English!) Dienstag 8-10 CSH05 Thomas Lucke thomaslucke@web.de
Übungsgruppe 2 Dienstag 8-10 8D10 Leonie Rämisch leonie.raemisch@student.uni-tuebingen.de
Übungsgruppe 3 Dienstag 14-16 8D09 Amaline Ritter amaline.ritter@student.uni-tuebingen.de
Übungsgruppe 4 Dienstag 14-16 N09 Sawani Patwardhan sawani.patwardhan@student.uni-tuebingen.de
Übungsgruppe 5 Mittwoch 12-14 N08 Karl Gauck karl.gauck@student.uni-tuebingen.de
Übungsgruppe 6 Mittwoch 12-14 8D10 Dominic Braun dominic.braun@student.uni-tuebingen.de
Übungsgruppe 7 Mittwoch 12-14 C9A03 Benedict Sondershaus benedict.sondershaus@student.uni-tuebingen.de
Übungsgruppe 8 Mittwoch 12-14 1B01 Daniel Wiorek daniel.wiorek@student.uni-tuebingen.de
Übungsgruppe 9 Mittwoch 16-18 1B01 Rosa Biehler rosa.biehler@student.uni-tuebingen.de
Übungsgruppe 10 Mittwoch 16-18 N08 Benedict Bleidt benedict.bleidt@student.uni-tuebingen.de
Helpdesk Freitag 13-15 N11 Nils Goertler nils.goertler@student.uni-tuebingen.de

Der Übungsbetrieb wird koordiniert von Sebastian Bordt.

For non-German students

The lectures are in German, the slides are in english. Übungsgruppe 1 by Thomas Lucke is taught in english. The written exam is provided in German language (but you can answer in english).

Allgemeine Informationen

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

Folien

Übungsblätter

  • Übungsblätter sind auf Ilias. Dort werden die Blätter auch abgegeben.

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: Algorithms and Data structures: a basic toolbox)

Videos der Vorlesung

Es gibt Videos der Vorlesung von 2022: hier
Ganz unten auf dieser Webseite ist ein Überblick, was in welchem Video dran ist. Aber Achtung: keine Garantie, dass dieses Jahr nicht einzelne Themen anders / gar nicht / zusätzlich besprochen werden.

Spezielle Gruppen von Studierenden

  • Non-german students: The lectures 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 für 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 müssen sich in Alma zur Klausur anmelden. Deadline: jeweils eine Woche vor der Klausur.
  • Sie werden nach Anmeldeschluss in verschiedene Räume 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 von 2022

Link zu den Videos

  • 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
  • Video 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, binäre suche
  • Video 33, google page rank
  • Video 34, google page rank
  • Video 35, suchbäume
  • Video 36, avl bäume, inverted index
  • Video 37 und 38, Komplexitätstheorie (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 48, Online algorithms: secretary problem
  • Video 49, Closest pair of points: deterministic algorithms
  • Video 50, Closest pair of points: randomized algorithms
  • Video 51, KD trees and nearest neighbor search
  • Video 52, KD trees and nearest neighbor search
  • Video 53, Nearest neighbors in high dimensions: Random projections
  • Video 54, Nearest neighbors in high dimensions: locality sensitive hashing