CS 6820 :  Analysis of Algorithms
Fall 2016

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

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:

• Cornell University Code of Academic Integrity
• Computer Science Department Code of Academic Integrity
• Explanation of AI Proceedings

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.

---