School of Computer Science, Tel Aviv University

Fall 2003-2004

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:00-16:00, Dach Lecture Hall

Lecturer: Benny Chor

Contact Info:

		Email	Phone	Office	Office Hours
Lecturer	Prof. Benny Chor	benny@cs.tau.ac.il	640-5977	Schreiber 223	By e-appointment
Teaching Assistant	Dr. Gad Kimmel	kgad@tau.ac.il	640-5394	Schreiber 011	By e-appointment
Grader (Bodek)	Alexander Medvedovsky	medv@tau.ac.il		MailBox 284	By e-appointment

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 1-5, Chapters 0-2. 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 2-5 deal with languages and automata theory, lectures 6-10 with

computability theory, and lectures 11-14 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.1-1.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.3-1.4
4	17/11	Context free grammars. Push down automata.	Chapter 2, Sections 2.1-2.2
5	24/11	Equivalence of PDAs and CFGs. Pumping lemma for context free languages.	Chapter 2, Sections 2.2-2.3
6	1/12	Turing machines. Algorithms. Church-Turing thesis.	Chapter 3, Sections 3.1-3.2
7	8/12	Hilbert's tenth problem. Decidability of DFA and PDA related problems.	Chapter 3, Sections 3.2-3.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.1-4.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. RE-completeness. 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.3-7.4
13	17/1	Cook-Levin theorem: SAT is NP-complete. Additional Reductions (3SAT , Traveling Salesperson). On search vs. decision problems. Reduction from 3SAT to Hamiltonian path (a separate file).	Chapter 7, Sections 7.4-7.5
14	24/1	Approaches to dealing with computational intractability: 1) approximations, 2) fixed parameter algorithms, 3) randomization.	Chapter 10, Sections 10.1-10.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 6-7 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.

Grade:

Textbook

Introduction to the Theory of Computation, M. Sipser, PWS Publishing Co., 1997.

Reference Books

Computational Complexity, C. Papadimitriou, Addison-Wesley Publishing Co., 1994.
Elements of the Theory of Computation, H. Lewis and C. Papadimitriou, Prentice-Hall, 1981.
Introduction to Automata Theory, Languages, and Computation, J. Hopcroft and J. Ullman, Addison-Wesley Publishing Co., 1979.

Other On-line Resources

Exams from previous years (and previous instructors) in Tel-Aviv Univ.

Mid-term exams from previous years (and previous instructors) in Tel-Aviv Univ.

A virtual Turing machine you can possibly run.

Other Interesting On-line Resources

Mother Jones: Alternative views on some world affairs

Why bother with Computational Models? Get your degree on line…