School of Computer Science, Tel Aviv University

# Computational Models

## (or more accurately - introduction to the theory of computation)

0368.2200

Spring 2009

http://www.cs.tau.ac.il/~bchor/CM09/compute.html

The course is being taught in two groups:

(a) Monday 13:00-16:00, Orenshtein 103, with two recitations on Wednesday

(b) Wednesday 10:00-13:00, Orenshtein 111, with two recitations on Thursday

Group (a) Lecturer: Prof. Benny Chor (benny AT cs.tau.ac.il, appointments by e-mail)

Group (b) Lecturer: Dr. Miri Priesler (mirip AT tau.ac.il, appointments by e-mail)

Group (a) Teaching Assistant: Mr. Rani Hod (ranihod AT tau.ac.il)

Group (b) Teaching Assistant: Mr. Jonathan Berant (contact info in website)

Note: The course is taught concurently in two groups. While there will be some differences in presentation style and details, the material to be covered is the same. Homework assignments, midterm, and final exams will be identical for both groups.

Class Bulletin-Board:

 Date Announcement 5/3/2009 The midterm is tentatively scheduled to Tuesday, April 7th (just before Passover).

Moed A, including (very brief) solutions.

Moed B, including (very brief) solutions.

Homework Assignments

 Assignment date handed due date solution remarks Assignment 1 9/3/09 26/3/09 , 18:00 Solution 1 Assignment 2 27/3/09 19/4/09 , 12:00 Solution 2 Assignment 3 23/4/09 7/5/09, 18:00 Solution 3 updated 28/4/09 Assignment 4 8/5/09 21/5/2009, 18:00 Solution 4 Assignment 5 28/5/09 Sunday 14/6, 18:00 Solution 5 9/6/09 Wednesday 1/7, 18:00. Solution 6

Your solution should be handed to the TAs mail boxes (Schreiber building, second floor), at the time and date specified.

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.

PrerequisitesThe course is a required course for Computer Science students, and "extended intro to Computer Science" is a prerequisite. "Discrete Math"  is recommended, though not required. Students from other disciplines are encouraged to contact the instructor.

Course Requirements and Important Information:

• 6 homework assignments, to be handed individually. (Best 5 out of 6 will be part of the grade.)
• Midterm exam. Material: Lectures 1-5, Chapters 0 to 2.
• Midterm is closed books, 10 multiple choice questions. Duration 100 minutes.
• Final exam. Closed book except for two double-sided pages.
• Course grade = 10% based on homework assignments, 90% on final exam. 10% of midterm grade is added to the weighted average of the homeworks plus final.
• Submission of at least 5 assignments with passing grades is a necessary condition for a passing grade in the course.
• You should submit your home assignments to the TAs mail boxes (Schreiber, second floor).
• You can collect your checked home assignments from room 114.

Exam Material: The exam will include everything covered in lectures and recitations, except the following topics: The busy beaver function (lecture 8). Unrestricted grammars (lecture 10). Sketch of the proof Cook-Levin theorem (lecture 12). Randomized algorithms (lecture 14).

