Algorithmen und Datenstrukturen

Proseminar, Wintersemester 2020/21

News

  • 10.06.2020: Wir sind online!

Einführung und Themenvergabe

Termine

30.10.2020Frist für Themenauswahl
23.11.2020Letzte Rücktrittsmöglichkeit
30.11.2020Vorlage der detaillierten Inhaltsübersicht
11.01.2021Vollständige Fassung der Ausarbeitung
01.02.2021Vollständige Fassung der Folien
10./11.02.2021 (?)Blockseminar

Beachten Sie bitte, dass die vollständigen Fassungen von Ausarbeitung und Vortragsfolien Ihre finale Einreichung darstellen und sich von der endgültigen Version nur durch kleinere Anpassungen unterscheiden sollen, die nach Rücksprache mit Betreuerin bzw. Betreuer erfolgen. Es ist aber möglich (und dringend empfohlen!), vor den jeweiligen Fristen Entwurfsversionen Ihrer Dokumente 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

Nr.ThemaReferent/inBetreuer/in
Algorithmen
1PageRank-AlgorithmusSelin Ata, Henrik Sören HüttenJip Spel
2Huffman-KodierungFelix MiddeldorfPhilipp Berger
3LZW-Datenkompression
4RSA-KryptosystemMohamed Alyousef, Alexander WiegelThomas Noll
5Längste gemeinsame TeilsequenzYoussef Kharita, Martin SchymiczekPhilipp Berger
6Deutsch-Schorr-Waite Baumtraversierung
7Problem der K kürzesten Pfade
8Amortisierte Laufzeitanalyse
9String Matching
10Lineare ProgrammierungMaximilian Hense, Ahmet Erkan TuranThomas Noll
11A*-SuchalgorithmusAnas Gaafar, Ping WanTim Quatmann
12 Randomisierte AlgorithmenStanislav Mironenko, Anastasiia PetrovaIra Fesefeldt
Datenstrukturen
13Splay-BäumeNikita Antiufeev, Adnan HaddadJoshua Moerman
14Fibonacci-Heaps
15AVL-BäumeDenis BerschauerJoshua Moerman
16B-Bäume
17Bitstate Hashing
18Binäre Entscheidungsdiagramme
19Spielbäume
20Bayessche 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. Gopal Pandurangan, Prabhakar Raghavan, and Eli Upfal: Using PageRank to characterize web structure. Internet Math. Volume 3, Number 1 (2006), 1-20.
  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. 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.
  7. Victor M. Jimenez and Andres Marzal: Computing the K Shortest Paths: A New Algorithm and an Experimental Comparison. WAE, LNCS 1668, 1999, 15-29.
  8. CLRS, Chapter 17: Amortized Analysis.
  9. CLRS, Chapter 32: String Matching.
  10. CLRS, Chapter 29: Linear Programming.
  11. Stuart Russell and Peter Norvig: Artificial Intelligence: A Modern Approach. 3rd Edition, Prentice Hall, 2009. Section 3.5.2.: A* Search.
  12. Howard Barringer: Randomized algorithms – a brief introduction. Lecture notes.
  13. D.D. Sleator and R.E. Tarjan: Self-Adjusting Binary Search Trees. Journal of the ACM 32:3, 652-686, 1985.
  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 Analysis. Validation 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>