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 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 |
|
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; |
|
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! |
|
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 2nd |
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 |
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 |
|
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. |
|
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 |
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. |
|
PDAs. |
|
6 |
28/5; 30/5 |
Turing Machines and alternative Models of Computers |
Chapter 3, Sections 3.1-3.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.1-4.2 |
|
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 |
|
|
|
9 |
11/6; 13/6 |
Reductions; A mathematical example. Undecidability by Rice Theorem. Reduction Involving Controlled Execution (steppers). RE-Completeness. "Does a PDA accept Sigma Star" is undecidable
|
Chapter 5, Sections 5.1, 5.3 |
|
Reductions.
|
|
|
|
|
|
|
|
|
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 |
|
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 |
|
NP-completeness. NP-hardness. |
|
|
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 |
|
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 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".