Computer Science 6820

Analysis of Algorithms

Cornell University, Fall 2014

Announcements

First day of class is Wednesday, August 27.

Basic course data

Time and Place: Monday, Wednesday, and Friday, 2:30 to 3:20 in Hollister 110.
Course description (from the Catalog): 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. Additional topics may include algebraic and number theoretic algorithms, circuit lower bounds, online algorithms, or algorithmic game theory.

Staff

Instructor:	Eva Tardos eva.tardos@cornell.edu 316 Gates Office hours: Monday 1:15-2:15 and Thursday 2:45-3:45 Phone: 255-0984
TA:	Matvey Soloviev msoloviev@cs.cornell.edu Office hours: Tuesday 5:00-6:00 (G15 Gates Hall)

Office Hour schedule during final week

Monday, Dec 8: 1:15-2:15 Eva Tardos in Gates 316
Tuesday, Dec 9: 5-6 Matvey Soloviev in Gates G15
Wednesday, Dec 10: 3:30-4:30 Matvey in Gates 324
Wednesday, Dec 10: 4:15-5:15 Eva Tardos in Gates 316
Thursday, Dec 11: 2:45-3:45 Eva Tardos in Gates 316
Friday, Dec 12: 2-3 Matvey Soloviev in Gates G15
Monday, Dec 15: 2-3 Matvey Soloviev in Gates G15
Tuesday, Dec 16: 2-3 Eva Tardos in Gates 316
Wednesday, Dec 17: 2:30-3:30 Eva Tardos in Gates 316
Thursday, Dec 18: 11-12 Eva Tardos in Gates 316

Prerequisites

The official prerequisites for the course are CS 4820 or graduate standing. 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
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

Graduate students who are interested in taking the class and may be missing some of these prerequisites should talk to the Instructor.

Homework and Exams

Homework will be assigned every ~2 weeks; it should be handed in via CMS. Some problem sets will have extra credit questions. Students who solve the required problems well, can get a A for the course, but you need to do a fair fraction (not all) of the extra credit work also to get an A+.

Late homeworks without prior permission will not receive credit. If a genuine emergency situation prevents you from handing in an assignment on time, which includes conflict with important professional engagement, such as interview or paper deadlines, come talk to me and we can work something out.
You are expected to support the answers to the homework with proofs. Much of the homework will consist of questions asking you to design algorithms for various problems. 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 do not need to implement the algorithm. You should try to make your algorithms as efficient as possible.
Students may work on homework in groups of up to 2-3 people. 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.
You should cite any sources that you use in working on a homework problem.

There will be a midterm and a final exam, both take-home.

Exams will be done as a take-home exam. Unlike the homework, the take-home final must be done completely on your own.
The final exams may be picked up from Amy Finch Elser ahf42@cornell.edu in 437 Gates. Time of the midterm tba. Final will be offered between Dec. 8 and 15. For both exams, you should submit your solutions to CMS within 72 hours of the time you pick up the exam.

Grading

Grades on the midterm, and the final, and the homework will be weighted as follows:

Midterm: 20%
Final: 30%
Homework: 50%

Grading Criteria

For the most part, you will be asked to design 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.

CMS

We are using the CS course management system at http://cms.csuglab.cornell.edu/ to manage course grades. Please check your grades regularly to make sure we are recording things properly. The system also provides some grading statistics.

Regrade Policy

Regrade requests must be made within one week of the time that homework or exams are returned to the class. If you believe your solution to a question was correct and it was marked incorrect then you should write up an explanation of the grading error, attach it to your homework, and bring it to the TA. Alternately, you can leave the homework and written explanation with the instructor. Note that we're talking here about correct algorithms that were treated as incorrect; in general, we will not look at regrade requests that are simply arguing about the amount of partial credit assigned. Regrade requests will be handled periodically in batch mode rather than on-the-spot.

Discussion Forum (Piazza)

We will be using Piazza as an online discussion forum for the class. This allows for an open discussion of questions related to CS 6820, visible to the instructor and the other students in the course. You will need to register as a student in the course by visiting https://piazza.com/cornell/fall2014/cs6820.

Academic Integrity

Any violation of academic integrity will be severely penalized. You are allowed to collaborate on the homework in small groups of 2-3 students. However, you are expected to understand the homework solution, and be able to explain it. Beyond your group, you should only discuss questions with other groups at a level of understanding the question. You may not use published papers not referenced from the course web page, or the Web to find your answer.

Cornell's Code of Academic Integrity may be found here: http://www.cuinfo.cornell.edu/Academic/AIC.html