|
Computer
Science Department |
Introduction to the Theory of Computing
CS 381 - Spring 2008
| Date | Topic | Slide set1 | Assignments | |
|---|---|---|---|---|
| 1. | 2/5/08 | Course overview; Languages (Ch. 1 & 2) | syllabus slides1.pdf |
a1.pdf |
| 2. | 2/7/08 | Recursive set definitions; regular expressions (Ch. 3 & 4) | slides2.pdf | |
| 3. | 2/12/08 | Finite automata (Ch. 5) | slides3.pdf |
a2.pdf |
| 4. | 2/14/08 | Transition graphs (Ch. 6) | slides4.pdf | |
| 5. | 2/19/08 | Kleene's theorem (Ch. 7) | no new slides | |
| 6. | 2/21/08 | Properties of regular languages (Ch. 9) | slides5.pdf | a3.pdf |
| 7. | 2/26/08 | Pumping lemma for regular languages (Ch. 10) | no new slides | |
| 8. | 2/28/08 | Regular languages and decidability (ch. 11) | slides6.pdf |
a4.pdf |
| 9. | 3/4/08 | Context-free grammars, parsing, ambiguity (Chap. 12) | no new slides | |
| 10. | 3/6/08 | Regular grammars; CFGs in Chomsky Normal Form (Ch. 13) | slides7.pdf |
a5.pdf |
| 11. | 3/11/08 | PDAs (Ch. 14) | no new slides |
|
3/12/08 - First exam - 5:00PM |
||||
| 12. | 3/13/08 | CFG versus PDA (Ch. 15) | slides8.pdf | |
| 13. | 3/18/08 | Pumping lemma for context-free languages (Ch. 16) | no new slides |
a6.pdf |
| 14. | 3/20/08 | Properties of context-free languages (Ch. 17) | slides9.pdf |
|
SPRING BREAK |
||||
| 15. | 4/1/08 | Decidability for context-free languages(Ch. 18) | no new slides |
|
| 16. | 4/3/08 | Turing machines (Ch. 19) | slides10.pdf | a7.pdf |
| 17. | 4/8/08 | nPDAs, Post machines, Minsky's theorem (Ch. 20 & 21) | slides11.pdf |
|
4/9/08 - Second exam - 5:00PM |
||||
| 18. | 4/10/08 | TM variations (Ch. 22) | slides12.pdf | |
| 19. | 4/15/08 | Recursively enumerable languages (Ch. 23) | slides13.pdf | a8.pdf |
| 20. | 4/17/08 | The halting problem and related problems (Ch. 23, continued) | no new slides | |
| 21. | 4/22/08 | Chomsky hierarchy of languages (Ch. 24) | slides14.pdf | |
| 22. | 4/24/08 | Church's thesis (Ch. 25) | slides15.pdf | |
| 23. | 4/29/08 | review of big-O notation; polynomial-time TM simulations | no new slides | a9.pdf |
| 24. | 5/1/08 | Introduction to computational complexity theory; reasonable encodings; the time complexity class P | no new slides | |
| 25. | 5/6/08 | The complexity classes NP and co-NP; the SAT problem | ||
| 26. | 5/8/08 | Sample NP-complete problems | ||
| 27. | 5/13/08 | Q&A | ||
5/14/08 - Third exam - 5:00PM |
||||