CS 254: Computability and Complexity
Winter 2018
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 301
- Course website: http://cs.carleton.edu/faculty/jyang/cs254.18w/
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 | 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 Theory | ||||
| Week 1: finite automata | 1. 01/03 W Introduction; an undecidable problem Sipser 0.1–0.4 Out: ps01 (on Moodle) | 2. 01/05 F deterministic finite automata Sipser 1.1a Out: ps02 | ||
| Week 2: nondeterminism | 3. 01/08 M regular operations Sipser 1.1b | 4. 01/10 W nondeterministic finite automata Sipser 1.2a | 5. 01/12 F DFA-NFA equivalence Sipser 1.2b Out: ps03 | |
| Week 3: regular expressions | 6. 01/15 M Sipser 1.3a | 7. 01/17 W DFA-regexp equivalence Sipser 1.3b | 8. 01/19 F nonregular languages and the pumping lemma Sipser 1.4 Out: ps04 | |
| Week 4: context-free languages | 9. 01/22 M context-free grammars Sipser 2.1 | 10. 01/24 W pushdown automata Sipser 2.2 | 11. 01/26 F non-context-free languages Sipser 2.3 | |
| Unit 2: Computability Theory | ||||
| Week 5: Turing machines | 12. 01/29 M Turing machines: computation and examples Sipser 3.1 Out: ps05 | 13. 01/31 W Exam 1
| 14. 02/02 F recursive and recursively enumerable languages Sipser 3.2a | |
| Week 6: decidability | (mid-term break) Out: ps06 | 15. 02/07 W Turing machines: variants, enumerators Sipser 3.2b | 16. 02/09 F encoding, halting problem Sipser 3.3, 4.2 Out: ps07 | |
| Week 7: undecidability | 17. 02/12 M acceptance and emptiness Sipser 5.1 | 18. 02/14 W computability and reducibility Sipser 5.3 | 19. 02/16 F Church–Turing thesis, - Turing-complete: Sipser 4.1 | |
| Unit 3: Complexity Theory | ||||
| Week 8: P vs. NP | 20. 02/19 M P Sipser 7.1, 7.2 Out: ps08 | 21. 02/21 W Exam 2
| 22. 02/23 F NP Sipser 7.3 Out: ps09 | |
| Week 9: NP-completeness | 23. 02/26 M NP-completeness Sipser 7.4 | 24. 02/28 W An NP-complete problem Sipser 7.4 | 25. 03/02 F More NP-complete problems Sipser 7.5 Out: ps10 | |
| Week 10: space complexity | 26. 03/05 M Even more NP-complete problems Sipser 7.5 | 27. 03/07 W SPACE Sipser 8.1–8.3 | 28. 03/09 F (catch-up/wrap-up)
| |