CSC527: Theory of Computation
Spring 2012 Homework Problems

Here are the homework problem sets.

  1. Homework Problem Set No.1
    Due date: Wednesday, January 25
  2. Homework Problem Set No.2
    Due date: Wednesday, February 1
    Problems 1.4(e), 1.4(f), 1.4(g) (5 points each); Problems 1.5(g), 1.7(b), 1.7(c) (10 points each); Problems 1.31, 1.33, 1.34 (15 points each).
  3. Homework Problem Set No.3
    Due date: Wednesday, February 8
    Problems 1.12 (10 points), 1.16(a) (10 points), 1.20(g) (5 points), 1.21(a) (10 points), 1.35 (15 points), 1.40(b) (10 points), 1.46(d) (15 points), and 1.51 (10 points).
  4. Homework Problem Set No.4
    Due date: Wednesday, February 22
  5. Homework Problem Set No.5
    Due date: Wednesday, February 29
    Problems 2.15, 2.30(a), 2.30(d), 2.31, 2.32, 2.39, 2.43(b), and 2.44. All problems are worth 10 points.
  6. Homework Problem Set No.6
    Due date: Wednesday, March 21
    Problems 3.8(b), 3.9(a), 3.9(b) (these problems are worth 20 points each), 3.15(b) and 3.15(c) (15 points each), and 3.15(d) (10 points).
  7. Homework Problem Set No.7
    Due date: Wednesday, March 28
    Problems 4.3, 4.10, 4.15, 4.17, 4.18, 4.19, and 4.24. Each problem is worth 10 points.
  8. Homework Problem Set No.8
    Due date: Wednesday, April 11
    Problems 5.1, 5.2, 5.4, 5.9, 5.14, 5.22, 5.23, and 5.25. Each problem is worth 10 points.
  9. Homework Problem Set No.9
    Due date: Wednesday, April 18
    Problems 7.1 (a), (b), (d), and (f) (4 points each); 7.2 (a), (b), (e), and (f) (4 points each) 7.6, 7.9, 7.11, 7.17, and 7.20(a) (15 points each)