Krzysztof Onak > Teaching > Algorithmic Techniques for Taming Big Data (DS-563, Fall 2021)

Algorithmic Techniques for Taming Big Data (DS-563/CS-543, Fall 2021)

Course Description: Growing amounts of available data lead to significant challenges in processing them efficiently. In many cases, it is no longer possible to design feasible algorithms that can freely access the entire data set. Instead of that, we often have to resort to techniques that allow for reducing the amount of data such as sampling, sketching, dimensionality reduction, and core sets. Apart from these approaches, the course will also explore scenarios in which large data sets are distributed across several machines, or even geographical locations, and the goal is to design efficient communication protocols or MapReduce algorithms.

The course will include a final project and programming assignments in which we will explore the performance of our techniques when applied to publicly available data sets. Throughout the course, we will explore various strategies for implementing techniques that have theoretical guarantees in practice.

Instructor: Krzysztof Onak (
Office Hours: Tuesday 4–6pm, MCS 138N (or adjacent common area)

Teaching Fellow: Nadya Voronova (
Office Hours: Wednesday 2–4pm, MCS 141

Lecture: Tuesday/Thursday 2–3:15, MCS B33
Discussion: Wednesday 10:10–11am, MCS B37

Piazza (announcements and discussions):
Gradescope code for submitting homework: BPDKV8

Satisfies the Following HUB Units: Quantitative Reasoning II (QR2) and Creativity/Innovation (CRI)


Useful Auxiliary Materials


Note: the due date is subject to change until the assignment is handed out.

Course Requirements

Apart from active participation, the class will require solving homework problem sets, two experimental programming assignments, and a final project. The overall grade will be based on the following factors:

Programming Assignments: The course will feature two programming assignments in which students will implement algorithms covered in class and apply them to data sets of their choice. Collaboration here is not allowed (except for discussing high–level ideas), i.e., students are required to implement algorithms and run experiments on their own.

Final Project: Possible final projects ideas include but are not limited to

The outcome of a project will be a short technical report, describing obtained results and conclusions. As opposed to programming assignments, students are allowed to work in teams of two or three. A list of potential projects topics will be provided, but students are encouraged to develop their own ideas. These projects have to be approved by the instructor.

Late Homework Policy: No extensions (except for extraordinary circumstances). If you submit your programming assignment or homework one day late, you may lose 10% of points.

Laptop and Cellphone Policy

Using laptops, cellphones, tablets, and other similar electronic devices is generally not allowed. If you want to use your laptop or tablet for taking notes, you have to email a copy of your notes to me after the class and you are not allowed to use your device for other purposes, such as replying to emails or browsing the web.


Self–assessment questionnaire: Since advanced courses offered through the Faculty of Computing & Data Sciences are meant to be open to students from various disciplines, we provide an on-line questionnaire to assist students with self–assessment and placement. Please follow this link to access it.

Tentative Syllabus