CS 46 Midterm exam on Wednesday, 4 Mar. in class covering material through pp. 227. It will be closed book, no notes.

Due: Wednesday, Feb. 25

Five problems, no choice this week.

1. Write solutions to: 4.1.1, 4.1.4 (hint: it makes a difference if n is even or odd), 4.1.10, 4.1.k (below), 4.3.3.

   Call this problem 4.1.k: Example 4.1.9 on page 190 of my text claims to be a right-shifting machine. It is not! (in my printing. There is a remote chance that you have a later printing with it fixed.) So, copy the machine given in your printing of the text onto your answer sheet. Trace it on input aab. What does it do in general? If your version is not a correct right-shifting machine, fix it. That is, give a diagram in the style of figure 4-9 that is a correct right-shifting machine. If your version is a correct right-shifting machine, construct a left-shifting machine that simply thows away the leftmost character of a non-empty input w.