CIT 596 Theory of Computation -- Spring 2014

The general plan is

cover Chapter 1 in its entirety
Chapter 2 until the deterministic PDA part.
have the first midterm around March 3
cover Chapter 3 from Sipser.
Chapter 34 from CLRS (algorithms text) for NP completeness.
midterm 2 around April 3
decidability which is Chapter 4 of Sipser.

The final will be cumulative and is scheduled on what the registrar says

The schedule will be added to as we proceed. Here is what the first month or so looks like.

Date	Lecture Topics	Assigned Readings & Other Info
Jan 16	Course introduction Finite State Machines.	Textbook - Pages 31 to 40 Intro and logistics an example automata formal definition
Jan 21	Snow!
Jan 23	Designing automata Regular operations Union construction	Textbook - Pages 41 to 47
Jan 28	Nondeterminism - what is an NFA	Textbook - Pages 47 to 53
Jan 30	Equivalence of NFA and DFA Using NFAs to show regular languages are closed under concatenation and star	Textbook - Pages 58 to 63
Feb 4	Regular Expressions	Textbook - Pages 63 to 69 Some info about the assignment (also nerd jokes) One of SEVERAL uses of regular expressions common regex
Feb 6	Regular Expressions - part 2	Textbook section on GNFAs
Feb 11	Examples of all the algorithms we have covered	NFA 2 DFA solution to NFA 2 DFA NFA 2 Regex example A regex crossword!
Feb 13	Snow!
Feb 18	Pumping Lemma	Textbook pages 78-82 Pumping Lemma Random set of tips for code navigation Pumping lemma note
Feb 20	More Pumping Lemma examples	Read all the way to end of Chapter 1 in the book regular expression equivalence
Feb 25	Intro to CFG	Chapter 2 Pg 101-108 Example of a real language being described by grammar - graphviz
Feb 27	CFG in Chomsky Normal Form Intro to PDAs	NOT FOR MIDTERM Chapter 2 Pg 109-114 One way to parse... why care about CNF?
Mar 4	Midterm
Mar 6	Midterm solution discussion One more example of converting CFG to CNF
Mar 18	Push down automata	Slides Pages 111-116
Mar 20	PDA = CFG? CYK parsing	A chapter on dynamic programming. (Pg 174-176 were covered in class) A YouTube video about CYK parsing.
Mar 25	Pumping lemma for CFG	notes
Mar 27	A more detailed pumping lemma example	Pages 128-129 No need to read the proof. Concentrate on the application instead.
Apr 1	Turing Machines - definitons and examples	Pages 164-173 turing machine simulator Turing's original paper A more accessible version of Turing's paper a classic Turing machine
Apr 3	Turing Machines - how are they connected to algorithms	Examples of Turing machines computing(slides) Turing + Lego = Everything is awesome!
Apr 8	P, NP and NP-Complete	slides
Apr 10	Computing some complexities	A cheat sheet for common complexities slides Karp's seminal paper
Apr 15	Midterm 2
Apr 17	The Traveling Salesman Problem	tsp slides
Apr 22	More NP Complete problems Some ideas on solving NP Complete problems	slides
Apr 24	Decidability	Read Chapter 4 from Sipser Poetic proof of the halting problem Solution to questions on decidability
Apr 29	Halting problem
May 6	Final exam (will be cumulative)