Home Page for CS510 (Fall 2009)

Schedule

• Tuesday, Thursday, 2:10pm--3:30pm in EPS 350.

Textbook

• Introduction to the Theory of Computation (2nd edition), by Michael Sipser. (We will mainly follow the 2nd and 3rd part of the book.)

Instructor: Dr. Binhai Zhu

• Office: EPS 355
• Office hours: Tue, Wed: 9-10am; Wed: 2-4pm (or by appointment)
• Email: bhz@cs.montana.edu
• Phone: X4836

Syllabus by lecture

• This is mostly the syllabus from 2008, watch out for changes!!!!!!!!
• I usually update the syllabus before/after each lecture --- mainly to help you go over the materials (especially after skipping a lecture).
• For those who are auditing the course without taking CS350, try to read through Chapter 0 during the first week.
• Sep 1 --- Turing machines, Church-Turing thesis (read page 137-159).
• Sep 3 --- Primitive recursive functions (read class notes).
• Sep 8 --- Decidable languages (read page 165-170).
• Sep 10 --- Decidable languages (read page 170-173). One-to-one and onto functions. The diagonalization method (read page 173-178). Not all func's are primitive recursive (read class notes). Ackermann's func is not primitive recursive (read class notes).
• Sep 15 --- Halting is undecidable (read page 179-181). A Turing-unrecognizable language (read page 181-182). Reducibility, A_TM <= HALT_TM (read page 187-189).
• Sep 17 --- Reducibility, A_TM <= FINITE_TM, A_TM <= 2_diff_TM, A_TM <= REGULAR_TM, A_TM <= E_TM (read page 189-192).
• Sep 22 --- E_TM <= EQ_TM (read page 189-192). Reduction via computation history (read page 193-198).
• Sep 24 --- Post Correspondence Problem (read page 199-201). Time complexity (read page 247-256). Review for Test 1.
• Sep 29 --- The class of P (read page 256-262). Review of dynamic programming.
• Oct 1 --- Test 1.
• Oct 6 --- Review of dynamic programming.
• Oct 8 --- The class of NP, the P vs NP question (read page 263-270).
• Oct 13 --- Polynomial time reducibility (read page 270-273). HC <= TSP, VC <= IS, Circuit SAT <= SAT. All problems in NP <= Circuit SAT (informally).
• Oct 15 --- VC <= IS <= Clique, Set Partition <= Rectangle Packing, 3SAT <= Vertex Cover.
• Oct 20 --- 3SAT <= Vertex Cover, Hamiltonian Path <= Gene Cluster.
• Oct 22 --- 3SAT <= Clique. Approximation algorithms (VC, geometric TSP).
• Oct 27 --- 3SAT <= Subset-Sum (read page 292-294). Approximation algorithms (MLUCP).
• Oct 29 --- 3SAT <= ZBD. Approximation algorithms (geometric TSP, diameter, MLUCP).
• Nov 3 --- Inapproximability proofs (TSP, 3-color).
• Nov 5 --- Test 2 (everything covered since Sep 24 up to the end of Oct 29 lecture).
• Nov 10 --- PSPACE problems (read page 303-305). Overview on Test 2.
• Nov 12 --- Savitch's theorem, PSPACE problems (read page 303-309). co-NP. Introduction to FPT algorithms.
• Nov 17 --- Introduction to FPT algorithms.
• Nov 19 --- Test 3 (everything covered since Nov 3).
• Nov 24 --- More polynomial reduction examples (IS <= mLCS).
• Nov 26 --- No class---Thanksgiving Holiday.
• Dec 1 --- Project presentations.
• Dec 3 --- Project presentations.
• Dec 8 --- Project presentations.
• Dec 10 --- Project presentations.

Tests (45%)

• CS510 - test 1 (Test 1 is scheduled on Oct 1, during regular class time.)
• CS510 - test 2 (Test 2 is scheduled on Nov 5, during regular class time.)
• CS510 - test 3 (Test 3 is scheduled on Nov 19, during regular class time.)

Assignments (40%)

• CS510 - assignment 1 (pdf) or CS515 - assignment 1 (ps) (Due: Sep 29, 2009.)
• CS510 - assignment 2 (pdf) or CS515 - assignment 2 (ps) (Due: Nov 3, 2009.)
• CS510 - assignment 3 (pdf) or CS515 - assignment 3 (ps) (Due: Nov 17, 2009.)

Project (15%)

Final Grade