Schedule of Topics - CS 341 - Summer 2008

This schedule is just a guide - the order of topics may be changed during the semester. You are responsible for the material as it is presented in class.

Week
 Topic
 Reading and Events
All reading assignments are from Sipser unless otherwise specified.
Jun 2
  • class policies
  • mathematical preliminaries
  • regular languages
  • Read the mathematical preliminaries handout
  • Read the proof techniques review sheet
  • Read ch 0
  • Homework 1 assigned
Jun 9
  • regular languages
  • finite automata
  • nondeterministic finite automata
  • equivalence of DFAs and NFAs
  • closure properties of reg languages
  • Read Sipser ch 1
  • Homework 2 assigned
  • hw 1 due Monday and hw 2 due Friday
Jun 16
  • regular expressions
  • equivalence of FAs and reg exprs
  • non-regular languages/pumping lemma for regular languages
  • decision procedures for reg languages
  • context-free languages
  • context-free grammars
  • Read Sipser 2.1-2.3
  • Read more about CFGs:
http://en.wikipedia.org/wiki/Context-free_grammar
Jun 23
  • Chomsky normal form
  • pushdown automata
  • equivalence of PDAs and CFGs
  • closure properties for CFLs
  • non-context-free languages/pumping lemma
  • decision procedures for CFLs
  • Turing machines
  • Finish reading ch 2
  • The midterm will be 7-9 pm on 6/24 (tentative)
    • The midterm will cover all material through the end of class on 6/20.
Jun 30
  • recursive and recursively enumerable languages
  • TM variants
  • deciability
  • Read ch 3, begin ch 4
Jul 7
  • reduction proofs
  • Halting problem
  • Rice's theorem
  • Read ch 4, 5.1 and 5.3

Final Exams: July 11-12