CSC 653: Advanced Theory of Computing

A printable PDF is available.

Assignment 3: Due Tuesday, September 30

Exercises and problems from Chapter 3:

  1. Exercise 3.2, parts b-e
  2. Exercise 3.4
  3. Exercise 3.6
  4. Problem 3.9
  5. Problem 3.11

Exercises and problems from Chapter 4:

  1. Exercise 4.2
  2. Exercise 4.4
  3. Exercise 4.7
  4. Problem 4.10
  5. Problem 4.12

The following two problems are "challenge problems" -- you are not required to do them, but if you get good solutions to them you will receive extra credit (up to 10 points each).

  1. Problems 3.18
  2. Problem 3.19