CMSC 452: Elementary Theory of Computation

SPRING 2014 HOMEPAGE

The Syllabus is in two parts:

• Content of Course:
• Policy for the course:

HOMEWORKS

Homework 1

Homework 2

Homework 3

Homework 4

Homework 5

Homework 6

Project 1 (READ THIS NOW- DUE TUESDAY FEB 25)

Project 2 (READ THIS NOW- DUE TUESDAY MAR 4)

Homework 7

Homework 8

Homework 9

Homework 10

Homework 11

Project to possibly get a BUMP from F-->D or D-->C

HANDOUTS

1. ws1stalk.PDF, The talk on WS1S decidablility. (Still in progress.)
2. closure.PDF,
3. Primitive Recursive, Decidable, Undecidable, and Beyone,
4. Blog about History of Savitch's Theorem
5. Notes on Complexity Classes
6. Notes on P, NP
7. Peter Fontana's lectures:
   1. Notes
   2. Exercise
   3. Semantics
   4. More Exercise
   5. Figures
   6. Primitive Rec, Ackerman, Dec, Undec, and Beyond
   7. DR-SUESS-HALT.PDF
   8. Goodstein Sequence
   9. Kolmogorov Complexity
   10. SANE reduction 4col LE 3col