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