Seminar (Theoretical Computer Science) WS2018/19

Crazy Ideas in Datastructures and Algorithms

Persons and Contact:

Peter Rossmanith
Phillip Kuinke
Jan Dreier
tcs-teaching@cs.rwth-aachen.de

Material

Schedule

We meet Thursdays in 14:30 in room 5052 at the dates specified below. The meeting on 06.12.18 will take place in the seminar room of i7, room 4116.

Date Topic Student Material
08.11.18 ELIZA Julia Reim
15.11.18 Fast Inverse Squareroot Leander Schulten
15.11.18 Hacker's Delight Lucas Forster
29.11.18 Persistent Datastructures Erhard Eibl
29.11.18 Persistent Datastructures René Schäfer
06.12.18 Bloom Filter Radina Antonova
13.12.18 Probabilistically Checkable Proofs Lukas Glänzer
20.12.18 Computer Aided Proofs David Klüner
10.01.19 Blockchain Eric Remigius
10.01.19 Blockchain Erik Probst
17.01.19 Property Testing Tim Schirrmacher
17.01.19 Enclosing Circle Anton Stanchev
24.01.19 L(2,1) Labeling Raimund Hensen
31.01.19 Certifying Algorithms Azur Ponjavic

Content

This is a seminar about special algorithms and data structures. Many were created to meet special requirements. Some seem strange but are still useful. Possible topics include - persistent data structures (save a complete history of their state) - parallel data structures - robust algorithms (Partially solve two NP complete problems. For example they find a correct 3-coloring of a graph or prove that a graph is not member of a certain graph class, even tough 3-coloring and membership test of the graph class are NP complete.)

Prerequisites

Participants should be familiar with the basic concepts of datastructures and algorithms.