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:
- Tuesdays 11:30-12:30 in Bloomberg 277 with Julia
- Wednesdays 2:30-3:30 in Bloomberg 277 with Iris
- Wednesdays 3:30-4:30 in Bloomberg 277 with Ishan
- Thursdays 10-12 in Bloomberg 267 with Fei
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) | |
| 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
- Grade Breakdown: Your grade will be determined by the assignments (30%), one prelim (25%), a final exam (35%), and quizzes (10%).
- Homework: There will be approximately four short programming assignments. Each assignment will have a due date for completion.
- Late Policy: Each student has a total of one slip day that may be used without penalty for homework. We will also drop your lowest quiz score and lowest homework score.
- Collaboration: You are required to work in groups of 2 students on each assignment. Please indicate the name of your collaborator at the top of each assignment and cite any references you used (including articles, books, code, websites, and personal communications). If you're not sure whether to cite a source, err on the side of caution and cite it. You may submit just one writeup for the group. Remember not to plagiarize: all solutions must be written by members of the group. If you are the odd person out we will have you join an existing group of 2.
- Quizzes: There will be short multiple-choice quizzes, generally at the end of the week. These are take home, and due within 24 hours.
- Prelim: In class, on Thursday October 25. The exam is closed book.
- Final Exam: In class, on Tuesday December 4. The exam is closed book.