Table of Contents

I. Software Systems and Methodology – 40%
 A. Data organization
  1. Data types
  2. Data structures and implementation techniques
 B. Program control and structure
  1. Iteration and recursion
  2. Procedures, functions, methods, and exception handlers
 C. Programming languages and notation
 D. Software engineering
II. Computer Organization and Architecture – 15%
 A. Digital logic design
 C. Memories and their hierarchies
 D. Networking and communications
III. Theory and Mathematical Background – 40%
 A. Algorithms and complexity
  1. Exact and asymptotic analysis of specific algorithms
  2. Algorithmic design techniques
  4. Computational complexity, including NP-completeness
 B. Automata and language theory
  1. Models of computation (finite automata, Turing machines)
  2. Formal languages and grammars (regular and context free)
  3. Decidability
 C. Discrete structures
  1. Mathematical logic
   a. Definition
   d. Boolean operators
  2. Elementary combinatorics and graph theory
  3. Discrete probability, recurrence relations, and number theory
   a. Definition
   i. Matrices
IV. Other Topics – 5%
Appendix
Further study
Greek letters
Mathematics

Study guide organization

I have organized the information using the topics listed on the insert dated July 2003 that comes with the test registration booklet. The website lists slightly different topics. I refer to the practice test and its instructions on multiple occasions. I highly encourage you to have a copy of the practice test available.

A few topics that do not fit into this hierarchy are appended (e.g. Greek letters).

Bolded items are in place to allow you to skim the study guide. I have not had time to bold everything that I think is important.

Some topics are presented in a less than ideal order. For example, we talk about NP-completeness and reference Turing machines before we explain what a Turing machine is. I do not cross-reference the sections.

⇒ Next section