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 cs-course-enroll@cornell.edu.

Overview

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

Review of basic graph algorithms: DFS, BFS, connected components, strongly connected components
Greedy algorithms: spanning trees, Steiner trees, matroids, arborescences, multicast cost-sharing
Advanced data structures: binomial and Fibonacci heaps, random treaps, self-organizing data-structures, disjoint sets
Network flows: maximum flows and minimum cuts, the preflow-push algorithm, minimum-cost flows, multicommodity flows; applications to matching, scheduling, network routing and vision
Dynamic programming: basic dynamic programming technique, dynamic programming on trees, tree decomposition, and algorithms for graphs with bounded tree width.
NP-completeness
Approximation algorithms: greedy algorithms, local search, on-line algorithms, primal-dual algorithms, linear programming, shortest vectors
Randomized algorithms: basic techniques from discrete probability, tail bounds, applications to optimization, distributed computation, packet routing
Lower bounds for constant depth circuits: random partial valuations, Haastad switching lemma
Algorithms in algebra and number theory: integer arithmetic, Csanky's algorithm, Chistov's algorithm, matrix rank, linear equations, polynomial gcds, fast Fourier transform, Luby's algorithm, primality testing

Time & Place

MWF 2:40–3:30pm, Hollister B14 (Ithaca) and Bloomberg 497 (NYC).
Permanent Zoom link: https://cornell.zoom.us/j/93585746762?pwd=TTJTNUY0b21IbUM0bVJDUnBMcC9BQT09
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.

Staff

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

Prerequisites

CS 4820 or graduate standing.

Familiarity with the content of CS 4820 is assumed. In particular, 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
finite automata, regular expressions, pushdown automata, context-free languages
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

Resources

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.

Dexter Kozen, The Design and Analysis of Algorithms
Jon Kleinberg and Éva Tardos, Algorithm Design
Thomas Corman, Charles Leiserson, Ronald Rivest, and Clifford Stein, Introduction to Algorithms (3rd ed.)
Vijay Vazirani, Approximation Algorithms

These titles are on reserve at the Engineering library.

Schedule

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.

Handouts

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

Ed

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.

CMS

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.

Homework

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.

Exams

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.

Grading

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

50% homework
25% prelim
25% 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 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.

CS 6820 Fall 22 Analysis of Algorithms