|
Computer
Science Department |
Introduction to the Theory of Computing
CS 381 - Fall 2009
| Date | Topic | Handouts | Assignments | |
|---|---|---|---|---|
| 1. | 9/10/09 | Course overview; Languages (Ch. 1 & 2) | syllabus Slide set #1 | Assignment 1 |
| 2. | 9/15/09 | Recursive set definitions; regular expressions (Ch. 3 & 4) | Slide set #2 | |
| 3. | 9/17/09 | Finite automata (Ch. 5) | Slide set #3 | Assignment 2 |
| 4. | 9/22/09 | Transition graphs and Kleene's theorem (Ch. 6 & 7) | Slide set #4 | |
| 5. | 9/24/09 | Proof of Kleene's theorem (Ch. 7) | Slide set #4 | Assignment 3 |
| 6. | 9/29/09 | Properties of regular languages (Ch. 9); Pumping lemma for regular languages (Ch. 10) | Slide set #5 | |
| 7. | 10/1/09 | Regular languages and decidability (ch. 11) | Slide set #5 | Assignment 4 |
| 8. | 10/6/09 | Context-free grammars; Regular grammars; CFG's in Chomsky Normal Form (Ch. 12 & 13) | Slide set #6 | |
| 9. | 10/8/09 | PDA's (Ch. 14) | Slide set #7 | Assignment 5 |
| 10. | 10/13/09 | CFG versus PDA (Ch. 15) | Slide set #8 | |
| 11. | 10/15/09 | First exam | ||
| 12. | 10/20/09 | Pumping lemma for context-free languages (Ch. 16) | Slide set #8 | Assignment 6 |
| 13. | 10/22/09 | Properties of context-free languages (Ch. 17) | Slide set #9 | |
| 14. | 10/27/09 | Decidability for context-free languages (Ch. 18) | Slide set #9 | |
| 15. | 10/29/09 | Turing machines (Ch. 19) | Slide set #10 | Assignment 7 |
| 16. | 10/3/09 | nPDAs, Post machines, Minsky's theorem (Ch. 20 & 21) | Slide set #11 | |
| 17. | 10/5/09 | TM variations (Ch. 22) | Slide set #12 | |
| 18. | 10/10/09 | Recursively enumerable languages (Ch. 23) | Slide set #13 | Assignment 8 |
| 19. | 11/12/09 | Second exam | ||
| 20. | 11/17/09 | The halting problem and related problems (Ch. 23, continued) | Slide set #13 | |
| 21. | 11/19/09 | Chomsky hierarchy of languages (Ch. 24) | Slide set #14 |