Schedule of Topics - CS 341 - Fall 2011

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.
Aug 24
  • class policies
  • mathematical preliminaries
  • Read the mathematical preliminaries handout
  • Read the proof techniques review sheet
  • Read ch 0
  • Homework 1 assigned
Aug 29
  • regular languages
  • finite automata
  • Read Sipser ch 1
  • Homework 2 assigned
Sep 5
  • finite automata
  • nondeterministic FAs
  • equivalence of DFAs and NFAs
  • Read Sipser 1.2
Sep 12
  • closure properties of regular languages
  • regular expressions
  • equivalence of FAs and regular expressions
  • Read Sipser 1.3
Sep 19
  • non-regular languages
  • Pumping lemma for regular languages
Sep 26
  • Pumping Lemma
  • decision procedures for regular languages
  • state minimization
  • Midterm 1: Oct 3
Oct 3
  • context-free languages
  • context-free grammars
  • Chomsky normal form
  • Midterm 1 on Monday night
  • Read section 2.1
Oct 10
  • pushdown automata
  • equivalence of PDAs and CFGs
  • closure properties of CFLs
  • Read section 2.2
Oct 17
  • non-context-free languages
  • Pumping lemma for CFLs
  • Read Sipser 2.3
Oct 24
  • more Pumping Lemma for CFLs
  • decision procedures for CFGs and PDAs
Oct 31
  • Turing machines
  • Midterm 2: Nov 7
  • Read section 3.1
Nov 7
  • decidable and semi-decidable languages
  • Read sections 3.2 and 3.3
Nov 14
  • TM variants
  • decidability
  • Read chapter 4
Nov 21
  • reduction proofs
  • Halting problem
  • Rice's Theorem
  • Read sections 5.1, 5.3
Nov 28
  • more on reductions
  • complexity introduction
Final exam slot: