Weekly schedule¶
Weekly topics¶
| Week | Theme | Lecture | Sipser pages |
|---|---|---|---|
| 1 | Introduction | Problems! | 1--25 |
| 2 | Models of Computation | DFAs & NFA | 31--54 |
| 3 | Models of Computation | NFA equiv. DFA & Regular Expressions | 55--76 |
| 4 | Models of Computation | Limits of the Regular Languages, Grammars | 77--82 |
| 5 | Models of Computation | Context-Free Languages (CFLs) [PDAs/CFGs] | 101--124 |
| 6 | Models of Computation | Turing Machines (TMs) | 165--187 |
| 7 | Decidability | Decidability | 193--211, 215--238 |
| 8 | Complexity | Complexity | 275--298 |
| 9 | Complexity | NP-Completeness | 299--322 |
| 10 | Complexity | Space complexity | 331--337, 348--351 |
| 11 | Revision | ||
| 12 | Revision |
Textbook¶
The textbook is:
Sipser, M. (2012). Introduction to the theory of computation (3rd ed.). Cengage.
If you like reading eBooks then you may find it useful to read it through BibliU.