Algorithms and Data Structures (Proseminar)

Proseminar, Wintersemester 2018/19

News

  • 09.07.2018: Wir sind online!

Termine

10.10.2018, 14:00 Einführungsveranstaltung Seminarraum 5053.a (Informatikzentrum, Foyer E2, Erdgeschoss gegenüber AH 5)
06.11.2018 12:00
07.11.2018 13:00
08.11.2018 11:00
09.11.2018 12:00
Einführung in die Literaturrecherche (Bibliothek)
02.11.2018 Letzte Rücktrittsmöglichkeit
12.11.2018 Vorlage der detaillierten Inhaltsübersicht
10.12.2018 Vollständige Fassung der Ausarbeitung
14.01.2018 Vollständige Fassung der Folien
31.01./01.02.2019 Blockseminar Seminarraum Inf. 2 (Raum 4201b)

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. Thema Referent/in Betreuer/in
Algorithmen
1 PageRank-Algorithmus Matthias Appenzeller, Nick Kocher Christian Hensel
2 Huffman-Kodierung Labrik Gashi, Qingyun He Jip Spel
3 LZW-Datenkompression Lukas Alt, Felix Meyer Benjamin Kaminski
4 RSA-Kryptosystem Bernd Schoolmann, Niklas Schulte Philipp Berger
5 Längste gemeinsame Teilsequenz Georg Manthey, Patrick Konrad Piel Benjamin Kaminski
6 Deutsch-Schorr-Waite Baumtraversierung
7 Problem der K kürzesten Pfade
8 Amortisierte Laufzeitanalyse
9 String Matching Philipp Dolif, Moritz Gose Thomas Noll
10 Lineare Optimierung Silviu-Eric Criste, Friedrich Kriegsheim Christian Hensel
11 A*-Suchalgorithmus Christina Gehnen, Philipp Hugenroth Philipp Berger
Datenstrukturen
12 Splay-Bäume
13 Fibonacci-Heaps
14 AVL-Bäume Sebastian Kräll Thomas Noll
15 B-Bäume
16 Bitstate Hashing
17 Binäre Entscheidungsdiagramme
18 Spielbäume Tom Torsten Bursch, Constantin Mensendiek Sebastian Junges
19 Rot-Schwarz-Bäume
20 Bayessche Netze Niklas Jansen, Achim Spies Sebastian Junges

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 31.7: RSA Crypto System.
  3. Terry Welch: A Technique for High-Performance Data Compression. IEEE Computer, 1984, 8-19.
  4. CLRS, Section 16.3: Huffman Codes.
  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. D.D. Sleator and R.E. Tarjan: Self-Adjusting Binary Search Trees. Journal of the ACM 32:3, 652-686, 1985.
  13. CLRS, Chapter 19: Fibonacci Heaps.
  14. Donald Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching.  Second Edition. Addison-Wesley, 1998, Section 6.2.3: Balanced Trees.
  15. CLRS, Chapter 18: B-Trees.
  16. Matthias Kuntz and Kai Lampka: Probabilistic Methods in State Space Analysis. Validation of Stochastic Systems, LNCS 2925, 2004, 251-266.
  17. Randal E. Bryant: Graph-Based Algorithms for Boolean Function Manipulation.  IEEE Trans. Computers, Vol. C-35, No. 8,  1986, 677-691.
  18. George T. Heineman, Gary Pollice, and Stanley Selkow: Algorithms in a Nutshell. Oreilly Media, 2008, Chapter 7: Path Finding in AI, 217-223.
  19. CLRS, Chapter 13: Red-Black Trees.
  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>