Current Topics in Theoretical Computer Science (SS 2017)

Lecture

Prof. Dr. Ulrich Meyer

Tuesdays 12:00 - 14:00, H 13 (Jügelhaus/Hörsaalgebäude)
Wednesdays 12:00 - 14:00, H 9 (Jügelhaus/Hörsaalgebäude)

QIS: ATTI1, ATTI2, MATThIA

Tutorials

Manuel Penschuck

Wednesdays 14:00 - 16:00
H 9 (Jügelhaus/Hörsaalgebäude)

The lecture is held in English. You can solve the assignments in German or in English.

Content

Streaming algorithms and their connection to other models of computation (external-memory, parallelism, power-aware computing). Lower bounds. References

M. Garofalakis, J. Gehrke, and R. Rastogi (eds) “Data Stream Management: Processing High-Speed Data Streams”, Springer, 2016. Available in CS library.

Exams

Oral exams towards the end of the semester.

Materials

Lecture notes and extra material

Lecture notes by Amit Chakrabarti at Dartmouth College from 2015. We will follow them rather closely for the first weeks of the lecture.
M. Garofalakis, J. Gehrke, and R. Rastogi (eds) “Data Stream Management: Processing High-Speed Data Streams”, Springer, 2016. Available in CS library. Chapter 8 on Sliding-window results is also available here and this version contains some more details.
Ch. Scheideler “Probabilistic Methods for Coordination Problems”, HNI Verlagsschriftenreihe, 2000. Online PDF. Chapter 3 provides a nice little introduction to probability theory which will be handy for the course. Further notes on basic probability theory by Annamaria Kovacs can be found here.
Some basics about hash functions by our former colleague Nicole Schweikardt. Please be aware of slightly different notation.
On Wed, May 24th we dealt with sparse recovery based on Chap 3 in this notes from a lecture by Moses Charikar. That paper also contains graph algorithms.
We worked through the space lower-bounds for graph algorithms in these further notes from a lecture by Moses Charikar.
For the external-memomy setting you can have a look at this book to be found in the CS library.
Lecture Notes Effiziente Algorithmen 2015 (German).

Menu