Guidelines

It is very important to stay current in this class and these assignments are selected to help you do so. This is where the pain and suffering occur.

Communicating clearly and concisely what you have to say is an important skill you will use throughout your career. All assignments are to be neat and professional. If you cannot clearly communicate something, there is a good chance that you do not yet understand it well.

Assignments will be graded on accuracy, completeness and clarity. Good writing, grammar, punctuation, etc. are extremely important because of the great effect they have on the impact of your work.

Assignment

Chapter

Problems
1 0 1,2,3,4,5,6,7
2 0 8,9,10,11
3 1 1,2,3
4 1 6
5 1 7
6 1 8,9,10,16
7 1 18,20
8 1 19,21
9 1 29,30,53
10 2 3,4
11 2 1,8,14,27
12 2 5*
13 2 11,26
14 2 22,30
15 3 1,2,5,7
16 3 8**,10,11
17 3 15,16,22***
18 4 1,2,3,4,9
19 4 5,6,7,11
20 4 16,22,28
21 5 1,24
22 5 13,14,15
23 5 3,17,18
24 5 4,9
25 5 30****, plus invent an undecidable language and prove by reduction that it is undecidable
26 7 1,2
27 7 26*****
28 7 3,4,8,9
29 7 5,11
30 7 17,20
31 7 36,39
32 7 27
33 10 11
34 10 2,15


*Just state diagrams will be sufficient -- you do not need to give informal descriptions.

**See p. 157 for a definition of "implementation-level description".

***The first edition had a much better version of this problem (based on the existence of God).

****Do not appeal to Rice's Theorem (as does the answer in the book), rather prove these by reduction.

*****Produce an algorithm to solve the problem and analyze its complexity.