Course Timetable : The course roughly consists of three parts:  Lectures 1-5 deal with languages and automata theory, lectures 6-10 with computability theory, and lectures 11-13 with complexity theory.

 Lecture(group a) Date Subject Reference(s) Lecture Slides (pdf) Recitation Topic Limks to Videos 1 2/3/09 Administratrivia. Some mathematical preliminaries. Finite automata. Regular languages. Closure properties: Union. Chapter 0.  Chapter 1, Section 1.1 Introduction Deterministic finite automata Treasure hunt: exploring an unknown DFA (taken from csunplugged.org) Mathematical background DFAs Lecture 02/03/09 Recitation 04/03/09: Video is missing 2 9/3 Non-Deterministic Finite Automata (NFA). Closure properties of Regular Languages. Regular expressions and their equivalence with finite automata via generalized NFAs Chapter 1, Sections 1.1-1.3 Lecture 2 NFAs. Regular expressions. closure properties of regular languages Lecture 09/03/09 Recitation 11/03/09 3 16/3 The pumping lemma. Non regular languages. Context free grammars. Chapter 1 and 2, Sections 1.4, 2.1, 2.2Hopcroft and Ullman, 3.4 Lecture 3 Additional closure properties of regular languages Lecture 16/03/09 Recitation 18/03/09 4 23/3 Context free grammars. Closure under union, concatanation, and star. Linear grammars. Ambuguity. CFL pumping lemma. Non context free languages. Chapter 2, Sections 2.1, 2,2, 2.3 Lecture 4 CFL Lecture 23/03/09 Recitation 25/03/09 5 30/3 Equivalence of Context Free Grammars and Push down automata. Non-Determinism adds power to PDAs. Chomsky normal form of CFGs. More CFL closure properties. Chapter 2, Sections 2,2, 2.3 Lecture 5 Pumping lemma for CFL. Lecture 30/03/09 Recitation 01/04/09 6 20/4 Turing Machines and alternative Models of Computers Non Deterministic TMs. Chapter 3, Sections 3.1-3.3 Lecture 6   Fancy Slides 6-30 Turing machine examples. RAM Lecture 20/04/09 Recitation 22/04/09 7 27/4 What is an algorithm? The Church-Turing Thesis. The language classes R, RE and coRE. Hilbert's tenth problem The halting problem Chapter 3, Section 3.3 Chapter 4, sections 4.1-4.2 Lecture 7 No recitation, Independence day Lecture 27/04/09 8 4/5 Review of the universal TM The acceptance and halting problems are undecidable (diagonalization proof) Computable functions. The busy beaver function is not computable (not in book). Additional undecidable languages. Chapter 4, sections 4.1-4.2 Chapter 5, sections 5.1 Lecture 8 Mapping reductions Lecture 04/05/09 Recitation 06/05/09 9 11/5 Reductions among languages Mapping reductions Chapter 5, sections 5.1, 5.3 Lecture 9 More mapping reductions Lecture 11/05/09 Recitation 13/05/09 10 18/5 Rice theorem Reductions using computation histories Unrestricted grammars Chapter 5, sections 5.1, 5.3 Lecture 10 (slightly revised May 19) Rice thm; tiling problem Lecture 18/05/09 Recitation 20/05/09 11 25/5 Intro to complexity theory: Deterministic and non-deterministic time classes; P and NP. Verifiability. Chapter 7. Lecture 11 Verifiers (NP) Lecture 25/05/09 Recitation 27/05/09 12 1/6 NP and coNP Poly time reductions: Definition and examples Sketch of the proof Cook-Levin theorem: SAT is NP-complete. Chapter 7 Lecture 12 Polynomial time reductions Lecture 01/06/09 Recitation 03/06/09 13 8/6 More poly time reductions and NP completeness languages: 3SAT to DirHamPath. SAT to IP. 3SAT to 3-COL. Bounded A_TM is NP-Complete. Decision, search, and optimization problems. A 2 approximation algorithm for vertex cover. Chapter 7 and 10 Lecture 13 Reduction from 3SAT to  Hamiltonian path NP and co-NP; more polynomial time reductions Lecture 08/06/09 Recitation 10/06/09 14 15/6 Subset Sum is NPC. NP and coNP hardness. Decision, search, and optimization problems. Approximation algorithms for hard optimization problems. Randomized (coin flipping) algorithms for hard problems. Chapter 7 and 10 Lecture 14 Approximation algorithms Lecture 15/06/09 Recitation 17/06/09: Video is missing

Administrativia Each week there will be a 3 hours lecture, followed 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 usually due two weeks after publishing. Solving assignments independently is key to understanding the material and to success in exams, and is strongly encouraged. Research done at the Technion showed that outright copying may be harmful to your health.

Textbook

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

Reference Books

• 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.
• Automata and formal languages, the open university (in Hebrew) , 1991.

Related On-line Resources

2007 year course

David Galles course at USF: http://www.cs.usfca.edu/~galles/cs411/

Other Interesting On-line Resources

• Avi Wigderson's plenary presentation at the International Congress of Mathematicians (August 2006):

See in particular opinion 76: "Why P does not equal NP and why humans will never prove it by themselves".