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).

9/3

Assignment 1 is now posted

27/3

Assignment 2 is now posted

28/3

Midterm exams from previous years when I taught the course are accessible here: 2005 , 2006 , 2007

3/4

The midterm (Tuesday, April 7th) is a closed book exam. No auxiliary material is allowed.

5/4

The midterm is at 9am. Exact location will only be known then (usual procedure).

5/4

Solution to ex1 was posted. See link below.

17/4

Midterm plus solutions is published.

19/4

Midterm grades (identified by rightmost 5 digits of ID) and statistics are published.

23/4

Assignment 3 (beta version) is now posted.

28/4

Assignment 3 has been updated, so now it is Assignment 3, version 1.1

2/5

Solution to ex2 was posted. See link below.

8/5

Assignment 4 (beta version) is now posted.

28/5

Assignment 5 is now posted. See link below.

6/6

Assignment 5 due date is postponed to Sunday 14/6, 18:00.

6/6

Assignment 6 will be posted on 11/6.

13/6

Solutions 3 and 4 are now posted.

27/6

Assignment 6 due date is postponed to Wednesday 1/7, 18:00.

27/6

Grades for assignments 1-3 can be viewed here. In case of disagreement with your own records, please contact the TAs asap.

29/6

A clarification regarding topics for the exam appear below.

29/6

A "rehersal class" (for all students) will be given once, in Lev Hall, on Thursday 9/7/09, 14:00-16:00.

30/6

Solution 5 is now posted.

30/6

The following zipped folder contains four previous exams (from 2005 and 2007), and three partial solutions. Exams from 2004 and 2006 have unfortunately disappeared with a former TA when he left for calmer seas. If you can retrieve any, they will be posted as well.

6/7

Solution 6 is now posted.

8/7

Instructions for Moed A can be found here. For Moed A itself, you will have to wait a few more days...

20/7

Grades of all submitted assignments can be found here. If you notice any discrapencies, pls let us know asap.

23/7

Moed A grades can be found here. Part 1 is the open problems (total out of 60). Part 2 is the closed problems (no. of correct answers, out of 8. Each correct answer is 5 points). Final grade is computed as min(100,0.1*homework grade + 0.9*exam grade + midterm grade). Homework grade is the average of the best 5 out of 6 assignments. If fewer than 4 assignments were submitted, homework grade is 0. Since a problem was discovered in closed question 8 (of the published version), everyone who answered (b), (c) or (d) got full credit. (a) is simply wrong and was given no credit.

The average and median of the final grades are both approx. 72.

Moed A plus brief revised solutions are now online (see link below).

25/9

Moed B plus brief revised solutions are now online (see link below).

 

A technical problem in the grading of the closed problems resulted in remarking of the exams, causing changes to the final grades in the range of 4-5 points (both up and down).

It had essenmtially no effect on the class average, even though individual effects obviously occured. Nobody failed in the course as a result of these changes.

 

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


 Assignment 6

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:

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:

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

by Muli Safra

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

Related On-line Resources 

2007 year course

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

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

 

Other Interesting On-line Resources

      P, NP and Mathematics- a computational complexity perspective

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