Organisational

       
        Class:	TTh 12-1:45, Social Sciences 263 
 Office hours:	We 11-12:  E2 357 
Prerequisites:	CMPS 130 - CMPS 101 - CE 16
     Textbook:  Martin - Introduction to Languages and the Theory of Computation (Errata)
        Final:  We, March 21, 4-7pm, E2-489

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 Made one problem extra credit

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
	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:	Discussion of 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
	Various proofs that H is not Turing decidable
	including Turing's original proof based on the
	computable reals
	Intro to reductions between decision problems
 
        Homework 3 Solutions
	Homework 4

8:	Lots of reduction examples

9:	Some more reductions
	Rice's Theorem and how to apply it
	
	Homework 4 Solutions
	Fermat's Theorem checker in Python

	Sample Midterm Questions
	Sample Midterm
	Solutions to Sample Midterm

10:	Review for midterm

11:     Midterm (till Section 11.4)
        Lasts entire class period
	Midterm W07 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
	Def of mu-recursive functions
  	Equivalence between partial computable functions
	and mu-recursive functions

14:	Alternate defs of partial computable functions

	Growth rates
	The class P

        Homework 5 Solutions
	Homework 6

15:	The class NP
	Various definitions
	NP-completeness
	Poly-time reductions

16:	Reduction of SAT to 3SAT,
        3SAT to CLIQUE
        CLIQUE to IS
        CLIQUE to VC
	Homework 7

        Homework 6 Solutions

17:	More reductions
        3SAT to 3COL
	3colorability reduction from CRLS 
        VC to HC (out of Garey and Johnson)

        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
	Weak NP completeness of Subset Sum
        (3SAT to SS)
	Pseudopolynomial time algorithm for SS
	Strong NP completeness of 3Partition
	Homework 8

	Homework 7 Solutions

     	Hints:
	14.30: SS to PARTITION
	You need add 1 or 2 large numbers to the
	instance of SS so that the even split in PARTITION
	corresponds to the uneven split in SS

	14.25: You might use the fact that the number of
	odd degree verices in an undirected graph is even 
	(prove this by induction)

 	Try an alternate proof that replaces each edge by a gadget

19:	How to deal with NP-completeness
 	Approximation algorithms

20:	Sols to Hw8
	Homework 8 Solutions

	Sample final
	Additional sample final questions
21:     Review 
	Solutions to additional sample final questions