Computational Models
0368-2200
  Fall 2007
Tel Aviv University



Instructor:
Prof. Nachum Dershowitz

Teaching Assistant:
Ricky Rosen

Exercise Grader:
Elia Even-Hen   mail box: 366

General Announcements:

  • Previous exams and quizzes in Computational Models course.
  • You should submit your home assignments directly to the grader's mail box.
  • You can collect your checked home assignments from room 114.


Class Bulletin-Board:

Date

Announcement

29.10.2006

Quiz will be on December 8 at 9am

31.10.2006

Exercise 1 is on the web

01.11.2006

There was a mistake in exercise 1, question 2 (a). The mistake was corrected.

07.11.2006

Notes of lecture 3 are on the web it includes minor improvements plus the last page has an example of the construction of a regular expression from an automaton.

13.11.2006

Exercise 2 is on the web

02.12.2006

Details about the quiz:
The material includes everything up to TMs. This is approximately the first six lectures: Finite automata, regular languages, context free languages and grammars, Turing Machines. The quiz will include questions from homework 1 and 2 (but not only questions from the HW). The quiz will be on December 8 from 9 to 11 am.

 

05.12.2006

Exercise 3 is on the web

10.12.2006

Quiz solution

11.12.2006 

 There was a mistake in exercise 3, question 4 (a,b,d). The mistake was corrected. It should be A<m instead of A<T ,also in (a) it should be “if B is in coRE then also A is in coRE (not B)”

14.12.2006

Quiz grades

25.12.2006

Exercise 4 is on the web

05.01.2007

Regarding question 7: A 3CNF is similar to SAT but you can only have three literals (variable or a negation of a variable) in each clause. For example (x1ÚØx2Ú x4) Ù (Øx2Ú x7ÚØx3) Ù (x2ÚØ x6Ú x2) Ù…

 

22.01.2007

A few extra copies of the course notes are in the copy room in Schreiber.

17.02.2007

You may bring two pages to the exam

19.02.2007

The Exam Solution (DOC)

20.09.2007

MOED B Exam Solution

02.10.2007

Grades



Home Assignments:

Assignment

Handed
Date

Submission
Deadline*

Solution

 Exercise1 (PS) or (DOC)

01.11.2006

15.11.2006

 DOC

 Exercise2 (PS) or (DOC)

14.11.2006

29.11.2006

 DOC

 Exercise3 (DOC) (PS)

05.12.2006

20.12.2006

 DOC

 Exercise 4 (DOC) (PS)

26.12.2006

10.01.2007

 DOC

 Exercise 5 (DOC) (PS)

09.01.2007

24.01.2007

 DOC

 

 

 

 

 

 

 

 


* Please submit the exercise directly to the grader mail box, until the hour 23:59 of the submission deadline.

Course Plan:

 

* The presentations are from last year

Lecture

Subject

References

Lecture Slides

Recitations

1

 

Adminisrativia and introduction. Mathematical terminology. Finite automata and regular languages. Busy Beaver problem.

Chapter 0.
Chapter 1, Section 1.1.

models1

* lec1.pdf

Mathematical background. DFA.

2

 

Nondeterminism finite state automata; Equivalence of regular languages and regular expressions.

Chapter 1, Sections 1.1-1.3.

models2

* lec2.pdf

NFA, the pumping lemma.

3

 

The pumping lemma. Myhill-Nerode theorem. Non regular languages; Regular expressions.

Chapter 1 and 2, Sections 1.4, 2.1, 2.2.

lecture 3

* lec3.pdf

Equivalent classes.

4

 

Context free grammars. Chomsky normal form. Linear grammars. pumping lemma for context free languages.

Chapter 2, Sections 2.2-2.3.


lecture 4

* lec4.pdf

* lec6.pdf

TM correction

Turing’s paper

CFG.

5

 

Turing machines. Algorithms. Multi-Tape TMs; Nondeterministic TMs.  Church-Turing thesis.

Chapter 3, Sections 3.1-3.3.

TM.

6

 

 

 

lecture 6

 

 

7

 

Hilbert's tenth problem.  Encodings. Universal TM. Diagonalization.Proof  of undecidability of the halting problem by diagonalization.

Chapter 3, Section 3.3.
Chapter 4, Sections 4.1-4.2

lecture 7

* lec7.pdf

 

8

 

Computable functions. Reductions. Proofs of undecidability via reductions by computation histories and by mapping reductions.

Chapter 5, Sections 5.1, 5.3.

lecture 8

* lec8.pdf

The class R. Reductions. Rice Theorem.

9

 

Rice Theorem. Kolmogorov  Complexity. RE completeness. Turing reductions. Godel incompleteness theorem.

Chapter 6, 6.2, 6.3, 6.4.

lecture 9

* lec9.pdf

The class RE. Mapping reductions.

10

 

Undecidable tiling, or domino,  problems. Recursion theorem. Unrestricted Grammar.

Chapter 5, 5.2.
Chapter 6, 6.

lecture 10
* lec10.pdf

 

11

 

Time complexity introduction. DTIME and NTIME. Time dependence on models. The class P.

Chapter 7, Sections 7.1- 7.2.

* lec11.pdf

 

12

 

The class NP.  Polynomial time Reductions. NP completeness, Cook-Levin theorem: SAT is NP-complete.

Chapter 7, Sections  7.3-7.4.

* lec12.pdf

 

13

 

Additional Reductions (IP, HamPath, Bounded Tiling). On search vs. decision problems. Approximation Algorithms.

Chapter 7, Sections 7.4-7.5
Chapter 10, Section 10.1

* lec13.pdf

 

14

 

Approaches to dealing with computational intractability: fixed parameter algorithms and randomization.

Chapter 10, Section 10.2.

* lec14.pdf

 


* The presentations are from last year

 


References:

  • Sipser, Introduction to the Theory of Computation.
  • Hopcroft and Ullman, Introduction to Automata Theory, Languages, and Computation.


Other Related Books:

  • Papadimitriou, Computational Complexity.
  • Corman, Introduction to Algorithms.
  • Jones, Computability and Complexity.
  • Davis, Segal and Weyuker, Computability, Complexity, and Languages (2d ed).
  • Otomatim vesafot formaliot, Open University, vols. A and B.
  • Lewis and Papadimitriou, Elements of the Theory of Computation (2nd. ed.).
  • David Harel, Algorithmics- The spirit of computing, ch. 8-9.
  • A. Ben-Amram, Algorithm and Programs: Introduction to Programming Languages, Computation and Complexity (Hebrew).