Skip to main content

Course Info

Special COVID-19-related information for F22

Everyone is expected to abide by the university public health requirements at all times. See this page for the latest information. Please notify the course staff if you become ill or are placed in isolation or quarantine. Do not attend class if you are ill.

Enrollment information for F22

Seats are reserved for graduate students. Others will have to go on the waitlist. For instructions, please visit this page or email


Methodology for developing and analyzing efficient algorithms. Understanding the inherent complexity of natural problems via polynomial-time algorithms, advanced data structures, randomized algorithms, approximation algorithms, and NP-completeness.

4 credits, letter grade or S/U.

Approximate syllabus (topics covered as time permits):

Time & Place

MWF 2:40–3:30pm, Hollister B14 (Ithaca) and Bloomberg 497 (NYC).
Permanent Zoom link:
Instructions for phone access here.

Lectures will be given live during this time and you are expected to attend in person if you are able. Lectures will also be broadcast via Zoom for those who cannot attend in person. Lectures will not be recorded.


  Name/Position Contact Office hours Location
Photo of Dexter Kozen Dexter Kozen
436 Gates
[mouse over for email]
M 11am–12pm
or by appt
436 Gates
Photo of Corey Torres Corey Torres
401 Gates
[mouse over for email]
8am–4:30pm 401 Gates MWTh
remote TuF
Photo of Makis Arsenis Makis Arsenis
336 Gates
Teaching assistant
[mouse over for email]
Tu 10–11am 406 Rhodes
Photo of Jason Gaitonde Jason Gaitonde
324 Gates
Teaching assistant
[mouse over for email]
M 1–2pm
576 Rhodes


CS 4820 or graduate standing.

Familiarity with the content of CS 4820 is assumed. In particular, we will assume knowledge of:


There is no required text for the course, but in many cases online notes will be provided. You are responsible for topics covered in lecture and for any assigned readings.

The following are some other useful sources.

These titles are on reserve at the Engineering library.


The schedule page lists the topics to be covered in lecture and the corresponding readings in the text, exam dates, and homework due dates. This is subject to change.


Supplementary course material will be posted on the handouts page. Check often for new postings.


We will be using Ed as an online discussion forum. Ed allows for open discussions of all course-related questions. You are encouraged to post any questions you might have about the course material. The course staff monitor Ed closely and you will usually get a quick response. If you know the answer to a question, you are encouraged to post it.

By default, your posts are visible to the course staff and other students. You should prefer this mode so that others can benefit from your question and the answer. You can post anonymously if you wish.

You can also post privately, and only the course staff will see your question. You should use this mode if your post might reveal information about a solution to a homework problem or for communications of a sensitive nature. If you post any part of a solution publicly, it will be considered a violation of academic integrity.

Do not confuse anonymous posting with private posting. If you post privately when there is no need, we reserve the right to make your question public if we think the class will benefit.

Everyone who preregistered for the course should already be signed up. If you have never used Ed before, or if you did not preregister for the course, visit the signup page to sign yourself up.

Ed is the most effective way to communicate with the staff outside of office hours. Please avoid email if Ed will do.

All course announcements will be posted on Ed. Please check frequently for new postings.


We will be using the CS course management system CMS to manage course grades and assignments. We will not be using Canvas. Everyone who preregistered for the course should already be enrolled in CMS, but if you registered late, 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 Corey (mouse over for email) so that she can register you.

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


There will be biweekly homework assignments consisting of 4-6 problems due at 11:59pm on the due date. See the schedule page for due dates. Assignments and solutions will be posted in CMS.

Collaboration  Homework assignments may be done individually or in pairs. Collaboration with a partner is encouraged. If you collaborate, one of the group members must invite the other in CMS and the other must accept. Only one person in the group needs to submit the assignment. It should include the names and netIds of both collaborators.

Late Homework  Please make an effort to get your homework in on time. There is no late penalty for submitting after the deadline, but solutions will be posted usually within a day or two after the due date, and no homework will be accepted after solutions are posted.

Submitting Homework  You should submit a typeset electronic version of your homework to CMS in .pdf format. We recommend LaTeX for typesetting. Unfortunately we cannot accept scanned or photographed handwritten homework due to illegible script and large file sizes. LaTeX templates can be found on the handouts page.

After submitting your homework, please download it from CMS and double-check that you submitted what you intended to submit. If you submitted the wrong file, submitted a corrupt .pdf file, neglected to include a file, or something similar, out of fairness we cannot accept your solutions later.


There will be a 72-hour takehome prelim exam and a 72-hour takehome final exam. Exam dates are on the schedule page. Exams are cumulative. Download the exam from CMS when you are ready to take it. Upload your typeset solutions to CMS within 72 hours after downloading, but not later than 11:59pm on the last day of the exam period.


Your course grade will be based on the homework, prelim, and final exam.

Regrades  If you believe your solution to a question was correct and it was marked incorrect, then you should write an explanation of the grading error and submit it as a regrade request in CMS. You may also ask for a clarification. Regrade requests must be made within the deadline as posted on CMS. Please note that partial credit is not negotiable.

Academic Integrity

The utmost level of academic integrity is expected of all students. Please read the following carefully.

On the homework, you may discuss general approaches and techniques with others, but the specifics of the solution must be developed between you and your partner. Under no circumstances may you submit work done with or by someone else under your own name or share solutions with anyone else except your partner.

You must acknowledge all outside sources (apart from the course materials) that you consulted, including Internet sources.

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 Ed. If your question necessarily includes such material, post privately.

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

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 If you have or think you may have a disability, please contact SDS for a confidential discussion:, 607-254-4545,