Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2023/2024
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

Sublinear algorithms

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
NI-SLA Z,ZK 5 2P+1C Czech
Garant předmětu:
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
Time-table for winter semester 2023/2024:
Time-table is not available yet
Time-table for summer semester 2023/2024:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2024-05-23
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet7067806.html