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: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 |
|
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 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 |
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 |
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 |
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. Non-Determinism 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.1-3.3 |
Fancy Slides 6-30 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.1-4.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.1-4.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 non-deterministic 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 Cook-Levin theorem: SAT is NP-complete. |
Chapter 7 |
|
Polynomial time reductions |
|
|
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 |
|
NP and co-NP; 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 On-line Resources
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".