School of Computer Science, Tel Aviv University 

Fall 2004-2005


Computational Models

(or more accurately - introduction to the theory of computation)

 

  0368.2200

http://www.cs.tau.ac.il/~bchor/CM05/compute.html

Mondays 13:00-16:00, Dach Lecture Hall

Lecturer: Benny Chor

Teaching Assistant: Gadi Kimmel

 

 

 Solutions to Moed A Exam  (scanned, 5MB)

Moed A Grades   Moed B Grades

 

(Remark: Same factor applied to Moed A and B)

Contact Info:
 

 

 

Email

Phone

Office

Office Hours

Lecturer

Prof. Benny Chor

benny@cs.tau.ac.il

640-5977

Schreiber  223

By  e-appointment

Teaching Assistant

Dr. Gad Kimmel 

   kgad@tau.ac.il

640-5394

Schreiber  011

By  e-appointment 

Grader (Bodek)

Alexander Medvedovsky

  medv@post.tau.ac.il

 

 Mail Box 400

By  e-appointment


 

 

Course Outline

The course deals with fundamental questions of computer science:

  • What is a computer ?
  • What can computers do (and what can they not do)?
  • Why are some problems computationally hard, while very similar ones are computationally easy?

 

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.
Students from other disciplines are encouraged to contact the instructor.
 

Course Requirements and Important Dates:

  • 6 homework assignments. (Best 5 out of 6 will be part of the grade. Only parts of each assignment will be graded.)
  • Midterm exam: Friday, Nov. 26. Material: Lectures 1-5, Chapters 0 to 2. Grades.
  • Final exam. Closed book except for 4 double-sided pages of your choice.


Course Timetable (schedule and material of future lectures are tentative): 

The course consists roughly of three parts:  Lectures 1-5 deal with languages and automata theory, lectures 5-10 with computability theory, and lectures 11-14 with complexity theory.


 

Lecture
___________

Date
______

 Subject
     ______________________________________

 Reference(s) 
__________________

Recitation
___________

   1

18/10/04

 Administrativia and introduction.  Mathematical terminology.  Finite automata and regular languages - examples.

 Chapter 0.
 Chapter 1, Section 1.1

Mathematical
background

   2

25/10

Nondeterminism finite state automata; Regular expressions;
Equivalence of regular languages and regular expressions.

Chapter 1, Sections 1.1-1.3

  DFAs

            3 

   1/11
 

The pumping lemma. Non regular languages.
Context free grammars. Chomsky normal form.

Chapter 1 and 2, Sections 1.4, 2.1, 2.2

Additional closure properties of regular languages

            4

   8/11

Push down automata. NonDeterminism adds power to PDAs. Equivalence of PDAs and CFGs. Pumping lemma for context free languages.

Chapter 2, Sections 2.2-2.3

Examples: Pumping lemma for (non) regular languages.  CFL~PDA

            5

  15/11

NonDeterminism adds power to PDAs (revised); Closure properties of CFLs; Algorithmic Aspects of PDAs and CFLs. Turing machines.

Chapter 2, Sections 2.2-2.3. Chapter 3, Section 3.1

Examples: Pumping  lemma for PDAs.

            6

  22/11

Turing machines. Algorithms. Multi-Tape TMs; RAMs; Nondeterministic TMs.  Church-Turing thesis. 
Printer friendlier version.

Chapter 3, Sections 3.1-3.3

More TM examples.
TM with two sided infinite tape.

            7

  29/11

Hilbert's tenth problem.  Encodings. Universal TM. Diagonalization.Proof of undecidability of the halting problem by diagonalization.
Printer friendlier version.

Chapter 3, Section 3.3,

Chapter 4, Sections 4.1-4.2

More TM examples.
Addition on TM.

            8

  6/12

Computable functions. Reductions. Proofs of undecidability via reductions by computation histories and by mapping reductions.

Printer friendlier version.

Chapter 5, Sections 5.1, 5.3 

 

            9

  13/12

Rice Theorem. Kolmogorov Complexity. RE completeness.
Turing reductions. Godel incompleteness theorem.
Printer friendlier version.

Chapter 6, 6.2, 6.3, 6.4.

 

          

         

          10

 

  

 20/12

Undecidable tiling, or domino,  problems

(old fashioned chalk dust presentation)
 Recursion theorem  (printable version)

 Unrestricted Grammars - David Galles slides (printable version)

Chapter 5, 5.2

 

Chapter 6, 6.1

Rice Theorem

 

Kolmogorov complexity

           11

  27/12

Time complexity – introduction. DTIME and NTIME.

Time dependence on models. The class P.  (printable version)

 Chapter 7, Sections 
  7.1- 7.2

The Recursion Theorem

          
           12

 

 3/1/2005

The class NP.  Polynomial time Reductions. NP completeness, Cook-Levin theorem: SAT is NP-complete.
(printable version)

 Chapter 7, Sections   
  7.3-7.4

Additonal languages in NP

 

           13

   10/1

Additional Reductions (IP, HamPath, Bounded Tiling).
On search vs. decision problems. Approximation Algorithms.   (printable version)

Reduction from 3SAT to Hamiltonian path (a separate ps file)

 Chapter 7, Sections   
  7.4-7.5
Chapter 10, Section 10.1


Additional reductions:
3 coloring and set cover
are NP complete

                             14

              17/1

Approaches to dealing with computational intractability:
1) fixed parameter algorithms, 2) randomization. (13MB file!).  (printable version)

Chapter 10, Section 10.2.                          The view from Mars

Review of course material.


Presentations are based on those prepared by Prof. Maurice Herlihy for a similar course given at Brown University.



Problem Sets

Problem Set 1 -  Published Oct. 18, due Nov. 9, 2004.   Partial solution.

Problem Set 2 -  Published Nov. 9, due Nov. 23, 2004.   Partial solution.

Problem Set 3 -  Published Dec. 1, due Dec. 16, 2004.   Partial solution.              

Problem Set 4 -  Published Dec. 17, due Dec. 30, 2004.  Partial solution. 

Problem Set 5 -  Published Jan. 6, due Jan. 20, 2005.   Complete solution.

 

Early Printer Friendly Handouts

 http://www.cs.tau.ac.il/~tavorhai/CompuModels.htm  (courtesy of  Haim Tavor).


Administrativia

Each week (including 1st week) there will be a 3 hours lecture, preceeded 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 due two weeks after publishing. Grading will apply to part of the problems in each assignment.   Solving assignments independently is key to understanding the material and to success in exams, and is strongly encouraged. Research done at the Technion shows that outright copying may be harmful to your health.

 

Grade:  10-15% based on homework assignments, 20-25% based on midterm, 60-70% on final exam. Midterm component weighted only if it contributes  non-negatively to final outcome.

 

Textbook

 Introduction to the Theory of Computation, M. Sipser,  PWS Publishing Co.,  1997.

 

Reference Books

  • Computational Complexity, C. Papadimitriou, Addison-Wesley Publishing Co.,  1994.
  • Elements of the Theory of Computation, H. Lewis and C. Papadimitriou, Prentice-Hall, 1981.
  • Introduction to Automata Theory, Languages, and Computation, J. Hopcroft and J. Ullman, Addison-Wesley Publishing Co., 1979.

 

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.
A virtual Turing machine you can possibly run.

 

Other Interesting On-line Resources