Current Topics in Theoretical Computer Science (SS 2018)

Lecture

Prof. Dr. Ulrich Meyer

Tuesdays 12:00 - 14:00, Magnus (RMS 11-15)
Wednesdays 12:00 - 14:00, SR-11 (RMS 11-15)

Tutorials

Hung Tran

Wednesdays 14:00 - 16:00
307 (RMS 11-15)

The lecture is held in English. However if all participants agree, the lecture can alternatively be held in German. 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.
• U. Meyer, P. Sanders, and J. Sibeyn (eds) “Algorithms for Memory Hierarchies”, Springer, 2003. Available in CS library.

Exams

Oral exams towards the end of the semester.

Materials

Vorlesungsunterlagen und zusätzliches Material

• Vorlesungsmitschrift Effiziente Algorithmen 2015
• Lecture notes by Amit Chakrabarti at Dartmouth College from 2015. Beginnend ab der ersten Woche von ATTI2 für die ersten Wochen.
• 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.

Vorlesungsstoff

• EA-Script from year 2015: Chapters 1-6 (up to page 64).
• Lecture notes by Amit Chakrabarti (2015): Chapters 1-6 (up to page 28).
• Chapter 4 of Lecture 11 by Moses Charikar.
• Chapters 1+2 of Lecture 12 by Moses Charikar.
• Pages 149-156 of THE SLIDING-WINDOW COMPUTATION MODEL AND RESULTS by Mayur Datar and Rajeev Motwani.

Klickerfolien

• Klicker 1
• Klicker 2
• Klicker 3
• Klicker 4
• Klicker 5
• Klicker 6

Übungen (M-ATThIA, ATTI1)

• Übung 1 Abgabe: 25.04.18
• Übung 2 Abgabe: 02.05.18
• Übung 3 Abgabe: 09.05.18
• Übung 4 Abgabe: 16.05.18
• Übung 5 Abgabe: 23.05.18
• Übung 6 Abgabe: 30.05.18

Übungen (M-ATThIA, ATTI2)

• Übung 7 Abgabe: 06.06.18
• Übung 8 Abgabe: 13.06.18
• Übung 9 Abgabe: 20.06.18
• Übung 10 Abgabe: 27.06.18
• Übung 11 Abgabe: 04.07.18
• Übung 12 Abgabe: 11.07.18