CMSC 452: Elementary Theory of Computation

SPRING 2013 HOMEPAGE

REVIEW FOR THE FINAL: REVIEWFORTHEFINAL:

DR-SUESS-HALT.PDF

The Syllabus is in two parts:

• Content of Course:
• Policy for the course:
• Travelling Salesman Movie Info: Advice: See the trailor
• BOB
• Pictures of the proof of Cook's theorem Picture1.jpg Picture2.jpg
• More pictures of the proof of Cook's theorem: (From April 16, having to do with the HW.) Picture3.jpg Picture4.jpg Picture5.jpg

HOMEWORKS

hw01.PDF,

hw01sol.PDF,

hw02.PDF,

hw02sol.PDF,

hw03.PDF,

hw04.PDF,

hw04sol.PDF,

hw05.PDF,

hw05sol.PDF,

hw06.PDF,

reviewmid.PDF,

hw07.PDF,

PROJECT.PDF,

hw08.PDF,

hw09.PDF,

hw10.PDF,

hw11.PDF,

hw12.PDF,

HANDOUTS

1. ws1stalk.PDF, The talk on WS1S decidablility (Feb 12 lecture.)
2. cfgtalk.PDF, CFG's
3. nonreg.PDF, The talk on some sets being not reg.
4. A 17,826 word... word.PDF
5. That grammar that generates equal number of a's and b's: ab.PDF
6. Chomsky Normal Form notes: chomsky.PDF Chomsky Normal Form talk: chtalk.PDF
7. Talk on Ind set and Misc: istalk.PDF
8. Talk on Grid Problem gridnptalk.PDF