CSU390: Syllabus

Created: Monday, July 24, 2006
Last modified: 

Note: This is an approximate syllabus; it may change at any time.

1. Lecture 01, Fri 09-08-06
• Introduction & overview; administrivia; math review
• Reading: Sipser 0
• Homework 00 assigned
2. Lecture 02, Tue 09-12-06
• Strings & languages; finite automata: formal definition & state transition diagrams
• Reading: Sipser 0, 1.1, FA-Formal-Definitions.pdf
• Homework 01 assigned
3. Lecture 03, Fri 09-15-06
• Regular languages; combining languages; closure properties
• Reading: Sipser 1.1
• Homework 00 due
4. Lecture 04, Tue 09-19-06
• Nondeterminism; equivalence of NFAs and DFAs; closure properties
• Reading: Sipser 1.2, FA-Formal-Definitions.pdf
• Homework 01 due
• Homework 02 assigned
5. Lecture 05, Fri 09-22-06
• Regular operations; regular expressions
• Reading: Sipser 1.3
6. Lecture 06, Tue 09-26-06
• Equivalence of regular expressions and FA
• Reading: Sipser 1.3, GNFA-Formal-Definition.pdf
• Homework 02 due
• Homework 03 assigned
7. Lecture 07, Fri 09-29-06
• Nonregular languages: Pumping Lemma and its application
• Reading: Sipser 1.4, Pumping-Lemma-Reg-Langs.pdf
8. Lecture 08, Tue 10-03-06
• Proof of Pumping Lemma; review for Exam 1
• Reading: Sipser 1.4, Exam-1-Guide.pdf
• Homework 03 due
9. Fri 10-06-06
• Exam 1 (in class) Exam-1-Guide.pdf
10. Lecture 09, Tue 10-10-06
• Context-free languages; context-free grammars; parse trees; ambiguity
• Reading: Sipser 2.1
• Homework 04 assigned
11. Lecture 10, Fri 10-13-06
• Constructing CFGs; pushdown automata
• Reading: Sipser 2.2, Pushdown-Automata.pdf
12. Lecture 11, Tue 10-17-06
• Equivalence of CFLs and PDAs
• Reading: Sipser 2.2
• Homework 04 due
• Homework 05 assigned
13. Lecture 12, Fri 10-20-06
• Pumping Lemma for CFLs; closure properties; non-context-free languages
• Reading: Sipser 2.3, Pumping-Lemma-CFLs.pdf
14. Lecture 13, Tue 10-24-06
• Turing machines: state diagrams; decidable and Turing-recognizable languages
• Reading: Sipser 3.1, TM-Examples.pdf, Deciders-vs-Recognizers.pdf
• Homework 05 due
• Homework 06 assigned
15. Lecture 14, Fri 10-27-06
• Turing machine variants: multi-tape and nondeterministic
• Reading: Sipser 3.2, TM-Variants.pdf
16. Lecture 15, Tue 10-31-06
• Closure properties; Church-Turing thesis
• Reading: Sipser 3.3
17. Lecture 16, Fri 11-03-06
• Review for Exam 2
• Reading: Exam-2-Guide.pdf
• Homework 06 due
18. Tue 11-07-06
• Exam 2 (in class) Exam-2-Guide.pdf
19. Lecture 17, Fri 11-10-06
• Decision problems; decidability
• Reading: Sipser 3.3, 4.1, Decision-Problems.pdf, Decidability-Results.pdf
• Homework 07 assigned
20. Lecture 18, Tue 11-14-06
• Countable and uncountable sets; more languages than TMs; undecidability
• Reading: Sipser 4.2, 5.1, Undecidability-Results.pdf
21. Lecture 19, Fri 11-17-06
• Undecidability (continued): Halting Problem, mapping reductions
• Reading: Sipser 5.1, 5.3, Undecidability-Results.pdf, SchemeDemos
• Homework 07 due
• Homework 08 assigned
22. Lecture 20, Tue 11-21-06
• Time complexity
• Reading: Sipser 7.1, Time-Complexity.pdf
23. Lecture 21, Tue 11-28-06
• P and NP
• Reading: Sipser 7.2, 7.3, P-and-NP.pdf, P-Examples.pdf, NP-Examples.pdf
• Homework 08 due
• Homework 09 assigned
24. Lecture 22, Fri 12-01-06
• Polytime reductions, NP-Completeness
• Reading: Sipser 7.4, NP-Completeness.pdf
25. Lecture 23, Tue 12-05-06
• Review for Exam 3
• Reading: Exam-3-Guide.pdf
• Homework 09 due
26. Mon 12-11-06
• Exam 3 Exam-3-Guide.pdf
• Room: 153 Snell Engineering Building
• Time: 1:00-3:00 pm

---

Switch to:

• CSU390 Home Page

---

rjw@ccs.neu.edu