Cm08.htm

Monday 13:00-16:00, Dan-David 001

Recitations:

Tuesday 13:00-14:00, Schreiber 008

Tuesday 14:00-15:00, Schreiber 008

Wednesday 16:00-17:00, Schreiber 008

Instructor:
Prof. Nachum Dershowitz

Teaching Assistant:
Ricky Rosen

Exercise Grader:

Roza mailbox: 276

General Announcements:

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

Class Bulletin-Board:

Date	Announcement
23.10.2007	There is recitation today
29.10.2007	There will not be any more recitations before the first lecture takes place
20.01.2008	The strike is finally over. There is a lecture tomorrow
24.01.2008	Submission deadline of assignment no. 1 is postponed to Wed.13.02.08
31.01.2008	All 12 lecture notes: Course notes
03.02.2008	Makeup recitation on Friday 08.02.08 13:10-14:00 Dan David 001
19.02.2008	There will be no makeup recitations on Fridays
04.03.2008	Question 5 in ex3 should be: For each language determine if it is in R, RE\R, coRE\R or neither.
26.03.2008	Review class on Sunday, April 27th in Orenstein 103 at 10:00
06.04.2008	The instruction section of the coming exam at: instruction
28.04.2008	Solutions to the exam: here
04.05.2008	Exam Remarks and Grades

Home Assignments:

Assignment	Handed Date	Submission Deadline^*	Solution
Assignment 1	22.01.2008	13.02.2008	Solution 1
Assignment 2	12.02.2008	27.02.2008	Solution 2
Assignment 3	25.02.2008	12.03.2008	Solution 3
Assignment 4	11.03.2008	26.03.2008	Solution 4
Assignment 5	25.03.2008	08.04.2008	Solution 5

^* Please submit the exercise directly to the grader mail box, until the hour 23:59 of the submission deadline.

Homework submission is in singles only. External sources (books, journal articles, web pages) can be used but should be clearly quoted.
Solving assignments independently is the key to understanding the material and to success in exams, and is strongly encouraged.

Course Plan:

Lecture	Subject	Handouts	References	Recitations
0			Chapter 0. Chapter 1	Mathematical background. DFA.
1	Adminisrativia and introduction. Finite automata and regular languages. Nondeterminism finite state automata. The pumping lemma.	Handout 1 (pdf) Handout 1 (ppt)	Chapter 0. Chapter 1, Section 1.1. Chapter 1, Sections 1.1-1.3.	NFA
2	Equivalence of regular languages and regular expressions. Myhill-Nerode theorem. Non regular languages; Regular expressions.		Chapter 1 and 2, Sections 1.4, 2.1, 2.2.	The pumping lemma; Equivalent classes.
3	Context free grammars. Chomsky normal form. Linear grammars. Pumping lemma for context free languages.	Handout 2 (pdf)	Chapter 2, Sections 2.2-2.3.	Equivalent classes; CFG
4	Turing machines. Algorithms. Multi-Tape TMs; Nondeterministic TMs. Church-Turing thesis.	Handout 4 (pdf)	Chapter 3, Sections 3.1-3.3.	TM
Computability
5	Hilbert's tenth problem. Encodings. Universal TM. Diagonalization.Proof of undecidability of the halting problem by diagonalization. Rice Theorem. Kolmogorov Complexity. RE completeness. Turing reductions. Godel incompleteness theorem.	Handout 5 (pdf)	Chapter 3, Section 3.3. Chapter 4, Sections 4.1-4.2
6	Computable functions. Reductions. Proofs of undecidability via reductions by computation histories and by mapping reductions.	Handout 6 (pdf) Handout 7 (pdf)	Chapter 5, Sections 5.1, 5.3.	The class R. Reductions. Rice Theorem.
7	Undecidable tiling, or domino, problems. Recursion theorem. Unrestricted Grammar.		Chapter 6, 6.2, 6.3, 6.4.	The class RE. Mapping reductions.
8	TBA		Chapter 5, 5.2. Chapter 6, 6.
9	Time complexity introduction. DTIME and NTIME. Time dependence on models. The class P.		Chapter 7, Sections 7.1- 7.2.
Complexity
10	The class NP. Polynomial time Reductions. NP completeness, Cook-Levin theorem: SAT is NP-complete.		Chapter 7, Sections 7.3-7.4.
11	Additional Reductions (IP, HamPath, Bounded Tiling). On search vs. decision problems. Approximation Algorithms.		Chapter 7, Sections 7.4-7.5 Chapter 10, Section 10.1

Course Outline

The course deals with fundamental questions of computer science:

What is “computation”?
What is a computer?
Where does theory “meet” computation?

What can computers do?
What can they not do?

Why are some problems computationally hard, while very similar ones are computationally easy?
Is verifying the correctness of a solution to a problem easier than solving it? (not as easy at it sounds)
Is there a good reason to prove theorems?

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:

5 homework assignments. (Best 3 out of 5 will be part of the grade.)

Midterm exam date: Canceled.
Final exam on date: 28.04. 3 hours, closed book exam, except for 2 double-sided pages.
Course grade =TBA, most likely: min(100 , (0.1*assignment grade)+(0.95*final exam) ).

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

References:

Sipser, Introduction to the Theory of Computation.
Hopcroft and Ullman, Introduction to Automata Theory, Languages, and Computation.

Other Related Books:

Papadimitriou, Computational Complexity.
Corman, Introduction to Algorithms.
Jones, Computability and Complexity.
Davis, Segal and Weyuker, Computability, Complexity, and Languages (2d ed).
Otomatim vesafot formaliot, Open University, vols. A and B.
Lewis and Papadimitriou, Elements of the Theory of Computation (2nd. ed.).
David Harel, Algorithmics- The spirit of computing, ch. 8-9.
A. Ben-Amram, Algorithm and Programs: Introduction to Programming Languages, Computation and Complexity (Hebrew).