/CS5112-F18

CS5112 Fall 2018

Primary LanguageHTML

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) 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

  • 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.