CMSC 452, SPRING 2012 HOMEPAGE

SYLL.pdf

HOMEWORKS

hw01.PDF,

hw01sol.PDF,

hw02.PDF,

hw02sol.PDF,

hw03.PDF,

hw03sol.PDF,

hw04.PDF,

hw04sol.PDF,

hw05.PDF,

hw05sol.PDF,

hw06.PDF,

hw06sol.PDF,

hw07.PDF,

hw08.PDF,

hw08sol.PDF,

hw09.PDF,

hw09sol.PDF,

hw10.PDF,

hw10sol.PDF,

hw11.PDF,

hw11sol.PDF,

hw12.PDF,

hw12sol.PDF,

PROJ.PDF,

MIDSAM.PDF, NOTE: This is last years midterm with one question removed that is on material we are not covering (PDA's).

MIDADVICE.PDF,

TSPMOVIE

HANDOUTS

1. FMLWS1S.PDF, This is a short writeup of just what WS1S Formulas are and the statement of their connection to regular languages.

2. FULLWS1S.PDF, This is a PhD thesis on the decidability of WS1S. You just need the first 20 pages which does the proof that WS1S is decidable. There are nice examples!

3. QFMLWS1S.PDF, This is a short writeup of just what WS1S Formulas are and the statement of their connection to regular languages, and the decidabilty of WS1S. This document subsumes fmlws1s.pdf

4. RIJK.PDF, This is a short writeup of how to convert a DFA into a regular expression. (If you were not in class the day I did this then GET THE NOTES FROM SOMEONE WHO WAS! These notes really don't help unless you have the really key picture that I drew!!!!)

5. CHOMSKY.PDF, Chomsky Normal Form and CFL are in P.

6. ARTICLE ON MY POLL ABOUT P VS NP

7. RIJKEX.PDF, AND RIJKDFA.PDF, The document RIJKDFA.PDF is a scanned in picture of a 3-state DFA, labeled 1,2,3. The document RIJKEX.PDF is an exposition of using the R(i,j,k) method on this DFA.

8. DEC.PDF, This is a document about Decidable sets and computable functions.

9. DR-SUESS-HALT.PDF

10. DEC2.PDF Notes on Turing Machines. As of April 12 we only covered sections 1.1 and 1.3.

11. TSPMOVIE Trailer for upcoming movie about P vs NP.

12. Turing wasn't just a Math guy, he was also a... See for yourself: TURING1 TURING2 TURING2

13. Poll on P vs NP pollpaper.pdf