COMPUTATIONAL MODELS

Phone	459-4950
Office	E2-357
Hours	Mo 10-11, Th 2-3

	MWF 2:00-3:10, E2-192

Office	??? tba later
Hours 	??? tba later
Sec. 1	Tu 4-5:45 in E2-192
Sec. 2	F 11-12:10 Soc Sci 2-137

1	Paradoxes, Halting Problem, Turing Machines, Turing's thesis
	Halting Problem
	Course Syllabus
	Policies

2	Proof techniques, functions, relations, sets
	Read: Sections 1 and 2
	Hw1 Due 4-9-08 beg. of class
	Hw1 bookpages scanned Thanks Dave Chirag!

3	Def of regular languages, regular expressions, FA's

4	Pairwise indistinguishable words, NFA's

5	NFA acceptance, LambdNFAs, conversion to NFA's,
	Closure properties of LambdaNFAs, Subset constructions 
	Hw1 solutions Average 80.4
	Hw2 Due 4-9-08 beg. of class

6	Hw review
	Example proof that reg. expression equals a certain language
	Eliminating states from an NFA

7	Kleene's theorem
	Elimination proof
        Floyd-Warshal type proof given of book

8	Properties I_M, I_L
	Hw2 solutions Average 79.9
	Hw3 Due 4-23-08 beg. of class

9	Minimization alg, proof of Pumping Lemma

10	Apps of Pumping Lemma
	Midterm questions 
	Hw3 solutions Average 66
	Hw4 Due 4-30-08 beg. of class

11	Decision problems for regular languages

12	F - wrapup reg. languages - Context free languages
	Sample Midterm 1 with solutions
	Sample Midterm 2 with solutions


13	Mo - ambiguity in context free languages

14	We - hw4 is due
	Review for midterm
	Hw4 solutions Average 76
        Extra midterm review by Bryan at 2pm on Th
	- at the Bakin white boards


15  	F: Midterm solutions Average 78.76, Stand.Dev 14

16	Eliminating lambda and unit rules
	Chomsky Normal Form

17	CYK parsing alg.
	Intro to PL for Context Free Languages
	Hw5 Due 5-14-08 beg. of class

18	Complete the proof of the PL
	Examples of how to apply it

19	Another PL application
	Push down automata
	Equivalence of acceptance criteria

20	Deterministic PDAs
	Closure properties of CFLs
       	Using closure properties to show non-context freeness
	Hw5 solutions Corrected Average 81
	Hw6 Due 5-21-08 beg. of class

21	Decision problems for CFLs

22	Intro to TMs
        - as acceptors
	- computation of partial functions

23	Simulation of TMs with 2 stack or a queue
	Hw7 Due 5-28-08 beg. of class
	Hw6 solutions Average 71

24	Simulation of non-det TM by det TM
	Relationship between TM and programmable computers
	Intro to the Universal TM

Memorial day

25	Universal TM
	Closure properties of Turing acceptable 
	and Turing decidable languages
	Hw8 Due 6-4-08 of class
	Hw7 solutions Average 89

26	Countably infinite, uncoutably infinite
	Diagonalization proof that the powerset of the c.i.  set is u.i.
	Proof of the existance of languages that are not Turing acceptable

27	SA, NSA, various proofs that NSA not T.a.
	T.a. languages are not closed under compliment
	Language H associated with the Halting problem

28	Three proofs that H is undecidable
	including Turing's original proof
	Turing test
        Posters about philosophical question re. computers
	Hw8 solutions Average 87
	Begin review of final

29	Review
	Sample Final 1 and solutions
	Sample Final 2 and solutions
	Additional questions re Tms

	Sols to final Average 79, Stand.Dev. 14