CS 254: Computability and Complexity
Fall 2017
Basic Information
- Instructor: Jed Yang, Center for Math & Computing 324,
- Office hours: Monday 16:20–17:20 (in CMC 306), Thursday 14:35–15:35, Friday 13:00–14:00; or by appointment
- Lectures: 3a (MW 11:10–12:20, F 12:00–13:00) in Center for Math & Computing 206
- Course website: http://cs.carleton.edu/faculty/jyang/cs254.17f/
Course Information
An introduction to the theory of computation. What problems can and cannot be solved efficiently by computers? What problems cannot be solved by computers, period? Topics include formal models of computation, including finite-state automata, pushdown automata, and Turing machines; formal languages, including regular expressions and context-free grammars; computability and uncomputability; and computational complexity, particularly NP-completeness.- Textbook: Introduction to the Theory of Computation, 3rd edition, Michael Sipser, 2013.
Homework
Homework will be posted and collected electronically on Moodle.Solutions must be typeset with LaTeX. Some helpful links:
- (optional) homework template: hw-template.tex
- getting started: a short introduction | a tutorial [MIT] | more detailed tutorials | Carleton LaTeX Workshop
- reference: the not so short introduction | a reference guide [Cambridge] | the LaTeX Wikibook
- tools: a symbol finder | a table editor | a finite state machine designer
- cloud-based editors: ShareLaTeX | Overleaf (formerly writeLaTeX)
Calendar
Schedule to be updated throughout the term; topics, readings, and exam dates are tentative and subject to change.
| Week | Monday | Wednesday | Friday | |
|---|---|---|---|---|
| Unit 1: Automata and Languages | ||||
| Week 1: finite automata | 1. 09/11 M Introduction; an undecidable problem Sipser 0.1–0.4 Out: ps01 (on Moodle) | 2. 09/13 W deterministic finite automata Sipser 1.1a Out: ps02 | 3. 09/15 F regular operations Sipser 1.1b | |
| Week 2: regular expressions | 4. 09/18 M nondeterministic finite automata Sipser 1.2a | 5. 09/20 W DFA-NFA equivalence Sipser 1.2b Out: ps03 | 6. 09/22 F Sipser 1.3a | |
| Week 3: context-free languages | 7. 09/25 M DFA-regexp equivalence Sipser 1.3b | 8. 09/27 W nonregular languages and the pumping lemma Sipser 1.4 Out: ps04 | 9. 09/29 F context-free grammars Sipser 2.1 | |
| Unit 2: Computability Theory | ||||
| Week 4: Turing machines | 10. 10/02 M pushdown automata Sipser 2.2 | 11. 10/04 W non-context-free languages Sipser 2.3 Out: ps05 | 12. 10/06 F Turing machines: computation and examples Sipser 3.1 | |
| Week 5: decidability | 13. 10/09 M Exam 1
| 14. 10/11 W recursive and recursively enumerable languages Sipser 3.2a Out: ps06 | 15. 10/13 F Turing machines: variants, enumerators Sipser 3.2b | |
| Week 6: undecidability | (mid-term break) | 16. 10/18 W encoding, halting problem Sipser 3.3, 4.2 Out: ps07 | 17. 10/20 F acceptance and emptiness Sipser 5.1 | |
| Unit 3: Complexity Theory | ||||
| Week 7: time complexity | 18. 10/23 M computability and reducibility Sipser 5.3 | 19. 10/25 W Church–Turing thesis, - Turing-complete: Sipser 4.1; 7.1 Out: ps08 | 20. 10/27 F P Sipser 7.2 | |
| Week 8: P vs. NP | 21. 10/30 M Exam 2
| 22. 11/01 W NP Sipser 7.3 Out: ps09 | 23. 11/03 F NP-completeness Sipser 7.4 | |
| Week 9: NP-completeness | 24. 11/06 M An NP-complete problem Sipser 7.4 | 25. 11/08 W More NP-complete problems Sipser 7.5 Out: ps10 | 26. 11/10 F Even more NP-complete problems Sipser 7.5 | |
| Week 10: space complexity | 27. 11/13 M SPACE Sipser 8.1–8.3 | 28. 11/15 W (catch-up/wrap-up)
| (reading day) | |