Sublinear algorithms

Course guarantor:

Dušan Knop

Lecturer:

Dušan Knop

Tutor:

Dušan Knop

Supervisor:

Department of Theoretical Computer Science

Synopsis:

We will introduce three methods to tackle algorithms working in sublinear space.

Requirements:

BI-AG1, BI-AG2, BI-PST.

Syllabus of lectures:

1. Motivation, Probability theory recap

2. Moriss Counter

3. Unique elements I

4. Unique elements II

5. Turnstyle model

6. Group Testing

7. Sparse vector recovery

8. Sparse Fourier Transform

9. Property Testing I

10. Property Testing II

11. Polynomial convolution

12. Modular subset sum

13. String algorithms

Syllabus of tutorials:

1. Motivation, Probability theory recap

2. Unique elements

3. Group Testing

4. Sparse vector recovery

5. Property Testing

6. Applications

Study Objective:

We will cover basics of sublinear algorithms.

Study materials:

- Simon Foucart, Holger Rauhut: A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis, Birkhäuser 2013, ISBN 978-0-8176-4947-0

- David P. Woodruff (2014), „Sketching as a Tool for Numerical Linear Algebra“, Foundations and Trends® in Theoretical Computer Science: Vol. 10: No. 1–2, pp 1-157. http://dx.doi.org/10.1561/0400000060

Note:

Further information:

https://courses.fit.cvut.cz/NI-SLA

No time-table has been prepared for this course

The course is a part of the following study plans:

• Master specialization Management Informatics, in Czech, 2020 (elective course)