Course Identification

Sublinear time and space algorithms
20184022

Lecturers and Teaching Assistants

Prof. Robert Krauthgamer
Chen Amiraz

Course Schedule and Location

2018
Second Semester
Sunday, 10:15 - 12:00, Ziskind, Rm 1
18/03/2018

Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Lecture; Elective; 2.00 points

Comments

N/A

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

Final assignment

Scheduled date 1

N/A
N/A
-
N/A

Estimated Weekly Independent Workload (in hours)

3

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