General Information

Meetings: MWF 2:30–3:20pm
Zoom link: https://cornell.zoom.us/j/95805639767?pwd=OXZCUG1OVVRYRnN4TVpBbmdGUXRPUT09
(authenticated Cornell users only)
Instructor:

• Bobby Kleinberg, Gates Hall 317, email
  office hours: Wednesdays 3:45-4:45, Thursdays 3:00-4:00

Ed Discussions: https://edstem.org/us/courses/43368/discussion/

Course Description

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, submodular optimization, NP-complete problems, approximation algorithms, spectral methods, Markov chains.

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).
• probability: sample spaces, random variables, expectation and variance, independence, conditional probability and expectation, Markov's and Chebyshev's Inequalities.

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

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.

At the end of the semester, students will be asked to complete a project, which could involve reading and summarizing a research paper, implementing and evaluating algorithms, 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 an in-class midterm exam. It will be an open book and notes, closed Internet exam. Each student will work on the midterm individually.

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, including research-related travel.

Grading

Your course grade will be based on the homework, project, and midterm exam. Weighting will be roughly 60% homework, 20% project, and 20% midterm.

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 two weeks 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 Gradescope, including an explanation of the grading error.

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

Gradescope

We are using Gradescope 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. In that case, 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 Gradescope. 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.

Course Material Copyright

Course materials posted on this website, Gradescope, Ed, or Canvas, are intellectual property belonging to the author. Students are not permitted to redistribute, buy, or sell any course materials without the express permission of the instructor. Such unauthorized behavior constitutes academic misconduct. You may not repost course materials released on Gradescope or Canvas publicly. These materials are intellectual property and meant for participants in the course. They are not free to the public.

Ed Discussions

We will be using Ed Discussions as an online discussion forum. If you are enrolled in the course you should be automatically added to the discussion site. Email the course administrator if you're having trouble with this.

You are encouraged to post any questions you might have about the course material. The course staff monitor Ed 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.

Ed Discussions 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 Ed Discussions and all course announcements will be posted there, so check in often.

Special Needs

Students with Disabilities: Your access in this course is important to us. Please register with Student Disability Services (SDS) to document your eligibility early in the semester, and let us know so that we have adequate time to arrange your approved academic accommodations.

Once SDS approves your accommodation, a letter will be emailed to you and the instructor. Please follow up with the instructor to discuss the necessary logistics of your accommodations. If you are approved for exam accommodations, please consult with the instructor at least two weeks before the scheduled exam date to confirm the testing arrangements.

Efforts have been made to comply with all accessibility requirements. If you experience any access barriers in this course, such as with printed content, graphics, online materials, or any communication barriers, please reach out to the instructor or your SDS counselor right away. If you need an immediate accommodation, please speak with the instructor after class or email the instructor and SDS at sds_cu@cornell.edu. If you have or think you may have a disability, please contact SDS for a confidential discussion: sds_cu@cornell.edu, 607-254-4545, sds.cornell.edu.

Inclusiveness

You should expect and demand to be treated by your classmates and the course staff with respect. You belong here, and we are here to help you learn and enjoy this course. If any incident occurs that challenges this commitment to a supportive and inclusive environment, please let the instructors know so that the issue can be addressed. We are personally committed to this, and subscribe to the Computer Science Department's Values of Inclusion.