Lecture time:  Wednesday 14.1515.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: MAXCUT  Lecture Notes 

Dec 19  10. Testing Properties of Dense Graphs: MAXCUT  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 TriangleFreeness  Lecture Notes 

Feb 6  14. Streaming Algorithms: CountMinSketch and Approximating the Number of Distinct Elements  Lecture Notes 