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

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

Übungen (M-ATThIA, ATTI1)

Übungen (M-ATThIA, ATTI2)