An introduction to some fundamental algorithms and data structures.
Familiarity with basic programming, algorithms and data structures (at the level taught in a sophomore course), or permission of instructor.
Instructors: Ramin Zabih and Greg Zecchini
TA: Gengmo Qi
Graders/consultants: Yue Wang, Ta-Wei Mao, Zhenwei Zhang, Yong Huang, Siyu Yao, Xiran Sun
Lecture: Monday and Wednesday, 5:00pm-6:15pm, Bloomberg auditorium
Office hours
-TA
- Gengmo: By appointment(email or Slack)
-Graders
- Monday 11:00 - 12:00: Ta-Wei Mao, Bloomberg 360
- Monday 15:00 - 16:00: Xiran Sun, Bloomberg 360
- Tuesday 11:00 - 12:00: Yong Huang, Bloomberg 377
- Wednesday 11:00 - 12:00: Siyu Yao, Bloomberg 377
- Thursday 14:00 - 15:00: Zhenwei Zhang, Bloomberg 375
- Thursday 15:00 - 16:00: Yue Wang, Bloomberg 377
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.
Topics and schedule are tentative and subject to change
Video recordings of the lectures can be found on Mediasite
| Date | Lecture | Slides | Deadlines |
|---|---|---|---|
| 9/4 | Lecture 1: Dynamic Programming | PDF, Powerpoint | |
| 9/9 | Lecture 2: Dynamic Programming (continued) | PDF, Powerpoint | |
| 9/11 | Lecture 3: Dijkstra | PDF, Powerpoint | Quiz 1 : due 9/13 |
| 9/16 | Lecture 4: Union find | PDF, Powerpoint | |
| 9/18 | Lecture 5: Balanced Trees | PDF, Powerpoint | Quiz 2 : due 9/20 |
| 9/23 | Lecture 6: k-d Trees for nearest neighbors | PDF, Powerpoint | HW1 released |
| 9/25 | Lecture 7: Minimum spanning trees | PDF, Powerpoint | Quiz 3 : due 10/2 |
| 9/30 | Lecture 8: Data representation and real-world efficiency | PDF, Powerpoint | |
| 10/2 | Lecture 9: Max flow / Min cut | PDF, Powerpoint | Quiz 4 : due 10/4 |
| 10/7 | Lecture 10: Association rules | PDF, Powerpoint | HW 1: due 10/7 |
| 10/9 | Lecture 11: More graph problems / Complexity theory | PDF, Powerpoint | Quiz 5 : due 10/11 |
| 10/14 | Indigenous Peoples' Day, no class | ||
| 10/16 | Lecture 12: Reductions, lower bounds and approximation algorithms | PDF, Powerpoint | Quiz 6 : due 10/18 |
| 10/21 | Lecture 13: Exam review | HW2 released | |
| 10/23 | Prelim | 2018 Prelim | Prelim coverage changes from year to year |
| 10/28 | Lecture 14: Concurrency | PDF, Powerpoint | |
| 10/30 | Lecture 15: Distributed Computing | PDF, Powerpoint | Quiz 7 : due 11/1 |
| 11/4 | Lecture 16: Streaming algorithms | PDF, Powerpoint | HW2 due |
| 11/6 | Lecture 17: Streaming algorithms and hashing | PDF, Powerpoint | HW3 release, Quiz 8 : due 11/8 |
| 11/11 | Lecture 18: Proof by Induction | PDF, Powerpoint | |
| 11/13 | Lecture 19: Reductions, lower bounds, hashing | PDF, Powerpoint | Quiz 9 : due 11/15 |
| 11/18 | Lecture 20: Distributed hashing | PDF, Powerpoint | |
| 11/20 | Lecture 21: Locality sensitive hashing | PDF, Powerpoint | HW3 due |
| 11/25 | Lecture 22: Back propogation | PDF, Powerpoint | Quiz 10 : due 11/26 |
| 11/27 | Thanksgiving break, no class | ||
| 12/2 | Lecture 23: Max flow for computer vision | PDF, Powerpoint | HW4 due |
| 12/4 | Lecture 24: Exam review | ||
| 12/9 | Final Exam, in class | 2018 Final | Final coverage changes from year to year |
All assignments are available on the course CMS. Due dates for assignments without CMS links are tentative.
| Assignment | Due Date |
|---|---|
| Assignment 1: Dynamic Programming | October 7 |
| Assignment 2: Graph Shortest Path | November 4 |
| Assignment 3: Reduction | November 20 |
| Assignment 4: Streaming & hashing | December 2 |
Recommended textbook: Mining of Massive Datasets
- Grade Breakdown: Your grade will be determined by the assignments (25%), one prelim (25%), a final exam (35%), and quizzes (15%). All assignments will be available on the course CMS.
- 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. An assignment can be at most one day late without penalty via slip days.
- 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. Tentative date: Wednesday October 23. The exam is closed book.
- Final Exam: In class. Date: Monday December 9. The exam is closed book.