School of Computer Science, Tel Aviv University

Computational Models

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

 

0368.2200

Spring 2007

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

Monday 13:00-16:00, Orenshtein 103

Wednesday 10:00-13:00, Dach Lecture Hall

 

Lecturer: Benny Chor (benny AT cs.tau.ac.il, contact by e-appointments)

Teaching Assistants: Udi Boker (udiboker AT tau.ac.il)

                                 Yuval Inbar (inbaryuv ATpost.tau.ac.il)

                                 Ricky Rosen (rosenric AT post.tau.ac.il)

Grader(bodek): Ilya Even Chen, Box 366 Schreiber (2nd floor)
                         (elih AT post.tau.ac.il)

 

General Announcements:

  • Previous exams and quizzes in Computational Models course.
  • You should submit your home assignments directly to the grader's mail box.
  • You can collect your checked home assignments from room 114.

 

Class Bulletin-Board:

Date

Announcement

March 3, 2007

Due to the heavy congestion experienced in the first lecture, another weekly lecture has been scheduled. It will take place on Mondays 13:00-16:00. Location: Orenshtein 103.

March 24, 2007

Mid term exam will take place (as planned) on Friday, April 13. Material includes Lectures

1-5, Chapters 0-2 in Sipser's book. It is a closed books exam , with 10 multiple choice questions. Duration: 100 minutes.

March 27, 2007

Due to the planned strike on Wednesday, 28 March, the submission deadline of the second assignment is changed to Thursday, 29 March.

March 27, 2007

There will be a supplemental recitation on this Thursday, 29 March, between 14:00-15:00.

The recitation is planned for the students of Yuval Inbar and Ricky Rosen, and in case of a strike on Wednesday (28 March) also for the students of Udi Boker.

Rooms: Students of Ricky Rosen: Melamed hall; Students of Yuval Inbar and Udi Boker: Holtzblat hall

March 29, 2007

 Yuval has promised his students a written document with the basic steps of the proof of closure of context-free languages under intersection with a regular language. Of course all of you are invited to read it.

March 30, 2007

We will hold the midterm on the original date, Friday the 13 (of April). Due to the Wednesday March 28 strike, the midterm will cover only the material of the first FOUR lectures. Its format will be as planned: 10 multiple choice questions, 100 minutes duration, closed books.

We plan to hold review sessions for the midterm by the teaching assistants two days before the midterm (namely on Wed., April 11) in the late afternoon. However the campus may
be closed on that day as well. If it is feasible to hold the midterm as planned, it will
be held even if this (supplementary and voluntary) review cannot take place.

April 10, 2007

We will hold the midterm on the original date, Friday the 13 (of April), 9am, in the same format noted above.

 

Due to an unexpectedly large demand, the teaching assistants will hold special, extended office hours on Wednesday April 11, 18:00-19:00, in the following three locations: (1) Melamed hall;
 (2) Orenstein 103; (3) Orenstein 111.

April 12, 2007

Some notes regarding questions from the office hours on 11-4-2007. Notes

April 13, 2007

Due to the strike, submission deadline of assignment no. 3 is postponed till further notice!

April 17, 2007

Midterm results: The midterm turned out to be highly popular, with 186 active players (95% of registered  students). The average (78) and median (80) are also fairly high. The standard deviation (18) is, ahhm, rather standard.  An excel file with all grades (sorted by IDs) is attached.

May 6, 2007

The midterm exam with highlighted solutions is attached.

May 22, 2007

With the termination of the strike, we are trying to bring the course back to normal, to the extent possible with a severely truncated semester.

On Thursday, May 24, we will hold all the normally scheduled Thursday recitations. The plan is to go over the midterm questions in detail.

Assignment 3 is now due on Thursday, May 31.

Lectures next week will be the same for both the Monday and the Wednesday groups. At this point, lecture 5, missed by the Wednesday fans, will not be given. Depending on the availability of time slots for make up lectures, this may (or may not) change in the future.

May 24, 2007

Ricky's class on Thursday 13:00 - 14:00 will be held (permanently) in Schreiber  006

May 30, 2007

