Computer Science

Computational Models0368.2200 
Winter 2013/14 
Lecture 
Monday 13:0016:00, Dach 005 
Instructor 
Nachum Dershowitz  Schreiber 218 
Recitations 
Wednesday 14:0015:00, Dan David 205 Wednesday 15:0016:00, Dan David 205 
T.A Jenny Falkovich  Handasat Tochna 209
HWs Grader




Requirements:


Prerequisites:

Extended introduction to CS (aka Scheme). 
Textbooks 
Main reference:
Other textbooks:

Exam
Forum
Midterm
Surprise Quizes
Date 
Class Topic 
Notes 
Date 
Class Topic 
Notes 
HW 
HW Sol 
Oct 14 
Administratrivia. What is an algorithm? What can and cannot be done? The Busy Beaver Problem. The Halting Problem. (Chapters 16) 
Oct 16 
The Busy Beaver Problem. The Halting Problem. 

Oct 21 
Halting problems. Reductions. Rice's Theorem. (Chapters 79) 
Oct 23 
Reduction. Rice Theorem. 
Sol 2 

Oct 28 
Interpreters. Steppers. (Chapter 10) 
Oct 30 
2D Turing Machine. 
HW 3 
Sol 3 

Nov 4 
Semidecidability. Computations. 
Nov 6 
Interpreters. Steppers. Checkers. 
Sol 4 

Nov 11 
Representations. Equivalence of models. (Chapters 1112, 14, 16) 
Nov 13 
Semidecidability (r.e.). Mapping Reductions. 
Sol 5 

Nov 18 
Descriptional complexity. Recursion Theorem. 
Nov 20 
coRE; Enumerators. 
Sol 6 

Nov 25 
ChurchTuring Thesis. Gödel's Incompleteness Theorem. (Chapters 1718) 
Nov 27 
Classical TM. Verifiability of RE. 
Sol 7 TM_Variations 

Dec 2 
P. NP. Verifiability. CookLevin Theorem. P=NP? 
Dec 4 
Descriptional complexity. 
NO HW 


Dec 9 
Polynomial reductions. NP completeness. 
Dec 11 
P vs NP 
NO HW 


Dec 16 
Polynomial space. 
Dec 18 
Two definitions of NP NPC 
R10 
HW_8 
Sol 8 

Dec 23 
Finite machines. Pumping Lemma. 
Dec 25 
More NPC Examples 
R11 
HW_9 
Sol 9 

Dec 30 
Nondeterminism. Closure Properties. 
Jan 1 
Finite State Automata. Pumping Lemma. 
HW_10 
Sol 10 

Jan 6 
Grammars. Decision Problems. 
Jan 8 
Closure Properties of Regular Languages 



Jan 13 
Philosophical implications. Conclusions. 
Jan 15 
Grammars. Pumping Lemma 
