Computer Science
Tel-Aviv University

Computational Models

0368.2200

Winter 2013/14


Lecture 


Monday 13:00-16:00, Dach 005

Instructor 


Nachum Dershowitz | Schreiber 218 

Recitations 


Wednesday 14:00-15:00, Dan David 205

Wednesday 15:00-16:00, Dan David 205


 T.A                        Jenny Falkovich | Handasat Tochna 209 


HWs Grader 

                   

Itzik Malkiel 



Requirements:



  • Attendance is mandatory.
  • HomeWorks (done individually) - 10 points.
  • Midterm - 16 points if it helps and 8 points otherwise.
  • Surprise quizzes - 5 points.
  • Final test - 74-82 points (depending on midterm).


Prerequisites:


Extended introduction to CS (aka Scheme).


Recommended Reading

Textbooks 


Main reference:


Draft in progress containing our course material can be found here.


Other textbooks:


M. Sipser, Introduction to the Theory of Computation, PWS Publishing Co., 1997 (second edition, 2005).


C. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Co., 1994.


H. Lewis and C. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981.


J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Co., 1979.


אוטומטים ושפות פורמליות, האוניברסיטה הפתוחה, 1991


Announcements


Exam


Forum


Midterm



Surprise Quizes



Homework assignments



Schedule

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 1-6)

L1

Oct 16

The Busy Beaver Problem. The Halting Problem.

R1

HW 1

Sol 1

Oct 21

Halting problems. Reductions. Rice's Theorem.

(Chapters 7-9)

L2

Oct 23

Reduction. Rice Theorem.

R2

HW 2

Sol 2

Oct 28

Interpreters. Steppers.

(Chapter 10)

L3

Oct 30

2D Turing Machine. 

R3

HW 3

Sol 3

Nov 4

Semidecidability. Computations.
(Chapter 13)

L4

Nov 6

Interpreters. Steppers. Checkers.

R4

HW_4 

Sol 4

Nov 11

Representations. Equivalence of models.

(Chapters 11-12, 14, 16)

L5

Nov 13

Semidecidability (r.e.). Mapping Reductions.

R5

HW_5 

Sol 5

Nov 18

Descriptional complexity. Recursion Theorem.
(Chapter 15, 19)

L6

Nov 20

coRE; Enumerators.

R6

HW_6 

Sol 6

Nov 25

Church-Turing Thesis. Gödel's Incompleteness Theorem. (Chapters 17-18)

L7

Nov 27


Classical TM. Verifiability of RE.


R7

HW_7 

Sol 7

TM_Variations

Dec 2

P. NP. Verifiability. Cook-Levin Theorem. P=NP?

L8

Dec 4

Descriptional complexity. 

R8

NO HW


Dec 9

Polynomial reductions.  NP completeness.

L9

Dec 11

P vs NP

R9

NO HW


Dec 16

Polynomial space. 

L10

Dec 18 

Two definitions of NP

NPC

R10

HW_8

Sol 8

Dec 23

Finite machines. Pumping Lemma.

L11

Dec 25

More NPC Examples

R11

HW_9

Sol 9

Dec 30

Nondeterminism. Closure Properties.

L12

Jan 1

Finite State Automata. 

Pumping Lemma.

R12

HW_10

Sol 10

Jan 6

Grammars. Decision Problems.

L13

Jan 8

Closure Properties of Regular Languages

R13



Jan 13

Philosophical implications. Conclusions.

Lxx

Jan 15

Grammars. Pumping Lemma

R14