Elaine Rich
Prentice Hall, 2008
ISBN: 9780132288064
|
Elaine Rich Prentice Hall, 2008 ISBN: 9780132288064 |
 |
Michael Sipser Course Technology, 2006 ISBN: 9780534950972 |
 |
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman Addison Wesley, 2006 ISBN: 9780321462251 |
 |
Harry R. Lewis and Christos H. Papadimitriou Prentice Hall, 1997 ISBN: 9780132624787 |
| Week | Date | Topics | Readings | Notes | Events |
| 1 | Aug 27 | Mathematical background | Appendix A | AppA.pdf | a1.doc due Sep 10 6pm |
| 2 | Sep 3 | Languages and strings | Chapter 2 | ch2.pdf | |
| 3 | Sep 10 | The big picture: a language hierarchy | Chapters 3-4 | ch3-4.pdf | a2.doc due Sep 17 6pm |
| 4 | Sep 17 | Finite State Machines | Chapter 5 | ch5.pdf | a3.doc due Oct 1 6pm |
| 5 | Sep 24 | ||||
| 6 | Oct 1 | Regular expressions/grammars Regular and nonregular languages |
Chapters 6-7 Chapter 8 |
ch6-7.pdf ch8.pdf |
tutorial.pdf; mini.doc due Oct 15 6pm a4.doc due Oct 15 6pm |
| 7 | Oct 8 | Context-free grammars | Chapter 11 | ch11.pdf | a5.doc due Oct 29 6pm |
| 8 | Oct 15 | Pushdown automata Context-free and non-context-free languages |
Chapter 12 Chapters 13-14 |
ch12.pdf ch13-14.pdf |
|
| 9 | Oct 22 | Turing machine | Chapter 17 | ch17.pdf | a6.doc due Nov 26 6pm |
| 10 | Oct 29 | Church-Turing thesis; Halting problem; D and SD; Reduction | Chapters 18-21 | ch18-21.pdf | |
| 11 | Nov 5 | Complexity | Chapters 27-28 | ch27-28.pdf | |
| 12 | Nov 12 | ||||
| 13 | Nov 19 | ||||
| 14 | Nov 26 | Review | review.pdf | online course evaluation due Dec 10 | |
| 15 | Dec 3 | Final1 | last lecture | ||
| 16 | Dec 10 | Final2 | 8-10:30pm |