Skip to main content





Announcements

  • The first class meeting will be on August 24 at 2:30pm in Gates Hall G01 (ground floor, below the main entrance).

Overview

This is a first-year Ph.D.-level course on the design and analysis of algorithms, intended for graduate students and advanced undergraduates. We will focus on the core theory of algorithms; practical applications will receive much more limited coverage. Topics to be covered will include graph algorithms (especially for computing matchings and network flows), linear and semidefinite programming, convex optimization, fast algorithms for solving linear systems, spectral methods, Markov chains, submodular optimization, NP-complete problems, approximation algorithms, online algorithms, and a survey of some algorithmic techniques for manipulating massive data.

Instructor: Robert Kleinberg

Course information

Time and Place

Monday, Wednesday, Friday, 2:30-3:20pm.
Mentor's Lecture Hall, G01 Gates. (ground floor, below the main entrance).

Course Staff

  • Robert Kleinberg (Instructor)

    317 Gates Hall
    Office hours: Wednesday 3:45-4:45, Thursday 1:00-2:00
  • Soroush Alamdari (Teaching Assistant)

    Office hours: CIS tutoring office 105 at Surge Academic Building, 222 Tower Road
    Tuesday 12:00-1:00, Thursday 3:00-4:00
  • Jenna Edwards (Course Administrator)

    401 Gates Hall
    Email: jls478@cornell.edu

Prerequisites

CS 4820 or equivalent, i.e. an advanced undergraduate-level algorithms course. If you are unsure whether CS 6820 or CS 4820 is the right course for you, please talk to the instructor.

We will assume knowledge of:

  • discrete mathematical structures, including graphs, trees, DAGs
  • basic data structures such as lists, trees, heaps, sorting and searching
  • asymptotic complexity, O( ) and o( ) notation, solving recurrences
  • machine models and general computability
  • algebra: linear algebra (including eigenvalues and eigenvectors), basic facts about polynomials over the real and complex numbers and the integers mod p.
  • probability: sample spaces, random variables, expectation and variance, independence, conditional probability and expectation.

Texts

You are required to read the course notes posted on the web site. These will sometimes contain more detail than what was presented in lecture.

Optional Textbooks

  • The Design and Analysis of Algorithms, by Dexter Kozen.
  • Algorithm Design, by Jon Kleinberg and Éva Tardos.

Homework, Project, and Exams

In the first half of the semester there will be problem sets roughly every two weeks. The problem sets will generally be handed out on a Friday and will be due on the Friday two weeks hence.

Students may work on homework in groups of up to four people. Collaboration is encouraged. Each group may turn in a single solution set that applies to all members of the group. However, students are asked to understand each of their group's solutions well enough to give an impromptu white-board presentation of the solution if asked.

Acknowledge all sources, including others in the class from whom you obtained ideas and any Internet sources.

In the second half of the semester, students will be asked to complete a project, which could involve reading and summarizing research papers, implementing and evaluating algorithms from the lectures or readings, undertaking original research in algorithms, or a combination of the above. Students may work on projects in groups of up to four people.

There will a midterm and a final. Both of them will be open book and notes, closed Internet, take-home exams. Student will work on exams individually. Dates of the take-home exams are TBA.

Late Homework Policy

    Please make every effort to submit your homework solutions in a timely fashion. Late submissions will be subject to a grade penalty equivalent to 20 percent of the value of the assignment.

    Solution sets will typically be posted three days after the deadline of an assignment, and late submissions will not be accepted after the solution set has been posted.

    Extensions will be granted, by permission of the instructor, in case of illness or other acceptable excuses.

Grading

Your course grade will be based on the homework, project, and exams. Weighting will be roughly 40% homework, 20% project, and 40% exams.

Grading criteria: For the most part, the homework will ask you to design and analyze algorithms for various problems. (There will not be any programming assignments.) A complete answer consists of a clear description of an algorithm (an English description is fine), followed by an analysis of its running time and a proof that it works correctly. You should try to make your algorithms as efficient as possible. Compared to CS 4820, the grading in CS 6820 places greater emphasis on writing correct and complete proofs.

Regrade requests must be made within one week of the time that the course staff announces the assignment or exam is graded. If you believe your solution to a question was correct and it was marked incorrect then you should enter a regrade request into CMS, including an explanation of the grading error. Instructions for requesting regrades on CMS can be found in the CMS User Documentation: follow the “Help” link in the left frame, then select the subtopic “Assignment Pages”.

Academic Integrity

The utmost level of academic integrity is expected of all students. Academic integrity is rarely an issue in graduate courses, but unfortunately it does arise from time to time, so we want to be clear.

Under no circumstances may you submit work done with or by someone else under your own name or share detailed proofs with anyone else except your partner(s). However, general questions regarding proof techniques or the requirements of the assignment are permissible.

You must cite all sources, including Internet sources. You must acknowledge by name anyone whom you consulted. You may not give nor receive assistance from anyone else during an exam. You may not give any hints or post any material that might be part of a solution publicly on Piazza. If your question necessarily includes such material, post privately.

If you are unsure about what is permissible and what is not, please ask.

Academic Integrity Resources:

CMS

