Each portion will be divided into two parts of three questions each. Each part will take one class period. The two parts of the same portion will be administered in two consecutive class periods. You will be told the order in which the portions will be administered, but not anything about which topics will be covered in a given part of each portion.

For a closed-book exam like this, questions tend to have the form "show me that you know something about topic X" even if they aren't stated that way. So if a question asks about topic X, there are likely to be several ways you can earn credit, depending on the exact statement of the question. The question may ask you to trace or analyze an algorithm related to topic X, or state how topic X is related to some other topic, or state why topic X is important, or state how topic X is handled in one or more particular programming languages, etc. Naturally the more of the specific questions you can answer, the more credit you will get. Many of the old comprehensive exam questions (links below) are good examples of how this might work.

Notes for each of the three portions of the exam are given below. Additional notes and clarifications may be added as the course proceeds. In particular, the notes for the Hopcroft text are for the second edition, and will be changed to reflect the third edition.

Programming language principles reference: Michael L. Scott, Programming Language Pragmatics, Morgan Kaufmann, 2nd edition, Chapters 1 - 11 and 14

You're responsible for the sections in the listed chapter that appear on the associated CD-ROM, except as noted below. You're not responsible for the LeBlanc-Cook symbol table of Section 3.4. In Section 4.5, you're not responsible for the details of the long example (although it's good to understand this example just like it's good to understand any example).

You needn't understand the details of Exercises 3.15 & 3.29, or know why they represent exceptions to the claim at the end of p. 133. You should know that the do represent exceptions to that claim.

Formal languages and theory of computation reference: Hopcroft, Motwani and Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd edition, Addison-Wesley.

You aren't responsible for the details of the DFA minimization algorithm -- not all the details are given in the text. You aren't responsible for the algorithm that takes a DFA and constructs an equivalent regular expression. You should know what each of these algorithms does and why they are important.

You are not responsible for counter machines in Chapter 8. You're not responsible for the details of the proof of Theorem 10.9 (Cook's Theorem), although you should understand the basic idea. You're not responsible for the proof of Theorem 10.13.

Analysis of algorithms reference: Thomas H. Cormen et al., Introduction to Algorithms, 2nd ed., MIT Press, Chapters 15 - 30

The starred sections will not be covered.

Links to previous exams