Ricky's recitation tomorrow (31.05) from 14:00 to 15:00 will be held in Engineering studies - classrooms number 207.

May 31, 2007

For Yuval's students: detailed description of the last ex on the recitation today (31.05) -- TM that accepts (and decides) palindromes, is at:  palindromes over {0,1}

June 5th, 2007

Ricky's recitation tomorrow (7.06) from 14:00 to 15:00 will be held in Dan David 205.

June 8th, 2007

Submission deadline of assignment no. 4 is postponed to Thursday 21.06.07

June 14, 2007

For Yuval's students: detailed description of the L100 in R ex - from the recitation today (14.06) is at:  L100

June 20, 2007

The sixth (and last) assignment will be given on June 28th with submission deadline of July 15th. We will put its solution on the site before the exam, but you probably won't get your graded exercises before the exam.

July 2nd, 2007

Detailed description of the "SubsetSum is in NPC" problem from the last recitation is at:  SubsetSum

July 15

NEW The insturction section of the coming exam at: insturction

July 15, 2007

Pre-exam recitation! There will be two pre-exam recitations. Notice that they are going to be exactly the same, i.e. there is no use in attending them both. Multiplicity is aimed for those who cannot attend one of them!
The first: Wed, July 18th at 16:00-17:30, at Lev Hall.
The second Thu., July 19th at 16:00-17:30, at Lev Hall.
Please double check the website on Tue. for possible updates.

July 22, 2007

Exam solution

August 1, 2007

Exam Remarks and Grades

Sep 20, 2007

Exam 'MOED-B' solution

Oct 7, 2007

'Moed-B' Grades

 

Homework Assignments

Assignment

Date Handed

Submission Deadline*

Solution

Remarks

 Assignment 1

March 1st

March 15th

 Solution 1

Notes

 Assignment 2

March 15th

March 29th

 Solution 2

1. Notes on Regular expressions vs. DFAs.

2. Notes on CFG pumping lemma.

 Assignment 3

April 2nd

May 31st

 Solution 3

Correction to question 4c: it should be 2|v|<|w|_2|v|+1

 Assignment 4

May 31st

June 21th

  Solution 4

Deadline postponed to June 21th

 Assignment 5

June 14

June 28th

  Solution 5

 

 Assignment 6

June 28

July 15

  Solution 6

 

Kindly hand in your solution directly to the grader's mail box (Schreiber366), no later than 23:59 (Israel time, not Fiji!)of the submission due day.

 

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. "Discrete Math" 
is recommended, though not required. 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.)
  • Definitive midterm exam date: Friday, April. 13. Material: Lectures 1-5, Chapters 0 to 2.
  • Midterm is closed books, 10 multiple choice questions. Duration 100 minutes.
  • Final exam on July 22nd, 2007. 3 hours, closed book exam, except for 2 double-sided pages.
  • Course grade = min(100,(0.1*assignment grade)+(0.9*final exam)+(0.1*midterm grade)).

      A passing grade in the final exam is a necessary condition for a passing grade in the course.


Course Timetable
(due to strikes of various origins, power cuts, attempted coups, shifting holidays, and other unforeseen probabilistic or deterministic events, the schedule and material of future lectures and recitations are tentative): 

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


 

Lecture

Date

 Subject
    

 Reference(s) 

Lecture Slides

Recitation
Topic

   1

28/2/07

Administratrivia. Finite automata. Regular languages. Closure properties: Union.

 Chapter 0.
 Chapter 1, Section 1.1

Introduction

Deterministic finite automata

Mathematical
background

DFAs

   2

    5/3; 7/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

            3 

  12/3; 14/3
 

