Algorithms and Data Structures (Proseminar)

Proseminar, Wintersemester 2015/16

News

  • 24.06.2015: Wir sind online!

Termine

23.10.2015, 14:00 Einführungsveranstaltung Seminarraum Inf. 2 (Raum 4201b)
09.11., 14:00
11.11., 16:00
13.11., 14:00		 Einführung in die Literaturrecherche (Bibliothek)
16.11.2015 Letzte Rücktrittsmöglichkeit
23.11.2015 Vorlage der Inhaltsübersicht
21.12.2015 Endgültige Fassung der Ausarbeitung
01.02.2016 Endgültige Fassung der Folien
15./16.02.2016 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 – Christian Dehnert
2 Huffman-Kodierung – Tim Lange
3 LZW-Datenkompression Marko van Treeck Harold Bruintjes
4 RSA-Kryptosystem – Benjamin Kaminski
5 Längste gemeinsame Teilsequenz Jonas Hein Benjamin Kaminski
6 Deutsch-Schorr-Waite Baumtraversierung – Christoph Matheja
7 Problem der K kürzesten Pfade Jens Butting Tim Lange
8 Amortisierte Laufzeitanalyse Manoel Römmer Christoph Matheja
9 Smoothed Analysis –
10 Externes Sortieren – Souymodip Chakraborty
11 String Matching – Federico Olmedo
12 Lineare Optimierung Abdallah Atouani Tim Lange
13 A*-Suchalgorithmus Tom Biskup Sebastian Junges
Datenstrukturen
14 Splay-Bäume Simon Veittes Christina Jansen
15 Fibonacci-Heaps Stoil Iliev Christina Jansen
16 AVL-Bäume – Hao Wu
17 B-Bäume Feiko Nanninga Hao Wu
18 Bitstate Hashing – Christian Dehnert
19 Binäre Entscheidungsdiagramme Richarda Leehr Thomas Noll
20 Spielbäume Eric Wagner Harold Bruintjes
21 Rot-Schwarz-Bäume Tobias Räwer Thomas Noll
22 Bayessche Netze Hannah Mauermann Sebastian Junges

Vortragstermine

Montag, 15.02.2016
09:00-10:30 7, 8, 12
10:45-11:45 13, 22
12:00-13:00 14, 15
Dienstag, 16.02.2016
09:00-10:30 3, 5, 20
10:45-12:15 17, 19, 21

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. Spielman, Daniel; Teng, Shang-Hua (2001): Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. ACM Symposium on Theory of Computing, 2001, 296-305.
  10. Donald Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching.  Second Edition. Addison-Wesley, 1998, Section 5.4: External Sorting.
  11. CLRS, Chapter 32: String Matching.
  12. CLRS, Chapter 29: Linear Programming.
  13. Stuart Russell and Peter Norvig: Artificial Intelligence: A Modern Approach. 3rd Edition, Prentice Hall, 2009. Section 3.5.2.: A* Search.
  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 Analysis. Validation 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. CLRS, Chapter 13: Red-Black Trees.
  22. Eugene Charniak: Bayesian Networks without Tears, AI Magazine 12(4), 1991, 50-63.

Anmeldung

Die Anmeldung erfolgt zwischen dem 25. Juni und dem 8. Juli 2015 über die zentrale Fachgruppenseite. Nachträgliche Anmeldungen sind nicht möglich.

Weitere Informationen

Kontakt

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