CS486 - Teaching Material - Winter 2008

Lecture Contents

1. 1/3/2008: Presentation of the course. Review on Languages, Automata and Grammars. Informal description of a Turing Machine.


2. 1/8/2008: Turing Machines (TMs). Transition diagrams for TMs. Configurations. Accepting and Rejecting configurations. One-step relation. Sequences of configurations. Language recognized by a TM. Turing-Decidable Languages and Turing-Recognizable Languages. Programming techniques: storage in control and multiple tracks. Examples.


3. 1/15/2008: Variants of TMs and the problem of their equivalence. Multitape TMs. Time complexity of a TM. Nondeterministic TMs (NTMs). Computation of a NTM. Language recognized by a NTM.

Reference: HMU-8.3 and HMU-8.4 (see list of references in Syllabus)


4. 1/17/2008: TMs and Digital computers. Simulation of a computer with a multitape TM.

   Reference: HMU-8.6.2



5. 1/22/2008: Comparing running times of computers and Turing machines. Turing-recognizability vs Turing-decidability. Hilbert's tenth problem. The definition of algorithm. The Church Thesis.

   Reference: HMU-8.6.3 and S-3.3



6. 1/24/2008: Decidable problems concerning CFGs and DFAs. The Halting problem. Cantor's theorem and the diagonalization techniques. Existence of nonsolvable problems. The Halting problem is Turing-recognizable but not Turing-decidable.

   Reference: S-4



7. 1/29/2008: Reducibility. Mapping Reducibility.

   Reference: S-5



8. 1/31/2008: More on Mapping Reducibility. Updated Feb 3rd.

   Reference: S-5



9. 2/5/2008: Preparation to MT.

   Reference: S-5



10. 2/7/2008: MT1


11. 2/12/2008: Review of MT1. Introduction to the Recursion Theorem.


12. 2/14/2008: The Recursion Theorem. Self reference and self replication. The Theorem of Rice.


13. 2/19/2008: Decision Problems and Languages. Measuring complexity. Running time of DTMs and NTMs. Asymptotic notation.


14. 2/21/2008: The class P. Robustness of P. Examples of problems in P.

    Reference: S-7.1, S-7.2.



15. 2/26/2008: Polynomial time NTMs and the class NP. Efficient veriability. The P vs NP question. Example of problems in NP. Polynomial time reductions. Notion of NP-completeness. Statement of Cook's theorem. SAT and VC.


16. 2/28/2008: Proving NP-completeness. NP-completeness of IS.


17. 3/4/2008: NP-Completeness of CLIQUE, VC and Subset-Sum. NP-completeness of SAT: Cook's theorem: sketch of the proof.


18. 3/6/2008: Proof of Cook's Theorem. Preparation to the Final exam. Download Sample final.

Downloads

1. 2/14/2008: self


2. 2/14/2008: cs486-w-08-pj. Due on Thursday 2/21/2008 at the beginning of class.


3. 3/4/2008: cs486-w-08-sample-final.

Announcements

• 1/3/2008: There will be no class on Thursday 1/10/2008.


• 1/24/2008: MT1 will take place on February, Thursday 7th, 2008. sample mt, solutions to sample mt


• 2/12/2008: Office hours on Thursdays are canceled until the end of the quarter.

CSNS - Computer Science Network Services

Assignments and exams should be uploaded by the due date through the CSNS - Computer Science Network Services website. If you have never used this system before then follow the instructions for students.