Theory Syllabus 1999

Syllabus for Theory Qualifier
October, 1999

The material is drawn from the sources indicated and is covered in CS410, CS481, CS482, and CS681. Where more than one reference is given, you need only consult one. Though you will not be asked to recite proofs or algorithms given in the texts, you will need to be well-versed in the concepts and techniques used to construct these results in order to solve the exam problems.
  1. Formal languages and automata: [K2, §3-16, 19-27] or [HU, §2-6, 9]
    • finite automata and regular expressions
    • properties of regular sets
    • context free grammars
    • pushdown automata
    • properties of context free languages
  2. Computability and undecidability: [K2, §28-34] or [HU, §7, 8]
    • Turing machines
    • undecidability
  3. Complexity, completeness and reducibility
    • NP-completeness: [K1, §21-25] or [GJ, §1-5] or [CLR, §36]
    • completeness for other classes: [HU, §12.1, 13.4-5]
  4. Elementary data structures: [CLR, §11-14]
    • linked lists
    • hashing
    • some variant of binary search trees, such as red-black trees or 2-3 trees, with good worst-case guarantees
  5. Design and analysis of algorithms
    • complexity of algorithms: [K1, §1] or [CLR, §1,2]
    • sorting: [CLR, §7-10]
    • spanning trees: [K1, §2] or [CLR, §24]
    • searching of graphs: [K1, §2,4] or [CLR, §23]
    • shortest paths: [K1, §5] or [CLR, §25.1-3,26.1]
    • Floyd-Warshall algorithm: [CLR, §26.2]
    • dynamic programming: [CLR, §16]
    • union-find: [K1, §11] or [CLR, §22]
    • max flow and matching: [K1, §16,18.3] or [CLR, §27.1-3]
    • fast Fourier transform: [K1, §35] or [CLR, §32]
    • elementary number theoretic algorithms and RSA cryptography: [CLR, §33.1-3, 7-8]

References

[CLR]
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. McGraw-Hill, 1990.
[GJ]
M. Garey and D. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
[HU]
J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
[K1]
D. Kozen. The Design and Analysis of Algorithms. Springer-Verlag, 1991.
[K2]
D. Kozen. Automata and Computability. Springer-Verlag, 1997.