We are using the course management system CMS for managing assignments, exams, and grades. Everyone who preregistered for the course should be entered by the first day of classes, but if you did not preregister, you may be missing. Please login and check whether you exist. There will be a list of courses you are registered for, and CS 6820 should be one of them. If not, please send your full name and Cornell netId to the Course Administrator so that you can be registered.

You can check your grades, submit homework, and request regrades in CMS. Please check your grades regularly to make sure we are recording things properly. The system also provides some grading statistics. There is a help page with instructions.

Please do not repost course materials released on CMS publicly. These materials are intellectual property and meant for participants in the course. They are not free to the public.

Piazza

We will be using Piazza as an online discussion forum. You will need to register as a student in the course by visiting https://piazza.com/cornell/fall2016/cs6820.

You are encouraged to post any questions you might have about the course material. The course staff monitor Piazza closely and we aim to give a quick response. If you know the answer to a question, you are encouraged to post it (but please avoid giving away any hints on the homework or posting any part of a solution--this is considered a violation of academic integrity).

By default, your posts are visible to the course staff and other students, and you should prefer this mode so that others can benefit from your question and the answer. However, you can post privately so that only the course staff can see your question, and you should do so if your post might reveal information about a solution to a homework problem. You can also post anonymously if you wish. If you post privately, we reserve the right to make your question public if we think the class will benefit.

Piazza is the most effective way to communicate with the staff and is the preferred mode of interaction. Please reserve email for urgent or confidential matters. Free-ranging technical discussions are especially encouraged. Broadcast messages from the course staff to students will be sent using Piazza and all course announcements will be posted there, so check in often.

Special Needs

We provide appropriate academic accommodations for students with special needs and/or disabilities. Requests for academic accommodations are to be made during the first three weeks of the semester and must be accompanied by official documentation. Please register with Student Disability Services in 420 CCC to document your eligibility.

This schedule is provisional. All dates for lectures and unreleased assignments and exams are subject to change.
Lecture Date Topic Readings Other notes
1 24 Aug Matchings I:
Maximum bipartite matching
Notes on matchings
2 26 Aug Matchings II:
Hopcroft-Karp algorithm
Notes on matchings
3 29 Aug Matchings III:
Finish Hopcroft-Karp
Notes on matchings
4 31 Aug Matchings IV:
Min-cost bipartite perfect matching
Notes on matchings Optional additional reading: Non-bipartite matching.
5 2 Sep Flow I:
Ford-Fulkerson. Max-flow min-cut.
Notes on flow algorithms Assignment 1 released.
5 Sep No class Labor Day
6 7 Sep Flow II:
Combinatorial applications
Notes on flow algorithms
7 9 Sep Flow III:
Edmonds-Karp and Dinitz
Notes on flow algorithms
8 12 Sep LP I:
Introduction
Notes on LP
by Éva Tardos
9 14 Sep LP II:
Simplex algorithm.
Simplex method notes
10 16 Sep LP III:
LP duality
Simplex method notes
Assignment 1 due at 18:00.
Assignment 2 released.
11 19 Sep NP-Completeness I Notes on reductions
12 21 Sep NP-Completeness II Notes on reductions
13 23 Sep Approximation Algorithms I:
LP-based and primal-dual algorithms
Notes on approx algs
14 26 Sep Approximation Algorithms II:
Randomized approximation algorithms
Notes on approx algs
15 28 Sep Approximation Algorithms III:
Chernoff bound
Notes on approx algs
16 30 Sep Approximation Algorithms IV:
Routing to minimize congestion
Notes on approx algs Assignment 2 due at 18:00.
Assignment 3 released.
3 Oct No class Rosh Hashanah
17 5 Oct Multiplicative Weights I:
Predicting from expert advice
Notes on mult weights
18 7 Oct Multiplicative Weights II:
Packing/covering LPs
Notes on mult weights
10 Oct No class Fall Break
19 12 Oct Multiplicative Weights III:
Application to sparsest cut
Notes on mult weights
20 14 Oct Semidefinite Programming I:
Solving SDPs
Notes on SDPs Assignment 3 due at 18:00.
21 17 Oct Semidefinite Programming II:
Approximating Max-Cut
Notes on SDPs Take-home midterm released.
22 19 Oct Convex Optimization I:
Gradient Descent
Notes on convex optimization Take-home midterm due on 20 Oct.
23 21 Oct Convex Optimization II:
Online convex optimization
Notes on convex optimization
24 24 Oct Submodular Optimization I:
Unconstrained minimization
Notes on submodular optimization
25 26 Oct Submodular Optimization II:
Constrained maximization
Notes on submodular optimization
26 28 Oct Spectral Methods I:
The graph Laplacian
Notes on spectral methods Project proposals due.
27 31 Oct Spectral Methods II:
Cheeger's inequality
Notes on spectral methods
28 2 Nov Spectral Methods III:
Planted clique
Notes on spectral methods
29 4 Nov Spectral Methods IV:
Robust PCA
Notes on spectral methods
30 7 Nov Markov Chains I:
Mixing time
Notes on Markov chains
31 9 Nov Markov Chains II:
Metropolis alg; Gibbs sampling
Notes on Markov chains
32 11 Nov Markov Chains III:
d-regular bipartite matching
Notes on Markov chains