Skip to main content



Course Information

CS 4820 develops techniques used in the design and analysis of algorithms, with an emphasis on problems arising in computing applications. Example applications are drawn from systems and networks, artificial intelligence, computer vision, data mining, and computational biology. This course covers four major algorithm design techniques (greedy algorithms, divide and conquer, dynamic programming, and network flow), computability theory focusing on undecidability, computational complexity focusing on NP-completeness, and algorithmic techniques for intractable problems, including identification of structured special cases, approximation algorithms, and local search heuristics.

Time and Place

MWF 9:05–9:55, Ives 305.

Prerequisites

CS 2800 and CS 3110.

We will assume that everyone has seen elementary data structures, searching, sorting, and basic terminology involving graphs, including the concepts of depth-first search and breadth-first search. These topics are reviewed in the text.

The lectures and homework involve the analysis of algorithms at a fairly mathematical level. We expect everyone to be comfortable reading and writing proofs at the level of CS 2800.

Text

Kleinberg and Tardos, Algorithm Design, Addison Wesley/Pearson, 2005. ISBN 0-321-29535-8.

Note that, although the text was designed for this course, there will be topics covered in lecture that are not in the text and there will be topics in the text that are not covered in lecture. You are responsible for topics covered in lecture and for any assigned reading in the text.

The following are some other useful references.

Syllabus

The syllabus lists the topics to be covered in lecture and the corresponding chapters in the text. This is subject to change.

Handouts

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

Piazza

We will be using Piazza as an online discussion forum. Piazza 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 Piazza 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, 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.

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

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

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!

CMS

We will be using the CS course management system CMS to manage course grades. Everyone who preregistered for the course should already be entered, but if you did not preregister, you are probably missing. Please login to CMS and check whether you exist. There will be a list of courses you are registered for, and CS 4820 should be one of them. If not, please send your full name and Cornell netId to Michelle <Turn on JavaScript to view email address> 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 we are recording things properly. The system also provides some grading statistics. There is a help page with instructions.

Staff and Office Hours

Staff members, along with their email addresses and office hours, are listed on Piazza.

Homework

There will be regularly scheduled homework sets due at 11:59pm on the due date. Homework must be submitted electronically to CMS.

Late Homework: It is expected that homework will be turned in on time. Assignments can be turned in late until 4pm the next day with a penalty of 8 points out of 30 for the assignment. Beyond that time, late homework will not be be accepted except in an emergency. If a genuine emergency exists, you must inform the course staff as soon as possible.

Deadline Extensions: Each student is entitled to one extension of the homework deadline during the semester, if the student has a valid excuse and requests the extension at least twelve hours in advance of the deadline. In the event of such a request, the deadline will typically be extended 72 hours. The definition of valid excuse is quite liberal and will be interpreted to include excessive workload in other classes, travel for academic reasons or for a job interview, minor illness, or other reasons at the instructor's discretion. Extensions for major illness or family emergency do not count against this entitlement.

Submitting Homework: You must submit an electronic version of your homework to CMS. You may either type it using typesetting software—we recommend LaTeX—or write it by hand and scan it. If you handwrite and scan, please write on only one side of the paper (the writing on the other side often bleeds through), make sure the scan is readable with good contrast, and save your scan using a compressed format such as .jpg or .gif (not .bmp, please). It is your responsibility to check that your scan is legible. It is probably a good idea to keep your handwritten original in case of any difficulties. Scanners are available in the computer labs.

Collaboration: On the homework, you are encouraged to discuss general approaches and techniques with others, but you must write up the solutions by yourself, with no collaboration. Please see the section on Academic Integrity below for further clarification of this policy.

Exams

Exams are closed book.

Students requiring a makeup exam must speak to the instructor by Friday, January 25, 2013. Please see the Registrar's exam page for policies and procedures.

Grading

Your course grade will be based on the homework and exams, weighted as follows.

Grading Criteria: For the most part, you will be asked to design algorithms for various problems. There will be no 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. When asked, a complexity analysis should also be provided.

Homework Regrades: If you believe your solution to a homework question was correct and it was marked incorrect, then you should write an explanation of the grading error and submit it in CMS. Regrade requests must be made within one week of the time that the homework scores are released.

Exam Regrades: Write up an explanation of the grading error, attach it to your exam, and submit it to the TA who graded the question. Alternatively, you can leave the exam and written explanation with the instructor. Regrade requests must be made within one week of the time that the exam scores are released.

You may request a regrade for a correct solution that was marked incorrect. In general, we will not consider regrade requests that simply argue about the amount of partial credit assigned.

Academic Integrity

The utmost level of academic integrity is expected of all students. Violations will be penalized severely. 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 your own work. You must write up (and understand) the solutions by yourself, with no collaboration. In particular, you may not work from written notes taken in discussion with others. Under no circumstances may you hand in work done with or by someone else under your own name or share solutions with anyone else.

You must acknowledge by name anyone with whom you collaborated and any outside sources (apart from the course text) that you consulted, including Internet sources.

All exams are closed book. 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.

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.