Proseminar Datenstrukturen und Algorithmen

Sommersemester 2024

News

  • 04.12.2023: Wir sind online!

Einführung und Themenvergabe

Termine

Mo, 15.04.2024, 14:30Einführungsveranstaltung (Raum 9U10)
Fr, 19.04.2024Frist für Themenauswahl
Fr, 10.05.2024Letzte Rücktrittsmöglichkeit
Mo, 13.05.2024Vorlage der detaillierten Vortragsstruktur
Mo 10.06.2024Vollständige Fassung der Folien
Mo/Di 08./09.07.2024Blockseminar (Raum 9U10)
Mo 22.07.2024Einreichung 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.

Inhalt

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

Zeitplan der Vorträge

UhrzeitMontag, 8. Juli (Raum 9U10)UhrzeitDienstag, 9. Juli (Raum 9U10)
09:00-10:00Julian Yassin Sehbaoui, Paul Hermes, Philipp Niklas Döbler13:00-14:00Aleksandr Stadnitskii, Jakob Kunz, Shohrukhbek Yakhyoev
10:15-11:15Quentin Brandherm, Yunus Gürbüz, Harun Düzel14:15-15:15Thorge Rieks, Aleksandr
Kachalov, Sami Zouhri
11:30-12:50Leon Paschke, Maxim Klöcker, Paul Blumberg, Jakob
Senger
15:30-16:30Phu Hoang, Monika Krasteva, Erik Nisamutdinoff
16:45-17:45Deha Ortasarı, Carlotta Lucia Schwanenberg, Sercan Sahin

Themen

Alle Themen sollen jeweils in Zweiergruppen bearbeitet werden.

Nr.ThemaReferent/inBetreuer/in
Algorithmen
1PageRank-Algorithmus
2Huffman-KodierungCarlotta Lucia SchwanenbergAlexander Bork
3LZW-DatenkompressionJulian Yassin Sehbaoui, Aleksandr StadnitskiiIra Fesefeldt
4RSA-KryptosystemPaul Blumberg, Erik NisamutdinoffLutz Klinkenberg
5Längste gemeinsame Teilsequenz
6Kürzeste gemeinsame Obersequenz
7Deutsch-Schorr-Waite Baumtraversierung
8Problem der K kürzesten Pfade
9Amortisierte LaufzeitanalyseYunus Gürbüz, Aleksandr
Kachalov
Lena Verscht
10String Matching
11Lineare ProgrammierungPhu Hoang, Leon PaschkeEmma Ahrens
12A*-SuchalgorithmusSercan Sahin, Jakob
Senger
Alexander Bork
13 Randomisierte AlgorithmenMaxim Klöcker, Monika KrastevaEmma Ahrens
Datenstrukturen
14Fibonacci-HeapsPaul Hermes, Jakob KunzIra Fesefeldt
15AVL-BäumeHarun Düzel, Sami ZouhriLena Verscht
16B-BäumePhilipp Niklas Döbler, Shohrukhbek YakhyoevIra Fesefeldt
17Bitstate Hashing
18Binäre Entscheidungsdiagramme
19SpielbäumeQuentin Brandherm, Thorge RieksIra Fesefeldt
20Bayessche NetzeDeha OrtasarıLutz Klinkenberg

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. CLRS, Section 15.4: Longest Common Subsequence.
  6. Jonathan S. Turner: Approximation algorithms for the shortest common superstring problem. Information and Computation 83 (1), 1989, 1-20.
  7. 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.
  8. Victor M. Jimenez and Andres Marzal: Computing the K Shortest Paths: A New Algorithm and an Experimental Comparison. WAE, LNCS 1668, 1999, 15-29.
  9. CLRS, Chapter 17: Amortized Analysis.
  10. CLRS, Chapter 32: String Matching.
  11. CLRS, Chapter 29: Linear Programming.
  12. Stuart Russell and Peter Norvig: Artificial Intelligence: A Modern Approach. 3rd Edition, Prentice Hall, 2009. Section 3.5.2.: A* Search.
  13. Howard Barringer: Randomized algorithms – a brief introduction. Lecture notes.
  14. CLRS, Chapter 19: Fibonacci Heaps.
  15. Donald Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching.  Second Edition. Addison-Wesley, 1998, Section 6.2.3: Balanced Trees.
  16. CLRS, Chapter 18: B-Trees.
  17. Matthias Kuntz and Kai Lampka: Probabilistic Methods in State Space AnalysisValidation of Stochastic Systems, LNCS 2925, 2004, 251-266.
  18. Randal E. Bryant: Graph-Based Algorithms for Boolean Function Manipulation.  IEEE Trans. Computers, Vol. C-35, No. 8,  1986, 677-691.
  19. George T. Heineman, Gary Pollice, and Stanley Selkow: Algorithms in a Nutshell. Oreilly Media, 2008, Chapter 7: Path Finding in AI, 217-223.
  20. 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>