Qualifying Examination Syllabus - Foundations
            (Computer Science Department  October 2003)

Notice

--------------------------------------------------------------
The syllabus may, and probably will, change in the future.  Be
sure you are studying from the correct syllabus, not from an
obsolete one.
--------------------------------------------------------------

Major Texts:  

D.-Z. Du and K.-I. Ko, PROBLEM SOLVING IN AUTOMATA, LANGUAGES,
  AND COMPLEXITY. John Wiley and Sons, 2001.

M. Sipser, INTRODUCTION TO THE THEORY IF COMPUTATION, PWS, 1997

J. Savage, MODELS OF COMPUTATION: EXPLOEING THE POWER OF COMPUTING. 
  Addison Wesley, 1998 (Reprinted with corrections, Feb 2000).

J. Hopcroft, R. Motwani, and J. Ullman, INTRODUCTION TO AUTOMATA
  THEORY, LANGUAGES, AND COMPUTATION. Second edition, Addison-Wesley,
  2001.

Other References:
 
H. Lewis and C. Papadimitriou, ELEMENTS OF THE
  THEORY OF COMPUTATION, 2nd edition, Prentice-Hall, 2000.

R. Floyd and R. Beigel, THE LANGUAGE OF MACHINES, Computer Science
  Press, 1994.

J. Martin, INTRODUCTION TO LANGUAGES AND THE THEORY OF
  COMPUTATION, McGraw-Hill, 1991.

Topics:

1.  Computation Models without Memory
    a.  Straight-line programs and Circuits
    b.  Normal-form expansions of Boolean functions
    c.  Reductions between functions
    d.  Specialized Circuits
    e.  Prefix Computations
    f.  Complex Boolean functions

2.  Computational Models with Memory
    a.  Finite-State Machines (FSM)
    b.  Sequencial circuits for FSM
    c.  Random-access machines
    d.  Turing machines
    e.  Design of a simple CPU

3.  Formal Languages  
    a.  Closure properties and finite representation of languages
    b.  Types 0 to 3 languages and left-linear grammars,
        context-free grammars, context-sensitive grammars, and
        unrestricted grammars
 
4.  Regular Languages 
    a.  Characterization: regular expressions, regular grammars,
        and deterministic and nondeterministic finite automata
    b.  Automata construction
    c.  Closure and algorithmic properties
    d.  Myhill-Nerode Theorem and state minimization
    e.  Pumping lemma of regular languages

5.  Context-Free Languages
    a.  Context-free grammars, derivations, parse trees, ambiguity
    b.  Context-free grammars vs (nondeterministic) pushdown automata
    c.  Closure and algorithmic properties
    d.  The pumping lemma of context-free languages
    e.  Deterministic context-free languages and parsing

6.  Computabiltiy
    a.  Characterization: Deterministic and nondeterministic 
        Turing machines
    b.	Variants of Turing machines (k-tape, two-way infinite tape, 
	etc.) and their equivalence proofs
    c.  Unrestricted grammars
    d.	Universal Turing Machines
    e.  Decidability and recursive and recursively enumerable sets
    f.	Primitive recursive functions, recursive functions, and 
	partial recursive functions

7.  Undecidability
    a.  Halting Problem
    b.  Uncomputable Functions and Undecidable problems
    c.  Reducibility
    d.	Tiling problem and Post Correspondence Problem
    f.  Rice Theorem

8.  Computational Complexity
    a. Complexity classes, time and space hirarchies
    b. Polynomial-time reductions and NP-completeness
    c. NP-complete problems