Current Topics in Algorithms for Big Data (SS 2022)

Lecture

Prof. Dr. Ulrich Meyer

Wednesday 14:00 - 16:00 in SR 11

Thursday 10:00 - 12:00 in SR 11

Office hours: By appointment

Tutorials

Hung Tran

Default is Wednesday 16:00 - 18:00 in SR 11, but upon mutual agreement we can try to find another slot.

Office hours: By appointment

Organisation of tutorials

We will issue problem sheets weekly on Thursday; you have one week to complete the assignments and hand them in before Thursday’s lecture electronically. Details will follow. The solutions will then be discussed in the following tutorial. The rules on bonification depend on the type of exam which will be announced in the near future. Working in groups is recommended however if assignments are found to have been plagiarized we remove all points from the assignment on the first occurrence and the whole bonification on the second occurrence.

Language

The lecture is held in English. By mutual agreement, the language of instruction can be changed to German, too.

You can solve the assignments in German or in English.

Content

In the first part we will consider classic and new algorithms for memory hierarchies

• For the external-memomy setting you can have a look at this book to be found in the CS library.

In the second part we will deal with streaming algorithms and their connection to other models of computation (external-memory, parallelism, power-aware computing). Lower bounds. Initial references:

• Lecture notes by Amit Chakrabarti at Dartmouth College from 2020. We will follow them rather closely for the first weeks of the second part.

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

Exam

The exam type is to be determined.

Materials

• Vorlesungsmitschrift Effiziente Algorithmen 2015
• Folien zu Energie-effizientem Sortieren
• 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.

Lecture notes and extra material

• Tafelbild 13.04.
• Tafelbild 14.04.
• Tafelbild 20.04.
• Tafelbild 21.04.
• Tafelbild 27.04.
• Tafelbild 28.04.
• Tafelbild 04.05.
• Tafelbild 05.05.
• Tafelbild 11.05.
• Tafelbild 12.05.
• Tafelbild 18.05.
• Tafelbild 19.05.
• Tafelbild 25.05.
• Tafelbild 01.06.
• Tafelbild 02.06.
• Tafelbild 15.06.
• Tafelbild 22.06.
• Tafelbild 23.06.
• Tafelbild 30.06.
• Tafelbild 06.07.
• Tafelbild 07.07.
• Tafelbild 13.07.
• Tafelbild 14.07.

Self Tests

• Selbsttest 20.04. mit Kommentaren
• Selbsttest 21.04. mit Kommentaren
• Selbsttest 04.05. mit Kommentaren
• Selbsttest 11.05. mit Kommentaren
• Selbsttest 25.05. mit Kommentaren

Assignments