Course Identification

Sublinear time and space algorithms
20204182

Lecturers and Teaching Assistants

Prof. Robert Krauthgamer
Dr. Ohad Trabelsi

Course Schedule and Location

2020
Second Semester
Monday, 14:15 - 16:00, Ziskind, Rm 1
20/04/2020

Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Lecture; Elective; Regular; 2.00 points

Comments

Will be taught via Zoom starting April 19th.

Prerequisites

Basic knowledge of algorithms, probability and linear algebra at an undergraduate level.

Restrictions

60

Language of Instruction

English

Attendance and participation

Expected and Recommended

Grade Type

Numerical (out of 100)

Grade Breakdown (in %)

50%
50%

Evaluation Type

Take-home exam

Scheduled date 1

N/A
N/A
-
N/A

Estimated Weekly Independent Workload (in hours)

2

Syllabus

The course will cover algorithms whose running time and/or space requirement is sublinear in the input size. Such algorithms can view only a small portion of the entire input, but they are particularly suitable for analyzing massive data sets. In recent years, this approach has been successfully used in several areas, including graph theory, linear algebra, combinatorial optimization, geometry, and string matching.

Learning Outcomes

Upon successful completion of the course, students should be able to:

  1. Demonstrate knowledge of basic concepts in sublinear time and space algorithms
  2. Design sublinear algorithms. 
  3. Analyze sublinear algorithms. 

Reading List

N/A

Website