Organisational

       
        Class:	TTh 4-5:45, Porter 250 
 Office hours:	We,F 10-11, 331 Baskin Engineering
Prerequisites:	CMPS 130 - CMPS 101 - CE 16
     Textbook:  Martin - Introduction to Languages and the Theory of Computation (Errata)
        Final:  March 18, 4-7 pm, in same classroom
           TA:  Jay Kreps jay@cse.ucsc.edu
                Office hours: Monday 10:00 in BE 354I (Inside the Grad. Room)
		Section: Thursday, 6:00-7:00 p.m., Jack's Lounge

Summary of lectures

1:	General introduction
	Self referential paradoxes 
	Proof of the Halting Problem at programming language level
	Definition of Turing Machines and its motivation
	Examples
	Turing acceptable

	Read Chapter 9

        Syllabus
	Policies, grading
	Halting Problem
	Homework 1

2:      Definition of Turing computable
	Variations of Turing machines and
	alternates to Turing machines
	(2 stacks and queue machine)
	Mankala Turing machine
 	Simulation of nondeterministic Turing machines
	by deterministic ones

3:      Church-Turing Thesis
        Comparison between RAM and Universal Turing Machine
	"Life" implementation of Turing Machines
	Encodings and construction of Universal Turing Machine
	Closure properties of Turing acceptable and Turing decidable

	Read Chapter 10

	Homework 1 Solutions
	Homework 2
4:	Equivalence of Turing enumerable and Turing acceptable
	Universal grammars and equivalence with Turing acceptable 
	Linear bounded automata and the Chomsky hierarchy

5:	Defs of countable and uncountable
	The countably infinite union of countably infinite sets
	is countably infinite
	Diagonalization argument that shows that the power set of
	a countably infinite set is uncountable

	Read Chapter 11

	Homework 2 Solutions
	Homework 3

6: 	SA - a Turing acceptable language
	that is not Turing decidable
	NSA - a language that is not Turing acceptable
        There exists a Turing decidable language that is 
 	not context sensitive

	Decision problems
	Definition of the Halting Problem

7:	Definition of the language H corresponding
	to the Halting Problem
        H is Turing acceptable but not Turing decidable
	Various proofs that H is not Turing decidable
	including Turing's original proof based on the
	computable reals

        Homework 3 Solutions 
	Alternate proofs that rationals are countable.
	Homework 4

8:	Reductions between decision problems
	Sample Midterm Questions
	Sample Midterm

9:	Some more reductions
	Rice's Theorem and how to apply it
	
	Solutions to Sample Midterm

	Review for midterm

	Homework 4 Solutions
	Fermat's Theorem checker in Python

10:     Midterm (till Section 11.4)
        Lasts entire class period
	Midterm W04 Solutions

11:    	The Post Correspondence Problem
        Undecidable problem for Context Free languages
        
	Finish Chapter 11

	Homework 5

12: 	Finish undecidable problem for Context Free languages
     	Busy Beaver Function
	
	Read Chapter 12

13:    	Defs of primitive and mu-recursive functions
  	There exist total computable functions that
	are not primitive recursive	
  	Equivalence between partial computable functions
	and mu-recursive functions
	Alternate defs of partial computable functions

	Homework 6
        Homework 5 Solutions

14:	Growth rates
	The class P

15:	The class NP 
	Various definitions
	SAT
	Homework 7
        Homework 6 Solutions
16:	NP-completeness
	Poly-time reductions
 	Reduction of SAT to 3SAT

17:	More reductions
	Homework 8
	Problem 34-3 from CLRS 
	Homework 7 Solutions
        Fun links:
	Wikipedia on NP-completeness
        The video game Tetris is NP-hard
	A compendium of NP-complete optimization problems
	

18:   	More reductions
	Weak and strong NP-completeness of number problems

19:	How to deal with NP-completeness
 	Approximation algorithms
	Homework 8 Solutions
	Sample final
	Additional sample final questions
	Solutions to additional sample final questions


20:     Review 

Final Exam Solutions

THANKS TO EVERYONE FOR A REWARDING CLASS

Thanks to Noah Constant for correcting some of the homework solutions!