Algorithms and Data Structures

Proseminar in Informatik (Blockseminar, in Aachen)

20.09.2011

Die Einführungsveranstaltung wird auf den 21.10.2011 verschoben.

Einführungsveranstaltung	Fr	21.10.2011	16 Uhr	Seminarraum Info 2
Einführung in die Literaturrecherche	Di	08.11.2011	11:00	Informatik-Bibliothek
	Mi	09.11.2011	11:30,	Informatik-Bibliothek
Letzte Rücktrittsmöglichkeit	Fr	11.11.2011
Vorlage der Gliederung	Fr	18.11.2011
Erste Fassung der Ausarbeitung	Do	01.12.2011
Endgültige Fassung der Ausarbeitung	Mo	19.12.2011
Endgültige Fassung der Folien	Di	24.01.2012
Blockseminar	Do	09.02.2012	9 Uhr	Seminarraum Info 2
	Fr	10.02.2012	9 Uhr	Seminarraum Info 1

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:

Nr.	Thema	Referent(in)	Betreuer(in)	Skript	Folien
1	Pagerank-Algorithmus	Benedikt Wolters	Yue	hier	hier
2	Huffman-Kodierung	Kirsten Hucko	Dehnert	-	-
3	Cocktail Sort	Kiril Mitev	Yue	-	hier
4	Longest Common Subsequence	Paul Dingil	Noll	hier	hier
5	Deutsch-Schorr-Waite Baumtraversierung	-	-	-	-
6	Problem der K kürzesten Pfade	Laura Slade	Dehnert	-	-
7	Amortisierte Laufzeitanalyse	-	-	-	-
8	Smoothed Analysis	-	-	-	-
9	Externes Sortieren	-	-	-	-
10	String Matching	-	-	-	-
11	Lineare Optimierung	-	-	-	-
Datenstrukturen
12	Splay Trees	Marvin Dönni	Noll	hier	hier
13	Fibonacci Heaps	Daniel Kempkens	Heinen	-	-
14	AVL-Bäume	-	-	-	-
15	B-Bäume	-	-	-	-
16	Bitstate Hashing	-	-	-	-
17	Binäre Entscheidungsdiagramme	Gordon Lawrenz	Heinen	hier	hier
18	RAID: Redundant Array of Independent [Inexpensive] Disks	Stefan Wexel	Noll	hier	hier
19	Spielbäume	Frederik Zwilling	Yue	-	hier
20	Rot-Schwarz-Bäume	Emmanuel Biver	Heinen	hier	hier

Nr.

Thema

Referent(in)

Betreuer(in)

Skript

Folien

Algorithmen

Benedikt Wolters

Kirsten Hucko

Kiril Mitev

Longest Common Subsequence

Paul Dingil

Noll

hier

Deutsch-Schorr-Waite Baumtraversierung

Problem der K kürzesten Pfade

Laura Slade

Dehnert

Amortisierte Laufzeitanalyse

Datenstrukturen

Marvin Dönni

Daniel Kempkens

Binäre Entscheidungsdiagramme

Gordon Lawrenz

Heinen

hier

RAID: Redundant Array of Independent [Inexpensive] Disks

Stefan Wexel

Frederik Zwilling

Emmanuel Biver

Folien der Einführungsveranstaltung

[CLRS = Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001.]

