Current Topics in Theoretical Computer Science (SS 2018)


Prof. Dr. Ulrich Meyer

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


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.


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


  • 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.


Oral exams towards the end of the semester.


Vorlesungsunterlagen und zusätzliches Material


  • 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.


Übungen (M-ATThIA, ATTI1)

Übungen (M-ATThIA, ATTI2)