CS3800 09F: Syllabus

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

1. Lecture 01, Wed 09-08-09
   • Introduction; admistrivia; overview of CS3800
   • Reading: Sipser 0

2. Lecture 02, Mon 09-14-09
   • Math primer; DFAs, state diagrams and examples
   • Reading: Sipser 0, 1.1

3. Lecture 03, Wed 09-16-09
   • Formal definitions; regular languages; regular operations; regular expressions
   • Reading: Sipser 1.1
   • Homework 01 assigned

4. Lecture 04, Mon 09-21-09
   • Closure properties; non-determinism; equivalence of NFAs and DFAs
   • Reading: Sipser 1.2

5. Lecture 05, Wed 09-23-09
   • Finish equivalence of NFAs and DFAs; regular expressions; equivalence of RE and FA
   • Reading: Sipser 1.3
   • Homework 01 due
   • Homework 02 assigned

6. Lecture 06, Mon 09-28-09
   • Finish equivalence of RE and FA; non-regular languages and the Pumping Lemma
   • Reading: Sipser 1.4

7. Lecture 07, Wed 09-30-09
   • The Pumping Lemma; closure properties; minimization of FA
   • Handouts:
     • Non-regularity Examples
   • Reading: Sipser 1.4
   • Homework 02 due
   • Homework 03 assigned

8. Lecture 08, Mon 10-05-09
   • Context-free languages; context-free grammars; ambiguity
   • Reading: Sipser 2.1-2.2
   • Handouts:
     • Constructing Context-free Grammars

9. Lecture 09, Wed 10-07-09
   • Finish ambiguity; compare RLs and CFLs; pushdown automata
   • Reading: Sipser 2.1-2.2
   • Homework 03 due
   • Homework 04 assigned

10. Columbus Day, Mon 10-12-09
    • No class...

11. Lecture 10, Wed 10-14-09
    • Equivalence of CFLs and PDAs
    • Reading: Sipser 2.2
    • Homework 04 due
    • Homework 05 assigned

12. Lecture 11, Mon 10-19-09
    • Pumping Lemma for CFLs; closure properties
    • Handouts:
      • The Pumping Lemma for CFLs: An Example
    • Reading: Sipser 2.3

13. Lecture 12, Wed 10-21-09
    • Turing Machines; state diagrams and examples; Church-Turing thesis
    • Reading: Sipser 3.1, 3.3

14. Lecture 13, Mon 10-26-09
    • Formal definitions; decidable and recognizable languages
    • Reading: Sipser 3.1, 3.3
    • Homework 05 due
      • Note: This assignment cannot be handed in late. I will be passing out solutions to this assignment the day it is due, in preparation for the midterm exam.

15. Lecture 14, Wed 10-28-09
    • Midterm exam (in class)

16. Lecture 15, Mon 11-02-09
    • Turing Machine variants: multi-tape and non-determinisitic
    • Reading: Sipser 3.2

17. Lecture 16, Wed 11-04-09
    • Decidability; cardinality of infinite sets; diagonalization
    • Reading: Sipser 4.1, 4.2
    • Homework 06 assigned

18. Lecture 17, Mon 11-09-09
    • Diagonalization; Halting Problem
    • Reading: Sipser 4.2

19. Veterans' Day, Wed 11-11-09
    • No class...
    • Homework 06 due (accepted until Fri 11-13-09)
    • Homework 07 assigned

20. Lecture 18, Mon 11-16-09
    • Reducibility
    • Reading: Sipser 5.1-5.3

21. Lecture 19, Wed 11-18-09
    • Redicibility; time complexity
    • Reading: Sipser 7.1

22. Lecture 20, Mon 11-23-09
    • P and NP
    • Reading: Sipser 7.2-7.3
    • Homework 07 due
    • Homework 08 assigned

23. Thanksgiving Break, Wed 11-25-09
    • No class...

24. Lecture 21, Mon 11-30-09
    • Polytime reductions
    • Reading: Sipser 7.4

25. Lecture 22, Wed 12-02-09
    • NP-Completeness
    • Reading: Sipser 7.4-7.5
    • Homework 08 due
    • Homework 09 assigned

26. Lecture 23, Mon 12-07-09
    • NP-Completeness
    • Reading: Sipser 7.4-7.5

27. Lecture 24, Wed 12-09-09
    • NP-Completeness
    • Reading: Sipser 7.4-7.5
    • Homework 09 due

28. Final Exam, TBA
    • TBA

Switch to:

• CS3800 09F Home Page