School
of Computer Science, Tel
Aviv University
Fall 20032004
Computational Models
(or more accurately  introduction to the theory of
computation)
0368.2200
http://www.cs.tau.ac.il/~bchor/CM/compute.html
Mondays
13:0016:00, Dach Lecture Hall
Lecturer:
Benny Chor
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@tau.ac.il


MailBox
284

By eappointment

Moed B Exam: Sept. 1st, 2004
Instructions
for the Moed B exam are rather long, and a bit different than Moed A,
so we highly recommend you carefully look at them before the exam.
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 "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:
 5 homework assignments.
 Midterm exam: Friday, Dec. 12, 9:00 am. Material:
Lectures 15, Chapters 02. Grades.
 Final exam. Closed book except for 4
pages of your choice. Final grade computed as following: Let e be exerices grade (4 best out
of 5),
t
 test grade, and
q be the
quiz (midterm) grade. Then
final =
max {
e*.15+
q*.25+
t*.60,
e*.15+
t*.85}.
Final Grades.
Course Schedule:
The course consists roughly of three
parts: Lectures 25 deal
with languages and automata theory, lectures 610 with
computability theory, and lectures 1114 with complexity theory.
Lecture
___________

Date
______

Subject
______________________________________

Reference(s)
__________________

1

27/10/03

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

Chapter 0.
Chapter 1, Section 1.1

2

3/11

Nondeterminism
finite state automata and regular expressions.
(printer
friendlier version)

Chapter 1, Sections 1.11.2

3

10/11

Equivalence of
regular languages and regular expressions.
The pumping lemma. Non regular
languages. (printer friendlier version; ps version)

Chapter 1, Sections1.31.4

4

17/11

Context free grammars. Push down automata.

Chapter 2, Sections 2.12.2

5

24/11

Equivalence of PDAs and CFGs. Pumping lemma for
context free languages.

Chapter 2, Sections 2.22.3

6

1/12

Turing machines. Algorithms. ChurchTuring
thesis.

Chapter 3, Sections 3.13.2

7

8/12

Hilbert's tenth problem. Decidability of DFA and
PDA related problems.

Chapter 3, Sections 3.23.3,
Chapter 4, Section 4.1

8

15/12

Decidability of PDA/CFG related problems.
Diagonalization.
Proof of undecidability of the halting problem by diagonalization.

Chapter 4, Sections
4.14.2

9

22/12

Mapping reductions. Proofs of undecidability via
mapping reductions.
Recursive inseparability.

Chapter 5, Sections 5.1, 5.3

10

29/12

Godel incompleteness theorem. REcompleteness. Turing
reductions.
Undecidability of Kolmogorov
complexity. Proof of Rice theorem.
Time complexity – introduction.

Chapter 6, Sections 6.2, 6.3, 6.4.
Chapter 7, Section 7.1

11

5/1/2004

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

Chapter 7, Sections
7.1 7.2

12

12/1

The class NP. Polynomial time Reductions.
NP completeness

Chapter 7, Sections
7.37.4

13

17/1

CookLevin theorem: SAT is NPcomplete.
Additional Reductions (3SAT, Traveling Salesperson). On search vs. decision
problems.
Reduction from 3SAT to Hamiltonian path (a
separate file).

Chapter
7, Sections
7.47.5

14

24/1

Approaches to dealing with computational
intractability:
1) approximations, 2) fixed parameter algorithms, 3) randomization.

Chapter 10, Sections 10.110.2

Presentations are based on those prepared by Prof.
Maurice Herlihy for a similar course given at Brown
University.
Problem Sets
Problem Set 1 
due Nov. 18. Partial
solution.
Problem Set 2 
due
Dec. 9. Partial
solution.
Problem Set 3 
due Jan. 6, 2004.
Partial solution.
Problem Set 4 
due
Jan. 20, 2004. Partial solution.
Problem Set 5
 due date postponed to Feb. 9, 2004.
Clarification to problem
set 5, problem 6, parts (c) and (d): Here,
7/8 approximation means satisfying at least 7/8 of
the optimum. In the terminology used
in class, this would be
1/8 performance ratio, as 7/8=1(1/8).
Administrativia
Each week there will be a 3 hours lecture and 1
hour
recitation. There will be 67 homework problems. Rethinking previous
announcement, homework submission is in singles
only
(no pairs, triplets, quartets, quintets etc.). Homework should be done
independently between different individuals. External sources (books,
journal
articles, web pages) can be used but should be clearly quoted.
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
Exams from previous years (and previous
instructors) in
TelAviv Univ.
Midterm exams from previous years (and previous
instructors) in TelAviv Univ.
A
virtual Turing machine you can possibly run.
Other Interesting Online
Resources