News
Exercise Sheet 7 is out nowWritten on 24.01.24 by Karl Bringmann As usual you can find it on the Material page of this website. Sorry for the delay. |
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 exam. Your final grade will be the better of your grade in the final exam and your grade in the re-exam. For passing the course it suffices to pass one of the exams, so it is not necessary to participate in both exams (but can be beneficial to improve your grade). For the exams you are allowed to bring a single one-sided handwritten DinA4-sheet; photocopies and printouts are not allowed.
Final exam: February 13, 2pm-4pm, HS001 in E1 3, please arrive 10min before 2pm
Re-exam: March 27, 2pm-4pm, HS001 in E1 3, please arrive 10min before 2pm
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, number of connected components | |
14.12. 4pm | AC | Tutorial 4 | |
19.12. 4pm | KB | Applications II: sparse matrix multiplication and sparse convolution | |
2.1. 4pm | canceled | ||
9.1. 4pm | NV | Property Testing IV: distribution testing | |
16.1. 4pm | KB | Lower Bounds I: encoding arguments | |
18.1. 4pm | HA | Tutorial 5 | |
23.1. 4pm | KB | Lower Bounds II: communication complexity | |
25.1. 4pm | HA | Tutorial 6 | |
30.1. 4pm | NV | Property Testing V: Lower Bounds using Yao's principle | |
6.2. 4pm | NV | Outlook + Sampling: generating a uniformly random edge in streaming and query models | |
8.2. 4pm | HA | Tutorial 7 |
Literature
The course will not follow a particular book. Some references can be found under Information->Material.