Proseminar Datenstrukturen und Algorithmen

Algorithmen und Datenstrukturen

Proseminar, Sommersemester 2024

News

  • 04.12.2023: Wir sind online!

Einführung und Themenvergabe

Termine

TBAEinführungsveranstaltung
TBAFrist für Themenauswahl
TBALetzte Rücktrittsmöglichkeit
TBAVorlage der detaillierten Inhaltsübersicht
TBAVollständige Fassung der Ausarbeitung
TBAVollständige Fassung der Folien
TBABlockseminar

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.

Themen

Alle Themen sollen jeweils in Zweiergruppen bearbeitet werden.

Nr.ThemaReferent/inBetreuer/in
Algorithmen
1PageRank-Algorithmus
2Huffman-Kodierung
3LZW-Datenkompression
4RSA-Kryptosystem
5Längste gemeinsame Teilsequenz
6Kürzeste gemeinsame Obersequenz
7Deutsch-Schorr-Waite Baumtraversierung
8Problem der K kürzesten Pfade
9Amortisierte Laufzeitanalyse
10String Matching
11Lineare Programmierung
12A*-Suchalgorithmus
13 Randomisierte Algorithmen
Datenstrukturen
14Splay-Bäume
15Fibonacci-Heaps
16AVL-Bäume
17B-Bäume
18Bitstate Hashing
19Binäre Entscheidungsdiagramme
20Spielbäume
21Bayessche Netze

Literatur

[CLRS = Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms, Third Edition. MIT Press and McGraw-Hill, 2009]
  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. D.D. Sleator and R.E. Tarjan: Self-Adjusting Binary Search Trees. Journal of the ACM 32:3, 652-686, 1985.
  15. CLRS, Chapter 19: Fibonacci Heaps.
  16. Donald Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching.  Second Edition. Addison-Wesley, 1998, Section 6.2.3: Balanced Trees.
  17. CLRS, Chapter 18: B-Trees.
  18. Matthias Kuntz and Kai Lampka: Probabilistic Methods in State Space AnalysisValidation of Stochastic Systems, LNCS 2925, 2004, 251-266.
  19. Randal E. Bryant: Graph-Based Algorithms for Boolean Function Manipulation.  IEEE Trans. Computers, Vol. C-35, No. 8,  1986, 677-691.
  20. George T. Heineman, Gary Pollice, and Stanley Selkow: Algorithms in a Nutshell. Oreilly Media, 2008, Chapter 7: Path Finding in AI, 217-223.
  21. 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>