Assignments

Assignment 0, due March 31, 2005

All problems are from Sipser:

1. 1. Sipser 0.1 d,e,f
   2. 0.2 d,e,f
   3. 0.3 f
   4. 0.6 e
   5. 0.7
   6. 0.8

Assignment 1, due April 5, 2005

Sipser:

1. 1. 0.10
   2. 0.11
   3. 1.3
   4. 1.4g
   5. 1.5d
   6. 1.31
   7. 1.32

Assignment 2, due April 12, 2005

Sipser:

1. 1. 1.16 (b) [1.12(b) in 1st edition]
   2. 1.21(a) [1.16(a)]
   3. 1.46(a) [not in 1st edition]
   4. 1.51 [1.34]
   5. 1.52 [1.35] (Please answer in your own words; the 2nd edition contains a sample solution.)

Assignment 3, due April 21, 2005

Sipser 2nd edition [first edition]:

1. 2.2 [2.2]
2. 2.18 [2.17]
3. 2.30 a,d [2.18 a,d]
4. 2.35 [2.20]
5. 2.22 [2.26] Hint: Focus on how two strings can be different. Two strings can be different if they are different lengths, or if there is some corresponding position where they differ. Your solution only needs to find a single difference. I have seen understandable solutions that use either a PDA or a grammar to define the language. As a warm up problem it may be useful to find a description for w#x#y#z such that |w| = |y|.

Assignment 4, due April 28, 2005

Sipser 2nd edition [first edition] (I didn't have my first edition, so I just described the problem):

1. 3.6 [3.6]
2. 3.18 [3.16]
3. 4.6 (diagonalization, {0,1}^\omega is not countable)
4. 4.17 (C is Turing-recognizable if there is a decidable language D such that C = {x| \exists y . <x,y> \in D})
5. 4.18 (any two disjoint Turing-recognizable languages are separated by a decidable language)

Assignment 5, due Tuesday May 10, 2005

Sipser 2nd edition

1. 5.13 [5.13]
2. 5.28 [5.22] (Note: sample solution is given in 2nd edition; however collaboration policy applies!)
3. 5.29 [5.23]
4. 5.30 [not in 1st edition]

Assignment 6, due Thursday, May 19, 2005

Sipser 2nd edition [1st edition]

1. 7.14 [7.13] P closed under star.
2. 7.17 [7.17] Almost all of P is NP complete if P = NP
3. 7.24 [7.22] not-equal-CNF
4. 7.39 [7.32] Window size in Cook Levin proof

Special extra credit assignment, due Tuesday, May 24, 2005.

Post-mid term exercise available as pdf.

Assignment 7, due Thursday, June 2, 2005.

Exercise and notes are available as pdf. Sample solution can be found on the Fall term web page, but note that the collaboration policy applies.