CSU390 08Sp: 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, Mon 01-07-08
   • Introduction; admistrivia; overview of CSU390; assessment
   • Reading: Sipser 0

2. Lecture 02, Thu 01-10-08
   • Math primer; DFAs, state diagrams and examples
   • Reading: Sipser 0, 1.1
   • Homework 01 assigned

3. Lecture 03, Mon 01-14-08 (SNOW Day)
   • Formal definitions; regular languages; regular operations
   • Reading: Sipser 1.1

4. Lecture 04, Thu 01-17-08
   • Closure properties; non-determinism; equivalence of NFAs and DFAs
   • Reading: Sipser 1.2
   • Homework 01due
     changed to Wednesday 01-23-08
   • Homework 02 assigned

   Martin Luther King Jr. Birthday, Mon 01-21-08, no class

5. Lecture 05, Thu 01-24-08
   • Finish equivalence of NFAs and DFAs; regular expressions; equivalence of RE and FA
   • Reading: Sipser 1.3

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

7. Lecture 07, Thu 01-31-08
   • The Pumping Lemma; closure properties; (minimization of FA - later if we have time)
   • Reading: Sipser 1.4
   • Homework 02 due
   • Homework 03 assigned

8. Lecture 08, Mon 02-04-08
   • Context-free languages; context-free grammars; ambiguity
   • Reading: Sipser 2.1
   • Handouts:
     • Constructing Context-free Grammars (An example from Prof. Aslam)

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

10. Lecture 10, Mon 02-11-08
    • Equivalence of CFLs and PDAs
    • Reading: Sipser 2.2

11. Lecture 11, Thu 02-14-08
    • Pumping Lemma for CFLs; closure properties
    • Handouts:
      • The Pumping Lemma for CFLs: An Example
    • Reading: Sipser 2.3
    • Homework 04 due
    • Homework 05 assigned

    Presidents' Day, Mon 02-18-08, no class

12. Lecture 12, Thu 02-21-08
    • Turing Machines; state diagrams and examples; Church-Turing thesis
    • Reading: Sipser 3.1, 3.3

13. Lecture 13, Mon 02-25-08
    • 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.

14. Lecture 14, Thu 02-28-08
    • Midterm exam (in class)

    Spring Break, Mon 03-03-08, Thu 03-06-08, no class

15. Lecture 15, Mon 03-10-08
    • Turing Machine variants: multi-tape and non-determinisitic
    • Reading: Sipser 3.2

16. Lecture 16, Thu 03-13-08
    • Decidability; cardinality of infinite sets; diagonalization
    • Reading: Sipser 4.1, 4.2
    • Homework 06 assigned

17. Lecture 17, Mon 03-17-08
    • Diagonalization; Halting Problem
    • Reading: Sipser 4.2

18. Lecture 18, Thu 03-20-08
    • Reducibility
    • Reading: Sipser 5.1-5.3
    • Homework 06 due
    • Homework 07 assigned

19. Lecture 19, Mon 03-24-08
    • Redicibility; time complexity
    • Reading: Sipser 7.1

20. Lecture 20, Thu 03-27-08
    • P and NP
    • Reading: Sipser 7.2-7.3

21. Lecture 21, Mon 03-31-08
    • Polytime reductions
    • Reading: Sipser 7.4

22. Lecture 22, Thu 04-03-08
    • NP-Completeness
    • Reading: Sipser 7.4-7.5
    • Homework 07 due

23. Lecture 23, Mon 04-07-08
    • NP-Completeness
    • Reading: Sipser 7.4-7.5
    • Homework 08 assigned

24. Lecture 24, Thu 04-10-08
    • NP-Completeness
    • Reading: Sipser 7.4-7.5

25. Lecture 25, Mon 04-14-08
    • NP-Completeness
    • Reading: Sipser 7.4-7.5
    • Homework 08 due

Switch to:

• CSU390 SP08 Home Page