CS-448 / 4 credits

Teacher: Kapralov Mikhail

Language: English

Remark: Cours biennal, donné les années impaires


Summary

In this course we will define rigorous mathematical models for computing on large datasets, cover main algorithmic techniques that have been developed for sublinear (e.g. faster than linear time) data processing. We will also discuss limitations inherent to computing with constrained resources.

Content

Keywords

streaming, sketching, sparse recovery, sublinear algorithms

Learning Prerequisites

Required courses

Bachelor courses on algorithms, complexity theory, and discrete mathematics

Important concepts to start the course

Discrete probability; mathematical maturity

Learning Outcomes

By the end of the course, the student must be able to:

  • Design efficient algorithms for variations of problems discussed in class
  • Analyze space/time/communication complexity of randomized algorithms
  • Prove space/time/communication lower bounds for variations of problems discussed in class
  • Choose an appropriate algorithmic tool for big data problem at hand

Teaching methods

Ex cathedra, homeworks, final

Assessment methods

Continuous control

Supervision

Office hours Yes
Assistants Yes
Forum Yes

In the programs

  • Semester: Fall
  • Exam form: During the semester (winter session)
  • Subject examined: Sublinear algorithms for big data analysis
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: During the semester (winter session)
  • Subject examined: Sublinear algorithms for big data analysis
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: During the semester (winter session)
  • Subject examined: Sublinear algorithms for big data analysis
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: During the semester (winter session)
  • Subject examined: Sublinear algorithms for big data analysis
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: During the semester (winter session)
  • Subject examined: Sublinear algorithms for big data analysis
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: During the semester (winter session)
  • Subject examined: Sublinear algorithms for big data analysis
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: During the semester (winter session)
  • Subject examined: Sublinear algorithms for big data analysis
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: During the semester (winter session)
  • Subject examined: Sublinear algorithms for big data analysis
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks

Reference week

 MoTuWeThFr
8-9     
9-10     
10-11  INF213  
11-12    
12-13  INF213  
13-14     
14-15     
15-16     
16-17     
17-18     
18-19     
19-20     
20-21     
21-22     

Wednesday, 10h - 12h: Lecture INF213

Wednesday, 12h - 13h: Exercise, TP INF213