CS681 Fall 04
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 Assistant Jeffrey Hartline jhartlin@cs.cornell.edu Upson 5154 254-5075 office

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

Time and Place

MWF 2:30-3:20, Upson 111

Office Hours

Dexter: by appointment.  Please contact Kelly.
Jeff: by appointment.  Please contact Jeff.

Sources

Textbooks

• D. C. Kozen.  The Design and Analysis of Algorithms.  Springer-Verlag, 1991.
• J. Kleinberg and E. Tardos.  Introduction 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, articles, homework sets, etc. 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 small groups.  If you collaborate, pass in 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.  Late homework will not be accepted without a good excuse.  Assignments and solutions will be posted on the web.  Submit assignments in class or to Kelly by 4pm on the due date.  Hardcopy only, please.

There will be two 72-hour takehome exams, open book and notes.  No collaboration is allowed on the exams.

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/8
HW2 9/20
HW3 10/1
Prelim - any 72-hour period from 10/4 to 4pm 10/15
Fall break 10/11-12
HW4 10/18
HW5 10/29
HW6 11/10
HW7 11/22
HW8 12/3

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 in the area of algorithms.  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)
• 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)