Myhill-Nerode theorem (not in Sipser's book), and the pumping lemma for regular languages. Algorithmic questions for DFAs & NFAs.  Context Free Grammars. Ambiguity. Chomsky Normal Form.

Chapter 1, Sections 1.4,

Chapter 2, Section 2.1.

 

Lecture 3

Equivalence classes. Usages of the Myhill-Nerode theorem and the pumping lemma for DFA.

            4

  19/3; 21/3

Context free grammars. Chomsky normal form. Pumping Lemma for context free languages. Example for non CFG languages. Push Down Automata (PDA).

Chapter 2, Sections 2.1-2.3

    Lecture 4

Context Free Grammars and their pumping lemma.

            5

  26/3; #@

Non-determinism adds power to PDAs (not in book).

Equivalence of PDAs and CFGs. Closure Properties of CFLs. Algorithmic Aspects of PDAs and CFLs, DFAs and PDAs. Perspectives.

Chapter 2, Sections 2.2-2.3.

 

   Lecture 5

PDAs.

            6

 28/5; 30/5

Turing Machines and alternative Models of Computers
Non Deterministic TMs. What is an algorithm?
The Church-Turing Thesis.
The language classes R, RE and coRE.

Chapter 3, Sections 3.1-3.3

   Lecture 6


Slides 6-30
of Muli Safra

More TM examples.
TM with two sided infinite tape.

 

            7

 4/6; 6/6

David Hilbert's Tenth Problem.
Universal Turning machine.
The acceptance/halting problem is undecidable.

Diagonalization proofs.

Chapter 3, Section 3.3,

Chapter 4, Sections 4.1-4.2

  

 Lecture 7

Undecidability.

Computable functions

Reductions

            8

  8/6

 Friday

 9-11:30

Lev Hall

Computable functions. Reductions. Reducing A to B by mapping reductions. More undecidable languages.

Chapter 5, Sections 5.1, 5.3 

 

 

 Lecture 8

 

            9

 11/6; 13/6

Reductions; A mathematical example.

Undecidability by Rice Theorem.

Reduction Involving Controlled Execution (steppers).

RE-Completeness.
 Reductions by computation histories: 

"Does a PDA accept Sigma Star" is undecidable

Undecidable tiling, or domino  problems

Description Length/Kolmogorov Complexity. Undecidability of Kolmogorov Complexity. Turing Reductions.

Chapter 5, Sections 5.1, 5.3 

 

 

 

 

 

 Lecture 9

Reductions.
Usages of the Rice Theorem.
Configurations

Kolmogorov complexity

 

 


 The recursion theorem.

 Unrestricted Grammars.

 

 

 

The Recursion Theorem

 

 

          

         

          10

 

15/6

Friday

10-13

Dan David 001

 

Lecture + recitation

Time complexity - introduction. DTIME and NTIME. Dependency of time on models of computation. Representing integers (unary vs. binary). The classes P and NP: definitions and examples. Simulating NP machines on deterministic TMs. Polynomial time growth vs. exponential time growth.

 Chapter 5, 5.2. Chapter 6.

Chapter 7, Sections   
  7.1-7.2

 

 

 

 

 Lecture 10

RE  È co-RE

 

P, NP.

Polynomial reductions.

           11

 18/6; 20/6

Equivalence of NP to poly time verifiers. Examples: Hamiltonian path; Composites. Poly time reductions. NP completeness.

Poly time reductions: Examples.

The P vs. NP question.

 

 Chapter 7, Sections   
  7.3-7.5

 

 Lecture 11

NP-completeness.

NP-hardness. 

          
           12

 

 25/6; 27/6

 

Cook Levin Theorem: SAT is NP-complete (statement & sketch of proof). coNP and coNP-completeness. NP-hardness. 

Additional reductions: SAT to 3SAT; SAT to IP;

3SAT to HamPath.

Bounded A_TM is NP-Complete. Concluding remarks.

 Chapter 7, Sections   
  7.3-7.5
Chapter 10, Section 10.1, 10.2

 Lecture 12

 

Reduction from 3SAT to 
Hamiltonian path


Additional reductions

 

coNP

 



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

  • 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


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

Exams from previous years (and previous instructors) in Tel-Aviv Univ.  This includes Fall 2003/4 exams from my last year's course.
Mid-term exams from previous years (and previous instructors) in Tel-Aviv Univ. 

Other Interesting On-line Resources

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

      P,NP and Mathematics- a computational complexity perspective

Doron Zeilberger 77 opinions (and counting).

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