CSU390: Syllabus

Created: Thursday, January 05, 2006
Last modified: 

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

1. Lecture 01, Tue 01-10-06
• Introduction & overview; administrivia; math review
• Reading: Sipser 0
• Homework 00 assigned
2. Lecture 02, Fri 01-13-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, Tue 01-17-06
• Regular languages; combining languages; closure properties
• Reading: Sipser 1.1
• Homework 00 due
4. Lecture 04, Fri 01-20-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, Tue 01-24-06
• Regular operations; regular expressions
• Reading: Sipser 1.3
6. Lecture 06, Fri 01-27-06
• Equivalence of regular expressions and FA
• Reading: Sipser 1.3
• Homework 02 due
• Homework 03 assigned
7. Lecture 07, Tue 01-31-06
• Nonregular languages: Pumping Lemma
• Reading: Sipser 1.4, Pumping-Lemma-Reg-Langs.pdf
8. Lecture 08, Fri 02-03-06
• Application of Pumping Lemma & closure properties
• Reading: Sipser 1.4
9. Lecture 09, Tue 02-07-06
• Review for Exam 1
• Homework 03 due
10. Fri 02-10-06
• Exam 1 (in class)
11. Lecture 10, Tue 02-14-06
• Context-free languages; context-free grammars; parse trees; ambiguity
• Reading: Sipser 2.1
12. Lecture 11, Fri 02-17-06
• Pushdown automata
• Reading: Sipser 2.2, Pushdown-Automata.pdf
• Homework 04 assigned
13. Lecture 12, Tue 02-21-06
• Equivalence of CFLs and PDAs
• Reading: Sipser 2.2
14. Lecture 13, Fri 02-24-06
• Pumping Lemma for CFLs; closure properties; non-context-free languages
• Reading: Sipser 2.3, Pumping-Lemma-CFLs.pdf
• Homework 04 due
• Homework 05 assigned
15. Lecture 14, Tue 02-28-06
• Turing machines: state diagrams; decidable and Turing-recognizable languages
• Reading: Sipser 3.1, TM-Examples.pdf, Deciders-vs-Recognizers.pdf
16. Lecture 15, Fri 03-03-06
• Turing machine variants: multi-tape and nondeterministic
• Reading: Sipser 3.2, TM-Variants.pdf
• Homework 05 due
• Homework 06 assigned
17. Tue 03-07-06 and Fri 03-10-06
• Spring Break Week
18. Lecture 16, Tue 03-14-06
• Closure properties; Church-Turing thesis
• Reading: Sipser 3.3
19. Lecture 17, Fri 03-17-06
• Review for Exam 2
• Homework 06 due
20. Tue 03-21-06
• Exam 2 (in class)
21. Lecture 18, Fri 03-24-06
• Decision problems; decidability
• Reading: Sipser 3.3, 4.1, Decision-Problems.pdf, Decidability-Results.pdf
• Homework 07 assigned
22. Lecture 19, Tue 03-28-06
• Countable and uncountable sets; more languages than TMs
• Reading: Sipser 4.2
23. Lecture 20, Fri 03-31-06
• Undecidability, Halting Problem, mapping reductions
• Reading: Sipser 4.2, 5.1, 5.3, Undecidability-Results.pdf, SchemeMappingReductionDemos
• Homework 07 due
• Homework 08 assigned
24. Lecture 21, Tue 04-04-06
• Time complexity
• Reading: Sipser 7.1, Time-Complexity.pdf
25. Lecture 22, Fri 04-07-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
26. Lecture 23, Tue 04-11-06
• Polytime reductions, NP-Completeness
• Reading: Sipser 7.4, NP-Completeness.pdf
27. Lecture 24, Fri 04-14-06
• NP-Completeness
• Reading: Sipser 7.4
28. Lecture 25, Tue 04-18-06
• Review for Exam 3
• Homework 09 due
29. Mon 04-24-06 (during finals week)
• Exam 3
• Room: 5 Kariotis Hall
• Time: 8:00 a.m.

---

Switch to:

• CSU390 Home Page

---

rjw@ccs.neu.edu