Proseminar Datenstrukturen und Algorithmen

Schedule

TypeDayTimeRoomStartLecturer
Introductionthursday4201b (i2 seminar room)Thomas Noll
Block seminartbatbatbaThomas Noll

Wintersemester 2026/27

Einführung und Themenvergabe

Termine

Datum Termin
Donnerstag, 15.10.2026, 16:30 Einführungsveranstaltung (Seminarraum 4201b, 2. Stock, Gebäude E1, Informatikzentrum)
19.10.2026 Frist für Themenauswahl
28.10.2026 Letzte Rücktrittsmöglichkeit
16.11.2026 Vorlage der detaillierten Vortragsstruktur
14.12.2026 Vollständige Fassung der Folien
11.-14.01.2027 Blockseminar (halber Tag; wird noch abgestimmt)
01.02.2027 Einreichung der Ausarbeitung

Beachten Sie, dass die vollständige Fassung der Vortragsfolien Ihre zu bewertende Einreichung darstellt und sich von der endgültigen Version nur durch kleinere Anpassungen unterscheiden sollte, die nach Rücksprache mit der betreuenden Person erfolgen. Es ist aber möglich (und dringend empfohlen!), vor den jeweiligen Fristen Entwurfsversionen Ihrer Ergebnisse einzureichen.

Themen

Dieses Proseminar bietet eine Weiterführung und Vertiefung diverser Themen, die im Rahmen der Vorlesung Datenstrukturen und Algorithmen behandelt werden. Die folgenden Tabellen geben einen vollständigen Überblick.

Algorithmen

Nr. Thema Referent/in Betreuer/in
1 PageRank-Algorithmus Jonah Dargel Darion Haase
2 Huffman-Kodierung Yingjie Wang Daniel Zilken
3 LZW-Datenkompression – –
4 RSA-Kryptosystem – –
5 Deutsch-Schorr-Waite Baumtraversierung – –
6 Problem der K kürzesten Pfade – –
7 Amortisierte Laufzeitanalyse – –
8 String Matching – –
9 Lineare Programmierung – –
10 A*-Suchalgorithmus Andrii Kozak Darion Haase
11 Randomisierte Algorithmen – –

Datenstrukturen

Nr. Thema Referent/in Betreuer/in
12 Fibonacci-Heaps – –
13 Splay-Bäume – –
14 R-Bäume – –
15 Bitstate Hashing – –
16 Binäre Entscheidungsdiagramme – –
17 Spielbäume JM Daniel Zilken
18 Bayessche Netze Tala Chikh Ali Thomas Noll

Literatur

[CLRS = Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms, 4th edition. MIT Press and McGraw-Hill, 2013]

  1. Fan Chung: A Brief Survey of PageRank Algorithms. IEEE Transactions on Network Science and Engineering 1(1), 2014.
  2. CLRS, Section 16.3: Huffman Codes.
  3. Terry Welch: A Technique for High-Performance Data Compression. IEEE Computer, 1984, 8-19.
  4. CLRS, Section 31.7: RSA Crypto System.
  5. H. Schorr and W. M. Waite: An efficient machine-independent procedure for garbage collection in various list structures. Commun. ACM 10(8), 1967, 501-506.
  6. Victor M. Jimenez and Andres Marzal: Computing the K Shortest Paths: A New Algorithm and an Experimental Comparison. WAE, LNCS 1668, 1999, 15-29.
  7. CLRS, Chapter 17: Amortized Analysis.
  8. CLRS, Chapter 32: String Matching.
  9. CLRS, Chapter 29: Linear Programming.
  10. Stuart Russell and Peter Norvig: Artificial Intelligence: A Modern Approach. 3rd Edition, Prentice Hall, 2009. Section 3.5.2.: A* Search.
  11. Howard Barringer: Randomized algorithms – a brief introduction. Lecture notes.
  12. CLRS, Chapter 19: Fibonacci Heaps.
  13. Daniel D. Sleator, Robert Tarjan: Self-Adjusting Binary Search Trees. Journal of the ACM 32(3), 1985, 652–686.
  14. A. Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. Int. Conf. on Management of Data, 1984, 47-57.
  15. Matthias Kuntz and Kai Lampka: Probabilistic Methods in State Space Analysis. Validation of Stochastic Systems, LNCS 2925, 2004, 251-266.
  16. Randal E. Bryant: Graph-Based Algorithms for Boolean Function Manipulation. IEEE Trans. Computers, Vol. C-35, No. 8, 1986, 677-691.
  17. George T. Heineman, Gary Pollice, and Stanley Selkow: Algorithms in a Nutshell. Oreilly Media, 2008, Chapter 7: Path Finding in AI, 217-223.
  18. Eugene Charniak: Bayesian Networks without Tears, AI Magazine 12(4), 1991, 50-63.

Anmeldung

Die Anmeldung erfolgt über eine zentrale Fachgruppenseite. Nachträgliche Anmeldungen sind nicht möglich.

Weitere Informationen

Kontakt

Thomas Noll <noll at cs.rwth-aachen.de>