Gopal Pandurangan, Prabhakar Raghavan, and Eli Upfal: Using PageRank to characterize web structure. Internet Math. Volume 3, Number 1 (2006), 1-20.
D.A. Huffman: A method for the construction of minimum-redundancy codes. In: Proceedings of the I.R.E.. September 1952, S. 1098-1101.
D.E. Knuth: The Art of Computer Programming, Vol. 3: Sorting and Searching. 2nd edition, Addison-Wesley, 1998. Section 5.2.2: Sorting by Exchanging.
CLRS, S. 350–355
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
Víctor M. Jiménez and Andrés Marzal: Computing the K Shortest Paths: A New Algorithm and an Experimental Comparison. Proc. of WAE, Lecture Notes in Computer Science, 1999, Volume 1668/1999, 15-29
CLRS, Chapter 17: Amortized Analysis, S. 405-430
D. Spielman, S.H. Teng: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM, 2001, S. 296-305
Donald Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching. Second Edition. Addison-Wesley, 1998, Section 5.4: External Sorting, S. 248--379
CLRS, Chapter 32: String Matching, S. 906-932
CLRS, Chapter 29: Linear Programming, S. 843-897
D.D. Sleator, R.E. Tarjan: Self-Adjusting Binary Search Trees.
Journal of the ACM 32:3, S. 652-686, 1985
CLRS, Chapter 19: Fibonacci Heaps, S 505-530
Donald Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. Pages 458-475 of section 6.2.3: Balanced Trees
CLRS, Chapter 18: B-Trees, S. 484-504
Matthias Kuntz and Kai Lampka: Probabilistic Methods in State Space Analysis. Validation of Stochastic Systems, Lecture Notes in Computer Science, Volume 2925, 2004, S. 251-266
Randal E. Bryant: Graph-Based Algorithms for Boolean Function Manipulation. IEEE Trans. Computers, Vol. C-35, No. 8 (August, 1986), S. 677-691
D. A. Patterson, G. Gibson, R. H. Katz: A case for redundant arrays of inexpensive disks (RAID). Proceedings of the 1988 ACM SIGMOD international conference on Management of Data, S. 109-116
S. Russell, P. Norvig: Artificial Intelligence - A modern Approach. Chapter 5: Adversarial Search, Pearson, 2010, S. 161-200

Hinweise zur Anfertigung der Ausarbeitung finden Sie hier. Weitere Informationen dazu sowie zum Vortrag gibt es bei der Einführungsveranstaltung.

Die Anmeldung erfolgt zwischen dem 20.06. und dem 03.07.2011 über die zentrale Fachgruppenseite.

Thomas Noll (noll at cs.rwth-aachen.de)

BSc/MSc/Diploma Topics
Teaching WS 2012/13
Hybrid Systems Group

We are looking for a HiWi for the Compiler Construction course. If you are interested, please contact Thomas Noll.

Joost-Pieter Katoen has been appointed as a member of the renowned Academia Europaea (Academy of Europe), a European, non-governmental association acting as an Academy whose members are scientists and scholars who collectively aim to promote learning, education and research.

Vacancies for postdoctoral researchers in "Automated Analysis of Probabilistic Programs". Application deadline: August 15, 2013.

Joost-Pieter Katoen has been awarded a Distinguished Professorship from the RWTH Aachen University.

The Hybrid Systems: Computation and Control (HSCC'13) conference in Philadelphia has been very successful: Hongfei Fu received the best student paper award for his paper "Approximating acceptance probabilities of CTMC-paths on multi-clock deterministic timed automata". Besides, the paper by Ilya Tkachev, Alexandru Mereacre, Alessandro Abate and Joost-Pieter Katoen was ranked second in the overall best paper award selection.

Joost-Pieter Katoen has been elected as Steering Committee Chair of ETAPS (www.etaps.org), the largest conference on theory and practice of software in Europe. He is the first non-UK ETAPS SC chair since the conference was initiated in 1998. More information here.

The Alumni-Magazine of RWTH Aachen University contains an interview with our former PhD student and postdoctoral researcher, Dr. Tingting Han.

HiWi's wanted to work in a new European Space Agency project for enhancing state-of-the-art design and analysis tools (COMPASS) for the next generation European rockets. Need programming and model checking affinity. See here for details and contact.

We offer openings for several PhD candidates in the area of
"Model-Based Design and Analysis for Dependable Software Systems". Deadline for application: September 14, 2012. For further information click here.

The Theory of Hybrid Systems Group offers two jobs as student assistants within the CEBug project. For more information, look here.

Dino Distefano received the prestigious Roger Needham Award for his work on software verification. This award is for a distinguished research contribution in computer science by a UK based researcher who has completed up to 10 years of post-doctoral research. Dr. Distefano was the first PhD student supervised by Joost-Pieter Katoen.

Marijn Jongerden received the German MMB (Messung, Modellierung und Bewertung von Rechensystemen) Award 2012 of the GI/ITG-Committee for Measurement, Modelling and Evaluation of Computing Systems for his PhD-thesis on "Model-based energy analysis of battery powered systems". His work was supervised by Boudewijn Haverkort (Twente) and Joost-Pieter Katoen.

Our paper "Formal Correctness, Safety, Dependability and Performance Analysis of a Satellite" has been accepted to ICSE 2012 in the track SE in Practice (18% acceptance rate). The paper treats a new satellite from the European Space Agency that was modeled and analyzed with modern tools during the actual satellite design.

Joost-Pieter Katoen will act as DJ in the "Nacht der Professoren" in the Apollo bar and cinema.