CS681 Fall 07
Design and Analysis of Algorithms
Course Information


Staff

Instructor

Dexter Kozen
kozen@cs.cornell.edu
Upson 5143
255-9209 office
257-4579 home
592-2437 cell

Teaching Assistants

Yin Wang
yinwang@cs.cornell.edu
Georgios Piliouras
gpil@cs.cornell.edu

Administrator

Kelly Patwell
patwell@cs.cornell.edu
Upson 5147
255-7790 office


Time and Place

MWF 2:30-3:20, Hollister 110


Office Hours

Dexter: Thursday 1-2:30 or by appointment.  Please contact Kelly for appointments.


Course Administration

Newsgroup

We have a course newsgroup, cornell.class.cs681.  All course announcements will be posted there; please check daily for new announcements.  You may also use the newsgroup for technical discussions, posting general questions about the homework, etc.  The course staff will try to respond to questions in a timely manner, or if you know the answer, feel free to post it yourself.  Please avoid giving away any hints on the homework though.

CMS

We are using the course management system CMS.  Kelly has entered everyone who preregistered, but if you did not preregister, you are probably missing.  Please login and check whether you exist.  There will be a list of courses you are registered for, and Com S 681 should be one of them.  If not, please send your full name and Cornell netid to Kelly so she can register you.  You can check your grades and submit homework in CMS.  There is a help page with instructions.


Sources

Textbooks (recommended, not required)

  • D. C. Kozen.  The Design and Analysis of Algorithms.  Springer-Verlag, 1991.
  • J. Kleinberg and E. TardosIntroduction to Analysis of Algorithms.  Addison-Wesley, 2005.
  • M. R. Garey and D. S. Johnson.  Computers and Intractibility: A Guide to the Theory of NP-Completeness.  W.H. Freeman, New York, 1979.

These titles are on reserve in the Engineering library, Carpenter Hall.

Handouts

All handouts other than homework and exams will be available on the web in pdf or html format.  It is your responsibility to check often for new postings.  For viewing pdf files, we recommend Adobe Reader, available free of charge.


Homework and Exams

There will be biweekly homework sets consisting of 3-5 problems, due by 4pm on the due date.  You may collaborate on the homework in groups of 2 or 3.  If you collaborate, submit one copy of your solutions with the names of all collaborators.  Acknowledge all sources, including others in the class from whom you obtained ideas.  Please type or write legibly and staple.  There will be a point deduction of 10% per day for unexcused late homework.  Assignments and solutions will be posted in CMS.  Solutions are typically posted 4 or 5 days after the due date at which time no late submissions will be accepted.  Submit hardcopy in class or to Kelly by 4pm on the due date, or a .pdf, .ps, .doc, or .txt file in CMS.  Do not submit Latex source.

There will be two 72-hour takehome exams, open book and notes.  No collaboration is allowed on the exams.  Sign out the exam with Kelly Patwell in 5147 Upson.  Return the completed exam to Kelly within 72 hours after signing it out (she must be there to record the time, do not just slip it under the door), or submit it via CMS.  If you wish to submit your exam during non-business hours, you must submit it via CMS.

Graded homework and exams will be passed back in class, otherwise old homework and exams will be available from Kelly.

Approximate weights: Homework 50%, exams 25% each.

Due dates (subject to change):
HW1 9/5
HW2 9/17
HW3 9/28
Prelim - any 72-hour period from 10/1 to 4pm 10/15.  If choosing to work over fall-break, test must be picked up before fall-break begins and submitted via CMS.  Special arrangements will be made for those wishing to observe religious holidays.  Please let us know in advance.
Fall break 10/6-9
HW4 10/17
HW5 10/29
HW6 11/12
HW7 11/30
Final exam - any 72-hour period from 12/3 to 4pm 12/14.

Regarding the homework:

  1. We encourage you to work in small groups.  It is more fun for you because you have others to bounce ideas off and you learn more, and it is more fun for us because there is less to grade.
  2. You do not have to form CMS groups to work in groups.  Only one person in a group needs to submit the homework.  We will transfer the grades to the collaborators.
  3. The preferred interpretation of collaboration on the homework is not "Dick does problem 1 and Jane does problem 2," but rather "Dick and Jane do problem 1 and Dick and Jane do problem 2."
  4. Whenever you give an algorithm, always give a correctness proof.  Super formal proofs are not necessary, a good convincing argument will do.
  5. Give an analysis of the complexity of your algorithm if that is the point of the question.  Again, there is no need to be overly formal.
  6. Please keep your solutions short and to the point.  Brevity is the soul of good computer science.
  7. If you submit hardcopy, staple!
  8. You are encouraged to type solutions. If you write by hand, please write neatly and legibly.
  9. Your proofs should be crystal clear.  We should not have to figure out why or how leaps of logic are true, even if they are.  If you do not understand a step, it is better to be honest than to try to fake your way through.  Use figures if they help the exposition.  Avoid pseudo-code--a high-level explanation of an algorithm is better.  If you must use pseudo-code, comment liberally.

Prerequisites

Familiarity with the content of CS481 and CS482 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
  • NP-completeness and polynomial-time reducibility.

Approximate Syllabus

The course is organized around a few fundamental themes.  The exact coverage is subject to change.  Topics below will be covered as time permits; we will probably not have time to cover everything.

  • Greedy algorithms: spanning trees, Steiner trees, matroids, arborescences, and multicast cost-sharing. (Kozen Lec 1-2, Kleinberg-Tardos Ch 4)
  • Advanced data structures: advanced heaps, self-organizing data-structures. (Kozen 8-13)
  • Network flows: maximum flows and minimum cuts, the preflow-push algorithm, minimum-cost flows, multicommodity flows, and applications to matching, scheduling, network routing and vision. (Kleinberg-Tardos Ch 7, Kozen Lec 14, 16-20)
  • Dynamic programming: basic dynamic programming technique, dynamic programming on trees, tree decomposition, and algorithms for graphs with bounded tree width. (Kleinberg-Tardos Ch 5)
  • NP-completeness (Kozen Lec 21-25, Garey and Johnson, Kleinberg-Tardos Ch 8)
  • Approximation algorithms: greedy algorithms, local search, on-line algorithms, primal-dual algorithms, linear programming. (Kleinberg-Tardos Ch 11)
  • Randomized algorithms: basic techniques from discrete probability, and applications to optimization, distributed computation, and packet routing. (Kleinberg-Tardos Ch 13)
  • Lower bounds for constant depth circuits: random partial valuations, Haastad switching lemma (Handout)
  • Algorithms in algebra and number theory: Integer arithmetic, Csanky's algorithm, Chistov's algorithm, matrix rank, linear equations and polynomial gcds, FFT, Luby's algorithm, primality testing (Kozen Lec 30-40)