News
Today's TutorialWritten on 30.11.23 by Alejandro Cassis Dear all, As per your requests, starting from today we will start the tutorials at 16:15. |
Exercise Sheet 4Written on 29.11.23 by Alejandro Cassis Hi everyone, Exercise sheet 04 has been released. |
Exercise 3Written on 15.11.23 by Nithin Varma Dear all, Exercise sheet 3 has been released. Apologies for the delay. |
Mistake in Exercise 2.2Written on 03.11.23 by Alejandro Cassis Dear all, We realized we had a mistake in exercise 2.2 of Sheet 02. The intended running time is O(m + n log(n)). The correct pdf is updated in the CMS. Sorry for the inconvenience. |
Tutorial InformationWritten on 02.11.23 by Alejandro Cassis Dear all, Today's tutorial is at 10:15 in room 024 E1 4. As agreed in the last lecture, starting from the next tutorial (on 16.11) we will change the time to 16:00, in the same room. |
Primer to RandomnessWritten on 14.10.23 by Karl Bringmann The course will make extensive use of randomization. Therefore, we have collected background on probability theory and how to use it in algorithm design in a "Primer to Randomness", which can be found under Information->Materials->Further Reading. We suggest that you read at least the first half of… Read more The course will make extensive use of randomization. Therefore, we have collected background on probability theory and how to use it in algorithm design in a "Primer to Randomness", which can be found under Information->Materials->Further Reading. We suggest that you read at least the first half of this document before the first lecture, Section 3 before the second lecture, and the whole document at the latest before the third lecture. |
Sublinear Algorithms
For a long time, computer scientists considered linear-time algorithms to be the ideal and ultimate goal of any research direction. However, as data sets become larger, it is reasonable and useful to ask if one can solve computational tasks using a sublinear amount of resources, such as running time or space. Surprisingly, even with sublinear resources one can design non-trivial and meaningful algorithms. In this course, we will learn how to design and analyze sublinear algorithms. Regarding space we will focus on streaming algorithms, and regarding time we will focus on property testing. We will also consider applications of sublinear algorithms in classic algorithm design, that is, how sublinear algorithms are used as subroutines in classic efficient algorithms.
Time, Date, and Format
This course consists of one lecture per week (Tuesday 16:00-18:00) and a tutorial every other week (Thursday 10:15-12:00). See Information->Timetable for details.
The first lecture is on October 24. The first tutorials is held on October 26. Lectures and tutorials are held physically in room 024 building E1 4.
Prerequisites
We assume mathematical maturity and comfort with basic probability theory. We also assume basic knowledge in algorithms. Therefore, required prerequisite is a basic lecture in algorithms such as "Introduction to Algorithms and Data Structures". The core lecture "Algorithms and Data Structures" would be helpful, but is not a formal requirement.
Registration
You need to register on this webpage to get access to exercise sheets and other course material.
Exercises
An important part of the course are the exercises, where you will analyze and design sublinear algorithms on your own. Solutions to the exercise sheets are due at the beginning of the lecture, and can be submitted either on paper in the lecture on virtually on this website. There will be 7 exercise sheets. You are allowed to collaborate on the exercise sheets, but you have to write down a solution on your own, using your own words. Please indicate the names of your collaborators for each exercise you solve. Further, cite all external sources that you use (books, websites, research papers, etc.). If you use any AI tools such as ChatGPT, explicitly mention this use as part of your solution and describe in 1-3 lines how you used it.
Exam
To be admitted to the exam, you need to score at least 50% of the points on the exercise sheets. Your grade will be determined by a written or oral exam.
Tentative Schedule
This is a tentative list of topics.
| Date | Lecturer | Topic | Comment |
|---|---|---|---|
| 24.10. 4pm | KB | Introduction (overview, probability background) + Streaming I: Morris counter | |
| 26.10. 10am | AC | Tutorial 0 (more probability background, presence exercises) | |
| 31.10. 4pm | KB | Streaming II: distinct elements + Applications I: reachability counting | |
| 2.11. 10am | AC | Tutorial 1 | |
| 7.11. 4pm | KB | Streaming III: moment estimation (AMS sketch), heavy hitters (CountMin sketch) | |
| 14.11. 4pm | NV | Streaming IV: L0 sampling, graph streams, linear sketching for connected components | |
| 16.11. 10am | HA | Tutorial 2 | |
| 21.11. 4pm | NV | Property Testing I: sortedness of lists, monotonicity of functions | |
| 28.11. 4pm | KB | Streaming V: sparse recovery | |
| 30.11. 10am | AC | Tutorial 3 | |
| 5.12. 4pm | NV | Property Testing II: linearity of Boolean functions | |
| 12.12. 4pm | NV | Property Testing III: graph properties: connectedness of sparse graphs, bipartiteness of dense graphs | |
| 14.12. 10am | AC | Tutorial 4 | |
| 19.12. 4pm | KB | Applications II: sparse matrix multiplication and sparse convolution | |
| 2.1. 4pm | NV | Sampling: generating a uniformly random edge in streaming and query models | |
| 9.1. 4pm | KB | Property Testing IV: estimating the edit distance between strings | |
| 11.1. 10am | HA | Tutorial 5 | |
| 16.1. 4pm | NV | Property Testing V: estimating the weight of Euclidean Minimum Spanning Tree | |
| 23.1. 4pm | NV | Lower Bounds I: Yao’s principle and applications | |
| 25.1. 10am | HA | Tutorial 6 | |
| 30.1. 4pm | NV | Lower Bounds II: Communication complexity and applications | |
| 6.2. 4pm | Outlook | ||
| 8.2. 10am | HA | Tutorial 7 |
Literature
The course will not follow a particular book. Some references can be found under Information->Material.