CS681 Fall 04
Design and Analysis of Algorithms
Course Information



Dexter Kozen
Upson 5143
255-9209 office
257-4579 home
592-2437 cell

Teaching Assistant

Jeffrey Hartline
Upson 5154
254-5075 office


Kelly Patwell
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.



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


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


Familiarity with the content of CS481 and CS482 is assumed.  In particular, we will assume knowledge of:

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.