Theory

Expect around 18 questions from this section

A. Automata and language theory (~ 6 questions)

  1. Models of computation (finite automata, pushdown automata, Turing machines)
  2. Formal languages (regular languages, context-free languages)
  3. Decidability

B. Design and analysis of algorithms and computational complexity (~ 6 questions)

  1. Exact or asymptotic analysis of the best, worst, or average case for the time and space complexity of specific algorithms
  2. Algorithmic design techniques (greedy, dynamic programming, divide and conquer)
  3. Upper and lower bounds on the complexity of specific problems
  4. NP-completeness

C. Correctness of programs (~ 6 questions)

  1. Formal specifications and assertions
  2. Verification techniques

humble servant

First Update Aug 22 2001

Last Update Aug 22 2001