COMPUTATIONAL MODELS

 
Final: 		Tu Dec 9, 4-7pm, same classroom
Final review: 	Sat Dec 6, 1-3pm, same classroom

Special office hours: 	
Krish		Sun Dec 7, 1-3pm, same classroom
Manfred 	Fr Dec 5, 1-2pm, E2-357


Instructor: Manfred Warmuth
office	E2-357
phone	459-4950
hours	M 1-2, W 12-1

Lecture times:
MW 5:00pm-6:45pm, J. Baskin Engr 372

Teaching Assistant: Krishna Roskin
sec. 1	M 11:00-12:10, BE 169
sec. 2	Th 12:00-1:10, Kresge 319

Reader: Tim Frohbisher


Lectures
I	Paradoxes, Halting Problem, Turing Machines, Turing's thesis
	Proof techniques
	Halting Problem
	Course Syllabus
	Policies

II	Functions, relations, sets
	Read: Chapters 1 and 2
	Def of regular languages, regular expressions, FA's
	Hw1 Due 10-8-08 beg. of class

III	Pairwise indistinguishable words
	Closure properties for FAs
	Cross product construction
	NFA's, NFA acceptance, LambdNFAs
	Closure properties of LambdaNFAs

IV	Conversion of LambdaNFAs NFA's,
	Subset constructions 
	Example proof that reg. expression equals a certain language
	Eliminating states from an NFA
	Hw1 solutions 
	Mean: 70, median: 66, deviation: 17.7

	Hw2 Due 10-15-08 beg. of class

V	Kleene's theorem
	Elimination proof
        Floyd-Warshal type proof given of book
	Properties I_M, I_L

VI	Minimization alg, proof of Pumping Lemma
	Hw2 solutions 
	Mean: 77.5, median: 82, deviation: 16.8

	Hw3 Due 10-22-08 beg. of class

VII	Pumping Lemma for regular languages
	Example proofs
	Decision problems regular automata and languages

VIII	Hidden Markov Models
	Context free grammars and languages
	Derivations, derivation tree
	Regular grammars
	Hw3 solutions 
	Mean 66.4, median: 69.5, deviation: 16.4

	Midterm questions 
	Sample Midterm 1 with solutions
	Sample Midterm 2 with solutions
	Midterm study plan

IX	Ambiguity in context free languages
	Midterm review
	Sample Midterm 3 with solutions

X	Midterm midterm solutions 
	Mean 75.6, median 78, deviation 13

	Hw4 Due Nov. 6 by 4:45 to Vanessa in department office E2-298

XI	Eliminating lambda and unit rules
	Chomsky Normal Form
	CYK parsing alg.

XII	Proof PL for context free languages
	Examples of how to apply it
	Hw5  Due Th Nov. 13  by 4:45 to Vanessa in department office E2-298 
	Hw4 solutions 
	Mean 62.6, median: 59, deviation: 15.6

XIII	Push down automata
	Equivalence of acceptance criteria
	Deterministic PDAs

XIV	Equivalence between PDAs and CFGs
	Closure properties of CFLs
       	Using closure properties to show non-context freeness
	Decision problems for CFLs
	Hw6 Due 11-19-08 beg. of class
	Hw5 solutions 
	Mean 67.1, median 71, deviation 14.5

XV	Intro to TMs
        - as acceptors
	- computation of partial functions
	Simulation of TMs with 2 stack 

XVI	Simulation of TMs with a queue
	Simulation of non-det TM by det TM
	Hw7 Due 11-26-08 beg. of class
	Hw6 solutions 
	Hw6 extra credit solution 
	Mean 73.4, median 80, deviation 21.4

XVII 	Relationship between TM and programmable computers
	Intro to the Universal TM
	Universal TM
	Closure properties of Turing acceptable 
	and Turing decidable languages
	Turing enumerable = Turing acceptable

XVIII	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
	SA, NSA, various proofs that NSA not T.a.
	T.a. languages are not closed under compliment
	Language H associated with the Halting problem
	Hw8 Due 12-29-08 beg. of class
	Hw7 solutions 
	Mean 71.7, median 75, deviation 17.5

XIX	Three proofs that H is undecidable
	including Turing's original proof
	Hw8 solutions 
XX	Turing test
        Posters about philosophical question re. computers
	Review
	Sample Final 1 and solutions
	Sample Final 2 and solutions
	Sample Final 3 
	Additional questions re Tms

	Sols to final
	Average ??, mean ??, stand.dev. ??