School of Computer Science, Tel Aviv University
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:0016:00, Orenshtein 103, with two recitations on Wednesday
(b) Wednesday 10:0013:00, Orenshtein 111, with two recitations on Thursday
Group (a) Lecturer: Prof. Benny Chor (benny AT cs.tau.ac.il, appointments by email)
Group (b) Lecturer: Dr. Miri Priesler (mirip AT tau.ac.il, appointments by email)
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 BulletinBoard:
Date 
Announcement 
5/3/2009 
The midterm is tentatively scheduled to Tuesday, April 7^{th} (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 7^{th}) 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 13 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:0016: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 45 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 
9/3/09 
26/3/09 , 18:00 


27/3/09 
19/4/09 , 12:00 


23/4/09 
7/5/09, 18:00 
updated 28/4/09 

8/5/09 
21/5/2009, 18:00 


28/5/09 
Sunday 14/6, 18:00 


9/6/09 
Wednesday 1/7, 18:00. 

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 CookLevin theorem (lecture 12). Randomized algorithms (lecture 14).
Course Timetable : The course roughly consists of
three parts: Lectures 15 deal with languages and automata
theory, lectures 610 with computability theory, and lectures 1113
with complexity theory.
Lecture(group a) 
Date 
Subject 
Reference(s) 
Lecture Slides (pdf) 
Recitation 
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 
Recitation 04/03/09: Video is missing 
2 
9/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 
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 
Additional closure properties of regular languages 

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 
CFL 

5 
30/3 
Equivalence of Context Free Grammars and Push down automata. NonDeterminism adds power to PDAs. Chomsky normal form of CFGs. More CFL closure properties. 
Chapter 2, Sections 2,2, 2.3 
Pumping lemma for CFL. 

6 
20/4 
Turing Machines and alternative Models of Computers Non Deterministic TMs. 
Chapter 3, Sections 3.13.3 
Fancy Slides 630 by Muli Safra 
Turing machine examples. RAM 

7 
27/4 
What is an algorithm? Hilbert's tenth problem The halting problem 
Chapter 3, Section 3.3 Chapter 4, sections 4.14.2 

No recitation, Independence day 

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.14.2 Chapter 5, sections 5.1 
Mapping reductions 

9 
11/5 
Reductions among languages Mapping reductions 
Chapter 5, sections 5.1, 5.3 
More mapping reductions 

10 
18/5 
Rice theorem Reductions using computation histories Unrestricted grammars 
Chapter 5, sections 5.1, 5.3 
(slightly revised May 19) 
Rice thm; tiling problem 

11 
25/5 
Intro to complexity theory: Deterministic and nondeterministic time classes; P and NP. Verifiability. 
Chapter 7. 
Verifiers (NP) 

12 
1/6 
NP and coNP Poly time reductions: Definition and examples Sketch of the proof CookLevin theorem: SAT is NPcomplete. 
Chapter 7 

Polynomial time reductions 

13 
8/6 
More poly time reductions and NP completeness languages: 3SAT to DirHamPath. SAT to IP. 3SAT to 3COL. Bounded A_TM is NPComplete. Decision, search, and optimization problems. A 2 approximation algorithm for vertex cover. 
Chapter 7 and 10 

NP and coNP; more polynomial time reductions 

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 

Approximation algorithms 
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 Online Resources
David Galles course at USF: http://www.cs.usfca.edu/~galles/cs411/
Midterm exams from previous years (and previous instructors) in TelAviv Univ.
Other Interesting Online 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".