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,8,9
2 1 3,6
3 1 7a
4 1 8,9,10,16
5 1 18,20
6 1 19,21
7 1 29,30,53
8 Additional Reading 1 Exercises 1.1, 1.2
9 Additional Reading 2 Exercises 2.1
10 2 3,4
11 2 1,8,14,27
12 2 5b
13 2 11,26
14 2 22,30
15 3 1,2,5,7
16 3 8c,10,11
17 3 15,16a-d,22d
18 4 1,2,3,4,10
19 4 6,7,8,12
20 4 5,24,30
21 5 1,24
22 5 30e, plus invent an undecidable language and prove by reduction that it is undecidable
23 5 3,17,18
24 5 4,9
25 7 1,2,28f
26 7 3,4,8,9
27 7 5,12
28 7 18,21g
29 7 38,41
30 7 29
31 Additional Reading 3 Exercises 3.1, 3.2
32 Additional Reading 4 Exercise 4.1


a For parts e and f, if you are not yet familiar with regular expressions, the '*' superscript means "0 or more copies of" and the '+' superscript means "1 or more copies of".

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

c See p. 185 for a definition of "implementation-level description".

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

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

f Don't prove NP-Completeness. Instead, produce an algorithm to solve the problem and analyze its complexity.

g Recall from your reading that UHAMPATH is NP-Complete.



Homework numbering mapping from 2nd edition

The mapping is represented as 2e -> 3e, so, for example 0.11 in the second edition is 0.12 in the third

0.11 is a new problem
the old 0.11 -> 0.12

4.5 is a new problem
4.5-4.7 -> 4.6-4.8
4.9 -> 4.10
4.11 -> 4.12
4.22 -> 4.24
4.28 -> 4.30

7.11 -> 7.12
7.17 -> 7.18
7.20 -> 7.21
7.26 -> 7.28
7.27 -> 7.29
7.36 -> 7.38
7.39 -> 7.41