School of Computer
Science, Tel Aviv University
Fall 20042005
Computational Models
(or more accurately  introduction to the theory of computation)
0368.2200
http://www.cs.tau.ac.il/~bchor/CM05/compute.html
Mondays
13:0016:00, Dach Lecture Hall
Lecturer:
Benny Chor
Teaching
Assistant: Gadi Kimmel
Solutions to Moed A Exam (scanned, 5MB)
Moed A
Grades Moed B Grades
(Remark: Same factor applied to Moed A and B)
Contact Info:


Email

Phone

Office

Office Hours

Lecturer

Prof. Benny Chor

benny@cs.tau.ac.il

6405977

Schreiber 223

By
eappointment

Teaching Assistant

Dr. Gad
Kimmel

kgad@tau.ac.il

6405394

Schreiber 011

By eappointment

Grader (Bodek)

Alexander Medvedovsky

medv@post.tau.ac.il


Mail Box 400

By eappointment

Course Outline
The course deals with fundamental questions of computer science:
 What
is a computer ?
 What
can computers do (and what can they not
do)?
 Why are
some problems computationally hard, while very similar ones are
computationally easy?
These questions were mostly raised during the 20th century,
and they accompanied and guided the actual development of computers.
Many of these and related questions were resolved, but some (especially those
dealing with computational hardness) retained their status
as "key open problems" into the 21st century.
Prerequisites
The course is a required course
for Computer Science students, and "extended intro to Computer
Science" is a prerequisite.
Students from other disciplines are encouraged to contact the instructor.
Course Requirements and Important Dates:
 6
homework assignments. (Best 5 out of 6 will be part of the grade. Only
parts of each assignment will be graded.)
 Midterm
exam: Friday, Nov. 26. Material:
Lectures 15, Chapters 0 to 2. Grades.
 Final
exam. Closed book except for 4 doublesided pages of your choice.
Course Timetable (schedule and material of future
lectures are tentative):
The
course consists roughly of three parts: Lectures 15 deal with languages
and automata theory, lectures 510 with computability theory, and lectures
1114 with complexity theory.
Lecture
___________

Date
______

Subject
______________________________________

Reference(s)
__________________

Recitation
___________

1

18/10/04

Administrativia and introduction. Mathematical terminology. Finite automata and regular languages  examples.

Chapter 0.
Chapter 1, Section 1.1

Mathematical
background

2

25/10

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

Chapter 1, Sections 1.11.3

DFAs

3

1/11

The pumping lemma. Non regular languages.
Context free grammars. Chomsky normal form.

Chapter 1 and 2, Sections 1.4, 2.1, 2.2

Additional closure properties of regular languages

4

8/11

Push down automata. NonDeterminism
adds power to PDAs. Equivalence of PDAs and CFGs. Pumping lemma
for context free languages.

Chapter 2, Sections 2.22.3

Examples: Pumping lemma for (non) regular languages. CFL~PDA

5

15/11

NonDeterminism adds power to PDAs (revised);
Closure properties of CFLs; Algorithmic Aspects of PDAs and CFLs. Turing machines.

Chapter 2, Sections 2.22.3. Chapter 3, Section 3.1

Examples: Pumping lemma for PDAs.

6

22/11

Turing machines. Algorithms. MultiTape TMs; RAMs; Nondeterministic TMs. ChurchTuring thesis.
Printer friendlier version.

Chapter 3, Sections 3.13.3

More TM examples.
TM with two sided infinite tape.

7

29/11

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

Chapter 3, Section 3.3,
Chapter 4, Sections 4.14.2

More TM examples.
Addition on TM.

8

6/12

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

Chapter 5, Sections 5.1, 5.3


9

13/12

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

Chapter 6, 6.2, 6.3, 6.4.


10

20/12

Undecidable tiling, or domino, problems
(old fashioned chalk dust presentation)
Recursion theorem (printable version)
Unrestricted Grammars  David Galles
slides (printable version)

Chapter 5, 5.2
Chapter 6, 6.1

Rice Theorem
Kolmogorov complexity

11

27/12

Time complexity – introduction. DTIME and NTIME.
Time dependence on models. The class P. (printable version)

Chapter 7, Sections
7.1 7.2

The Recursion Theorem

12

3/1/2005

The class NP. Polynomial time Reductions. NP
completeness, CookLevin theorem: SAT is NPcomplete.
(printable version)

Chapter 7, Sections
7.37.4

Additonal languages in NP

13

10/1

Additional Reductions (IP, HamPath, Bounded Tiling).
On search vs. decision problems. Approximation
Algorithms. (printable version)
Reduction from 3SAT to Hamiltonian path (a separate ps
file)

Chapter 7,
Sections
7.47.5
Chapter 10, Section 10.1

Additional reductions:
3 coloring and set cover
are NP complete

14

17/1

Approaches to dealing with computational intractability:
1) fixed parameter algorithms, 2) randomization. (13MB file!). (printable version)

Chapter 10,
Section 10.2.
The view from Mars

Review of course material.

Presentations are based on those prepared by Prof.
Maurice Herlihy for a similar course
given at Brown University.
Problem Sets
Problem Set 1 
Published Oct. 18, due Nov. 9,
2004. Partial solution.
Problem Set 2 
Published Nov. 9, due Nov. 23,
2004. Partial solution.
Problem Set 3  Published
Dec. 1, due Dec. 16, 2004. Partial solution.
Problem Set 4  Published
Dec. 17, due Dec. 30, 2004. Partial solution.
Problem Set 5  Published
Jan. 6, due Jan. 20, 2005. Complete solution.
Early Printer Friendly
Handouts
http://www.cs.tau.ac.il/~tavorhai/CompuModels.htm
(courtesy of Haim Tavor).
Administrativia
Each week (including 1st week)
there will be a 3 hours lecture, preceeded by a 1
hour recitation. There will be 6 homework problems. Homework submission
is in singles only (no pairs, triplets,
quartets, quintets etc.). External sources (books, journal articles, web pages)
can be used but should be clearly quoted. Assignments due two weeks after publishing. Grading will apply to
part of the problems in each assignment. Solving assignments
independently is key to understanding the material and to success in exams, and
is strongly encouraged. Research done at the Technion
shows that outright copying may be harmful to your health.
Grade: 1015% based on homework assignments, 2025% based on
midterm, 6070% on final exam. Midterm component weighted only if it
contributes nonnegatively to final outcome.
Textbook
Introduction to the
Theory of Computation, M. Sipser, PWS
Publishing Co., 1997.
Reference Books
 Computational
Complexity, C. Papadimitriou, AddisonWesley Publishing Co.,
1994.
 Elements
of the Theory of Computation, H. Lewis and C. Papadimitriou, PrenticeHall,
1981.
 Introduction
to Automata Theory, Languages, and Computation, J. Hopcroft
and J. Ullman, AddisonWesley Publishing Co.,
1979.
Other Online Resources
Last year course
David Galles course at USF: http://www.cs.usfca.edu/~galles/cs411/
Exams from previous years (and
previous instructors) in TelAviv Univ. This includes Fall 2003/4
exams from my last year's course.
Midterm exams from previous years (and previous
instructors) in TelAviv Univ.
A virtual Turing machine you can possibly run.
Other Interesting Online Resources