This page contains corrections but also clarifications, answers to questions I've been asked, etc. Actual corrections are marked with a

Problem 1

In problem 1 A, the argument to the fourth and fifth procedures is misnamed.

• It should read:

  dequeue Q: returns a queue containing...

  front Q: returns....

In problem 1 C, the obvious substitions of "stack" for queue should occur:

• It should read:

  stack-empty? stack: returns boolean true if stack is empty, false otherwise

In problem 1 D, you may use any programming language I'm likely to know or to be able to infer meaning from OR any reasonable pseudocode notation. The problem is asking you to provide an implementation that does not use any cons cells, arrays, or other structures except smoke and mirrors. You may do anything that you want with smoke and mirrors (provided it's in their contract, of course) in order to provide implementations of the necessary operations.

Problem 2

For each of part A and B, the correct answer is a regular expression that matches a string if and only if the English description describes that string, i.e., it matches all strings that the English description describes and no strings that the English description excludes.

For part D, the rules of the FSM are exactly the rules that we have been using in class. In particular, omitted transitions are assumed to be failing transitions.

Problem 3

The set data type described here is intended to behave exactly as mathematical sets do. In particular, both procedures in part B are technically correct; they simply represent alternative approaches.

On p. 9, final line, the word "proc" is incorrect; it should be "tst"

Problem 4

The final line of the first paragraph-like thing should read:

• "so that xyⁱz ... for all values of i"

i.e., all appearances of n on that line should be replaced by a new variable.

Problem 5 (optional)

On line 8, "all-with-first" is incorrect. It should read "all-but-first"

Also, you may assume either definition of set-insert, but please indicate what assumption you're making.