0368.2200
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:
Class BulletinBoard:
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:0016:00. Location: Orenshtein 103. 
March 24, 2007 
Mid term exam will take place (as planned) on Friday, April 13. Material includes Lectures 15, Chapters 02 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:0015: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 contextfree 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 
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:0019:00, in the following three locations: (1) Melamed hall; 
April 12, 2007 
Some notes regarding questions from the office hours on 1142007. 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 8^{th}, 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 28^{th} with submission deadline of July 15^{th}. 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 
Preexam recitation! There will be two preexam 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! 
July 22, 2007 

August 1, 2007 

Sep 20, 2007 

Oct 7, 2007 
Homework Assignments
Assignment 
Date Handed 
Submission Deadline^{*} 
Solution 
Remarks 
March 1st 
March 15th 

March 15th 
March 29th 

April 2^{nd} 
May 31st 
Correction to question 4c: it should be 2^{v}<w_2^{v+1} 

May 31st 
June 21th 
Deadline postponed to June 21th 

June 14 
June 28th 


June 28 
July 15 

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:
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.
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.
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):
Lecture 
Date 
Subject

Reference(s) 
Lecture Slides 
Recitation 
1 
28/2/07 
Administratrivia. Finite automata. Regular languages. Closure properties: Union. 
Chapter 0. 
Mathematical DFAs 

2 
5/3; 7/3 
NonDeterministic Finite Automata (NFA). Closure
properties of Regular Languages. Regular expressions and their equivalence
with finite automata via generalized
NFAs 
Chapter 1, Sections 1.11.3 

NFAs. Regular expressions. closure properties of regular languages 
3 
12/3; 14/3 
MyhillNerode 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. 

Equivalence classes. Usages of the MyhillNerode 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.12.3 
Context Free Grammars and their pumping lemma. 

5 
26/3; #@ 
Nondeterminism 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.22.3. 

PDAs. 
6 
28/5; 30/5 
Turing Machines and alternative Models of Computers 
Chapter 3, Sections 3.13.3 

More TM examples. 
7 
4/6; 6/6 
David Hilbert's Tenth Problem. Diagonalization proofs. 
Chapter 3, Section 3.3, Chapter 4, Sections 4.14.2 

Undecidability. Computable functions Reductions 
8 
8/6 Friday 911:30 Lev Hall 
Computable functions. Reductions. Reducing A to B by mapping reductions. More undecidable languages. 
Chapter 5, Sections 5.1, 5.3 


9 
11/6; 13/6 
Reductions; A mathematical example. Undecidability by Rice Theorem. Reduction Involving Controlled Execution (steppers). RECompleteness. "Does a PDA accept Sigma Star" is undecidable

Chapter 5, Sections 5.1, 5.3 

Reductions.







10 
15/6 Friday 1013 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 

RE È coRE 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 

NPcompleteness. NPhardness. 

25/6; 27/6 
Cook Levin Theorem: SAT is NPcomplete (statement & sketch of proof). coNP and coNPcompleteness. NPhardness. Additional reductions: SAT to 3SAT; SAT to IP; 3SAT to HamPath. Bounded A_TM is NPComplete. Concluding remarks. 
Chapter 7,
Sections 

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).
Other Online Resources
Last year course
David Galles course at USF: http://www.cs.usfca.edu/~galles/cs411/
Exams from
previous years (and previous instructors) in TelAviv Univ. This includes
Fall 2003/4 exams from my last year's course.
Midterm
exams from previous years (and previous instructors) in TelAviv Univ.
Other Interesting Online 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".