CS3800 SP2011: Schedule

Note: This is an approximate schedule; it may change at any time.
Homework links will become active by the "assigned" dates.

1. Lecture 01, Tue 01-11-11
   • Introduction; admistrivia; overview of CSU390; assessment
   • Reading: Sipser 0
2. Lecture 02, Fri 01-14-11
   • Math primer; DFAs, state diagrams and examples
   • Reading: Sipser 0, 1.1
   • Homework 01 assigned
3. Lecture 03, Tue 01-18-11
   • Formal definitions; regular languages; regular operations
   • Reading: Sipser 1.1
4. Lecture 04, Fri 01-21-11
   • Closure properties; non-determinism; equivalence of NFAs and DFAs
   • Reading: Sipser 1.2
   • Homework 01due
     changed to Wednesday 01-23-11
   • Homework 02 assigned
5. Lecture 05, Tue 01-25-11
   • Finish equivalence of NFAs and DFAs; regular expressions; equivalence of RE and FA
   • Reading: Sipser 1.3
6. Lecture 06, Fri 01-28-11
   • Equivalence of regular expressions and Finite automata
   • Reading: Sipser 1.3
   • Homework 02 due
   • Homework 03 assigned
7. Lecture 07, Tue 02-01-11
   • Non-regular languages and the Pumping Lemma
   • Reading: Sipser 1.4
8. Lecture 08, Fri 02-04-11
   • The Pumping Lemma; closure properties; (minimization of FA - later if we have time)
   • Reading: Sipser 1.4
   • Homework 03 due
   • Homework 04 assigned
9. Lecture 09, Tue 02-08-11
   • Context-free languages; context-free grammars; ambiguity
   • Reading: Sipser 2.1
   • Handouts:
     • Constructing Context-free Grammars (An example from Prof. Aslam)
10. Lecture 10, Fri 02-11-11
    • Finish ambiguity; compare RLs and CFLs; pushdown automata
    • Reading: Sipser 2.1-2.2
    • Homework 04 due
    • Homework 05 assigned
11. Lecture 11, Tue 02-15-11
    • Equivalence of CFLs and PDAs
    • Reading: Sipser 2.2
12. Lecture 12, Fri 02-18-11
    • Pumping Lemma for CFLs; closure properties
    • Handouts:
      • The Pumping Lemma for CFLs: An Example
    • Reading: Sipser 2.3
    • Homework 05 due
    • Homework 06 assigned
13. Lecture 13, Tue 02-22-11
    • Closure properties
    • Reading: This material is covered in exercises 2.2, 2.15, 2.16, and 2.17 on pages 128 and 129.
14. Lecture 14, Fri 02-25-11
    • Turing Machines; state diagrams and examples; Church-Turing thesis
    • Reading: Sipser 3.1, 3.3
    • Homework 06 due

    Spring Break, Mon 2-28-11, Fri 03-04-11, no class

15. Lecture 15, Tue 03-8-11
    • Formal definitions; decidable and recognizable languages
    • Reading: Sipser 3.1, 3.3
16. Lecture 16, Fri 03-11-11
    • Midterm exam (in class)
    • Homework 07 assigned
17. Lecture 17, Tue 03-15-11
    • Turing Machine variants: multi-tape and non-determinisitic
    • Reading: Sipser 3.2
18. Lecture 18, Fri 03-18-11
    • Decidability - DFA
    • Reading: Sipser 4.1
    Homework 07 due
    • Homework 08 assigned
19. Lecture 19, Tue 03-22-11
    • Decidability - CFG
    • Reading: Sipser 4.1
20. Lecture 20, Fri 03-25-11
    • Diagonalization; Halting Problem
    • Reading: 4.2
21. Lecture 21, Tue 03-29-11
    • Reducibility
    • Reading: Sipser 5.1
    • Homework 08 due
    • Homework 09 assigned
22. Lecture 22, Fri 04-01-11
    • Reductions via Comutation Histories
    • Reading: Sipser 5.1
23. Lecture 23, Tue 04-05-11
    • Post Correspondence Problem
    • Reading: Sipser 5.2
24. Lecture 24, Fri 04-08-11
    • Time Complexity
    • Reading: Sipser 7.1
    • Homework 09 due
    • Homework 10 assigned
25. Lecture 25, Tue 04-12-11
    • P and NP, Polytime reductions
    • Reading: Sipser 7.2-7.3
26. Lecture 26, Fri 04-15-11
    • NP-Completeness
    • Reading: Sipser 7.4
    • Homework 10 due
27. Lecture 27, Tue 04-19-11
    • NP-Completeness
    • Reading: Sipser 7.5
28. Final Exam, Fri 04-22-11, 8 AM to 10 AM, Hurtig Hall 224

Switch to:

• CSU3800 SP11 Home Page