CS 5112 Fall 2018

Algorithms and Data Structures for Applications

Course Description

An introduction to some fundamental algorithms and data structures used in current applications. Cryptocurrencies (hashing, Merkle trees, proofs of work), AI (nearest neighbor methods, k-d trees, autoencoders), and VR/AR (gradient descent, least squares, line-drawing algorithms). Lectures will be supplemented with occasional applied clinics taught in the evening. Programming assignments in Python.

Prerequisites

Familiarity with basic programming, algorithms and data structures (at the level taught in a sophomore course), or permission of instructor.

Course Staff

Instructors: Ramin Zabih and Greg Zecchini

TA: Richard S. Bowen; Irena Papst, Neil Adit

Graders/consultants: Fei Li, Julia Narakornpichit, Ishan Virk, Iris Zhang

Communication

Please join our slack workspace (must use an @cornell.edu email address). The #announce channel on that workspace is the channel by which we will distribute all course information.

Room & Time

Lecture: Tuesdays and Thursdays, 12:30pm - 1:45pm, Bloomberg Center 131, Cornell Tech

Evening clinics 6:30-8pm on the following Thursdays: 8/23, 8/30, 9/6, 9/20 and 10/4

Office hours:

Class number: 17766

Lectures

Date Lecture Slides
8/23 Lecture 1: Dijkstra’s Algorithm PDF, Powerpoint
8/28 Lecture 2: Cryptocurrency Intro & Digital Signatures PDF, Powerpoint
8/30 Lecture 3: Hashing PDF, Powerpoint
9/4 Lecture 4.1: Hashing Applications
Lecture 4.2: Consensus Algorithms (Proof of Work)
PDF, Powerpoint
PDF, Powerpoint
9/6 Lecture 5: Consensus Algorithms (Proof of Work cont.) PDF, Powerpoint
9/11 Lecture 6: Consensus Algorithms (Paxos) PDF, Powerpoint
9/13 Lecture 7: Some Distributed Applications PDF, Powerpoint
9/18 Lecture 8: Distributed Applications continued; bits PDF, Keynote
9/20 Lecture 9: Smart contracts (Ari Juels guest lecture) PDF
9/20 Clinic: Readability, Testing PDF, Keynote
9/25 Lecture 10: Universal hashing, nearest neighbors PDF, Powerpoint
9/27 Lecture 11: Density estimation PDF, Powerpoint
10/2 Lecture 12: Exact Nearest Neighbor Algorithms PDF, Powerpoint
10/4 Lecture 13: Streaming algorithms PDF, Powerpoint
10/9 No lecture (Columbus Day)  
10/11 Lecture 14: Convolution PDF, Powerpoint
10/16 Lecture 15: Dynamic Programming PDF, Powerpoint
10/18 Lecture 16: Dynamic Programming (Part 2) PDF, Powerpoint
10/23 Lecture 17: exam review  
10/25 Exam (prelim)  
10/30 Lecture 18: Locality-sensitive hashing PDF, Powerpoint
11/1 Lecture 19: Association rules PDF, Powerpoint
11/6 Lecture 20: Image segmentation PDF, Powerpoint
11/8 Lecture 21: Robust methods PDF, Powerpoint
11/13 Lecture 22: Union-Find PDF, Powerpoint
11/15 Lecture 23: Max Flow / Min Cut PDF, Powerpoint
11/20 Lecture 24: Intro to Complexity Theory PDF, Powerpoint
11/22 No lecture (Thanksgiving)  
11/27 Lecture 25: Max flow for computer vision Microsoft blog post PDF, Powerpoint
11/29 Lecture 26: Exam review  
12/4 Exam (final)  

Assignments

All assignments are available on the course CMS. Due dates for assignments without CMS links are tentative.

Assignment Due Date
Assignment 1: Dijkstra’s Algorithm September 6
Assignment 2: HashTables and Bloom Filters September 20
Assignment 3: Boyer Moore and Huffman Coding October 23
Assignment 4: Dynamic Programming November 29

Textbooks: none

Course Requirements and Grading