ECS 189A – Sublinear Algorithms for Big Data

ECS 189A: Sublinear Algorithms for Big Data
Fall 2024

Staff

Time/Location

Time: Tuesdays and Thursdays, 4:40pm-6:00pm
Location: Teaching and Learning Complex 3214

Course Description

A huge quantity of data is worth little unless we can extract insights from it. Yet, the large quantities mean that classic algorithms (running in linear, quadratic or even more time) can be infeasible in practice. We must instead turn to new algorithmic approaches and paradigms, which allow us to answer valuable questions about our data in runtime that is still feasible even when the data set is Facebook-sized.

Surprisingly, to answer many computational and statistical questions, sometimes there is no need to read/store every piece of data! This course focuses on this exciting "sublinear" algorithmic regime.

See the course missive for details on assessment and various policies.

Piazza: Link (you might need to access it through Canvas for the first time)

**Counts as a "field of specialization" course for GGAM programmes (MS and PhD)

Prerequisites

This is an advanced undergraduate level course that is also suitable for graduate students.

Suggested prior courses (see course missive above for details, and see Homework 0):

ECS 20 or equivalent, for basic discrete math, and
ECS 132 or MAT 135A or STA 130A or equivalent, for basic probability (and linear algebra), and
ECS 122A or ECS 222A or equivalent, for basic algorithm analysis

Email the instructor if you have questions about whether you are prepared for the course.

Mathematical maturity is essential: we will prove most of the results covered in the class. Almost all homework problems will require proof-writing.