Sept. 28, 2004
                    Theory Preliminary Exam

The Ph.D. Preliminary Exam in Theory will be held Friday October 15 -
Friday October 22, 2004. The examination committee consists of Hal
Gabow (chair) and Andrzej Ehrenfeucht. The exam will be take-home, open
book.

There will be a meeting to answer questions about the exam on Wednesday
September 29, 4:00 - 4:30 PM in room 831. Exams will be
available at 1:30 p.m., Friday October 15 from Vicki in EC-OT 720;
completed exams must be returned to Vicki by 1:30 p.m., October 22.  Each
student will be given an identifying number and exams will be graded
anonymously. Grades will be posted during the next week. Oral examinations
may be scheduled that week to give students the opportunity to elaborate
on answers; this will *only* be done in rare cases where clarification of
answers is necessary.

During the exam, students may address questions to the exam committee
by email; the committee's answers will be posted by email to all
students taking the exam. No other discussion of the exam is allowed
until the grades are posted, which will be after any oral exams.

The exam will consist of problems drawn from the areas of formal
languages and automata, computability and complexity, and design and
analysis of algorithms (not necessarily all of these). The questions
will be based on material normally covered in CSCI 5444 and 5454.
References germane to this material are:

  Introduction to Algorithms 
    by Cormen, Leiserson, Rivest & Stein

  Algorithms (2nd edition) 
    by Sedgewick

  Introduction to Automata Theory, Languages and Computation 
    by Hopcroft & Ullman

  Elements of the Theory of Computation 
    by Lewis & Papadimitriou

Parts of problems will allow the student to show understanding of basic
concepts; in other parts the student will apply the material in original
ways.  The level of difficulty will be roughly equivalent to any of the
following: the harder starred problems in Cormen, Leiserson, Rivest &
Stein; the harder unstarred problems in Hopcroft & Ullman, or Lewis &
Papadimitriou; the more difficult homework problems in CSCI 5444 or CSCI
5454. Exams from previous years are available from Vicki.

Prior to taking the exam, students must have written approval of their
advisor. Register for the exam with Vicki by Thursday September 30. If
registered you will receive a grade for the exam unless you withdraw by
Thursday September 30.