max planck institut
informatik
informatik
| Lecture time: | Wednesday 14.15-15.45 |
|---|---|
| Lecture rooms: | 024, Campus E1.4 |
| Lecturer: | Thomas Sauerwald |
| Audience: | The course counts as computer science lecture (2 SWS, 6 CP). The lecture will be given in English. |
| Exercises: | There will be 4 problem sets and you need to collect 50 percent of the points in order to be eligible for the final exam. |
| Final Exam: | The final exam will take place on Feb 21 (room TBA). |
Sublinear algorithms is a new area, where the algorithm is required to give an (approximate) answer without reading or storing the whole input. It is of particular interest in the study of massive data sets that occur in many applications such as financial transitions, Internet traffic analysis, biological databases etc. Due to the sheer size of these data sets that goes beyond billions, even linear time algorithms may be far too slow.
Despite the seemingly strong requirement to run in sublinear time, sublinear time algorithms exist for various problems in databases, graph theory, geometry, combinatorial optimization, string operations and statistical analysis. In this course we will introduce the basic models and techniques of sublinear algorithms, and cover some of the highlights in this exciting area.
| Date | Topic | Reference | |
|---|---|---|---|
| Oct 17 | 1. Introduction, Motivation, Examples | Slides |
|
| Oct 25 | 2. Testing Monotonicity of Lists, Approximating Number of Connected Components | Lecture Notes |
|
| Oct 31 | 3. Approximating Number of Connected Components (analysis), Hoeffding's inequality (incl. proof) | Lecture Notes |
|
| Nov 7 | 4. Testing Properties of Distributions (Uniformity) | Lecture Notes |
|
| Nov 14 | 5. Testing Properties of Distributions (Uniformity (cntd.), Lower Bound) | see Notes from Lecture 4 or Notes from Lecture 6 |
|
| Nov 21 | 6. Testing Properties of Distributions (Lower Bound (cntd.)), Testing Closeness of Distributions | Lecture Notes |
|
| Nov 28 | 7. Testing Properties of Dense Graphs: Bipartiteness | Lecture Notes (small update on Dec. 14) | |
| Dec 5 | 8. Testing Properties of Dense Graphs: Bipartiteness (cntd.) | see updated Notes from Lecture 7 | |
| Dec 12 | 9. Testing Properties of Dense Graphs: MAX-CUT | Lecture Notes |
|
| Dec 19 | 10. Testing Properties of Dense Graphs: MAX-CUT | see updated Notes from Lecture 9 | |
| Jan 9 | no class | ||
| Jan 16 | 11. Regularity Lemma | see the book "Graph Theory" (Chapter 7) by Reinhard Diestel | |
| Jan 23 | 12. Regularity Lemma (cntd.) | ||
| Jan 30 | 13. Regularity Lemma: Application to Testing Triangle-Freeness | Lecture Notes |
|
| Feb 6 | 14. Streaming Algorithms: Count-Min-Sketch and Approximating the Number of Distinct Elements | Lecture Notes |