The material you need to know is listed on:

1. The midterm study aid
2. The final exam study aid.
3. Notes on NP-completeness.

Old final Exams (2003 and earlier)

The notation rho(M) has been replaced by "M". The notation rho(w) has been replaced by "w". We encoded Turing machines using these symbols:
q a 0 1 , ( )
whereas the old text encoded them in unary using I and c.

1. Fall 2011: (11.pdf, 12 pages).
2. Fall 2010: (f10.pdf, 12 pages).
3. Summer 2010: (k10.pdf, 12 pages).
4. Fall 2009: (09.pdf, 11 pages).
   For Question 3 on page 4 of this exam, the parse tree is:
   
   For Question 4 on page 5 of this exam, the machine schema are:
   
   
5. Summer 2008: (08.pdf, 11 pages).
6. Fall 2007 purposely omitted (different text and definitions).
7. Summer 2003: (03.pdf, 11 pages).
8. Summer 2002: (02.pdf, 11 pages).
9. Summer 2001: (01.pdf, 11 pages).
10. Fall 1998: (98.pdf, 11 pages).
11. Fall 1997: (97.pdf, 4 pages).
12. Fall 1996: (96.pdf, 4 pages).
13. Fall 1993: (93.pdf, 3 pages).

Return to Home page for CSC 320.