Typos in Washburn, Marlowe, and Ryan

Ritter and IST 230 classes, Autumn 2000.

Last update 12 Dec. 2000

Mistakes caught are worth 0.1 points

p. 15. in the inductive step, has '(n-k+1)' instead of '(n-k+1)!'

also is missing () around a term

p. 27/p. A5. Answers to questions 25 and 27 are incorrect. They should be (1 0 1 0 1 0) and (0 0 1 1 1 0 0), respectively.

p. 42. Figure 1.21 the lowest level has too many nodes (Fib would be 8). Based on Definition 1.5.4, there is an extra node, and it's the next to last one on the right. [Also, this suggests that the answer to #19 is wrong in answer keys.]

p. 60, problem #1. The better answer (or best answer?) is for 4 = 7*28 - 3*64. The answer in the back is less correct and not found with the algorithm taught in the book and in the class. This mistake also appears in the Student Solutions manual.

p. 121. the trail in figure 4.5 has an extra arrow on the top line, or, perhaps just needs clarification that it can be in either direction but not both.

p. 136. Hamiltonian is mispelt in paragraph 2!

p. 150 and related pages. Depth first is either misdefined or the trees are miscomputed. A revised p. 150 is available here. This was first reported by Purvi and Laura, but also others.

p. 154, section 4.3, problem #17. Under the definition taught in lecture and commonly used as depth first, the answer in the back of the book is wrong. According to the book's definition/algorithm for doing a depth first tree (p. 149), it may be correct but the algorithm is not clear enough that I would hold you to it.

Brook Nale pointed out the opposite view clearly, which I include here.

The answer in the back is incorrect. The answer is on page A25. The breadth first spanning tree is correct, but the depth first one is wrong. They have this:

``` /_
/ /_

But the answer should be this:
/_
_/_

I have the steps written out below.

Brook
-------- Original Message --------
Date: Wed, 01 Nov 2000 23:52:26 -0500
From: Brook Nale
To: drm1@psu.edu

Dr. Mudgett,

Nevermind about that last e-mail, I think I pretty much understand
things now.  Is the answer in the back of the book wrong for pg 154, #17
for depth first transversal?  Would the correct steps be:
a.)  1 to 2
b.)  2 to 3
c.)  3 to 5
d.)  5 to 4
e.)  backtracking... 5 to 6

Somehow the book is getting a path from 2 to 4, but I don't understand
how that is possible.  Thanks, and totally ignore the last email, I was
looking at the problems totally in the wrong way.
Brook```

p. 188. The advanced exercises are difficult if not impossible to do without additional material. Some further comments were posted, but even with these notes in hand, the problems are too hard and exampls are not in the solutions manuals. The grader also balked when asked to derive a solution.

p. 193. x = x + 0 by axiom 2 (not 1 as in book)

p. 193. x = x(1) by axiom 2 (not 1 as in book)

p. 211. The AND blocks in the lower figure are not lableled as AND blocks. Clearly not a major problem. Maybe even intentional.

p. 270. #9 a min. path problem. The answer on p. A38 is 2-5-6-5-3-4 [=25]. The answer put forward by Kaplan and Murphy of 2-15-3-4 [=24], is by inspection, because it is less and a path, the correct answer.

p. 271. #13. minimal cut problem. The answer on p. A38 is 11. The answer put forward by Kaplan and Murphy of 9 (6 & 3), is by inspection, because it is less and it is a full cut, the correct answer.

p. 276 under Theorem 8.3.1, in the proof section, 'absolute' is spelled 'asolute'. Weiss, Gullbergh, Keenan, Lewczyk, Garretson

p.279. for problems 16-19, it should be "takes 2^k operations" (not 2^k seconds)
found by Ruiz and Kaplan

p. 285, Example 1. Starting index should be 'n', not 'k' (from McGlinchey, added 30/9/00)

p. 332 example 8, it says "...the productions are s :: a". This should be "s ::= a". Weiss, Gullbergh, Keenan, Lewczyk, Garretson

p. 333, theorum 10.1.1 'follwing' should be 'following'

p. 347, # 9. A Finite state machine problem. The answer in the back of the book will accept any number of aa's and any number of bbb's. This is wrong, it should be any number of aa's OR any number of bbb's. The answer in the hwk 14 soln set is a good example of such a machine for a similar language.

The same problem is seen in problems #5 and #7, where the question is for (a* + b*) and the machine put forward as the answer on p. A41 actually accepts (a + b)* . The solution manual appears to be correct in this area, however. Ramey & Leonard both found these.