Reading Assignments

• 4/25/08: Section 6.3 - Introduction to NP-Complete Problems.
• 4/25/08: Section 6.2 - Introduction to the class NP.
• 4/21/08: Section 6.1 - Introduction to the class P.
• 4/14/08: Sections 5.4 - Undecidable Problems
• 4/11/08: Sections 5.3 - The Halting Problem
• 4/4/08: Sections 4.3-4.4 - Variations on a Turing Machine.
• 3/31/08: Section 4.2 - Computations using Turning Machines.
• 3/26/08: Section 4.1 - Introduction to Turing Machines. (For the Wed after break.)
• 3/7/08: Section 3.6 - Pumping Lemma for Context Free Languages.
• 3/3/08: Section 3.4 - PDA's and CFL's.
• 2/29/08: Sections 3.2, 3.5, 3.7 and 3.8 - Odds and ends about CFL's.
• 2/22/08: Section 3.3 - Pushdown Automata.
• 2/18/08: Section 3.1 - Introduction to Context-Free Languages.
• 2/11/08: Section 2.6 - Decision problems for Regular Languages.
• 2/4/08: Section 2.5 - Pumping Lemma for Regular Languages.
• 1/28/08: Section 2.3 - DFA - NFA Equivalence.
• 1/18/08: Section 2.4 - Regular Expressions.
• 1/18/08: Section 2.2 - Introduction to Non-Deterministic Finite State Automata.
• 1/14/08: Section 2.1 - Introduction to Finite State Automata.
• 1/14/08: Chapter 1 - Preliminaries and some mathematical review.