Organisational

       
        Class:	TTh 12-1:45, Social Sciences I, Rm. 149
 Office hours:	We 10-11, Th 2-3:  E2 357 
Prerequisites:	CMPS 130 - CMPS 101 - CE 16
     Textbook:  Martin - Introduction to Languages and the Theory of Computation (Errata)
        Final:  March 15, 8:00-11:00 am
           TA:  Jay Kreps jay@cse.ucsc.edu
	        Office Hours: Mon. 5:00-6:00, E2 Rm. 489
		Sections:
		          Monday     3:30-4:40 pm in Social Science I, 153  
			  Wednesday  2:30-3:40 pm at Baskin Whiteboards (Jack's Lounge)

		Final Review Sessions
		   Manfred - Sa March 12, 1:00-3:00, Jack Baskin 372
		   Jay - Mo March 14, 3:30-4:40 in SSI 153

		Pictures of your classmates

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

3:      Simulation of nondeterministic Turing machines
	by deterministic ones
	Church-Turing Thesis
        Comparison between RAM and Universal Turing Machine
	Encodings and construction of Universal Turing Machine
	Closure properties of Turing acceptable and Turing decidable

	Read Chapter 10
	"Life" implementation of Turing Machines

	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

	General proof that |S| less than 2^|S|: Brookshear
	Proof of Schroeder-Bernstein Theorem


	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:	Solutions to HW3
        Proof that the rationals are countably infinite
	Alternate proofs

	Definition of the language H corresponding
	to the Halting Problem
        H is Turing acceptable but not Turing decidable
 
        Homework 3 Solutions
	Homework 4

8:	Various proofs that H is not Turing decidable
	including Turing's original proof based on the
	computable reals
	Reductions between decision problems

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


10:	Review for midterm

11:     Midterm (till Section 11.4)
        Lasts entire class period
	Midterm W05 Solutions

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


     	Busy Beaver Function
	
	Read Chapter 12
	Homework 5

13:    	Defs of primitive 
  	There exist total computable functions that
	are not primitive recursive	
	Ackermann function

14:	Def of mu-recursive functions
  	Equivalence between partial computable functions
	and mu-recursive functions
	Alternate defs of partial computable functions

	Growth rates

        Homework 5 Solutions
	Homework 6

15:	The class P
	The class NP
	Various definitions
	SAT

16:	NP-completeness
	Poly-time reductions
 	Reduction of SAT to 3SAT
        Homework 6 Solutions
	Homework 7

17:	More reductions
	Homework 8
	3colorability reduction from CRLS 
	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 



THANKS TO EVERYONE FOR A REWARDING CLASS