Home Page for CS538 (Fall 2011)

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: 3-4pm (or by appointment)
• Email: bhz@cs.montana.edu
• Phone: X4836

Syllabus by lecture

• This is mostly the syllabus from 2010, 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.
• Aug 30 --- Turing machines, Church-Turing thesis (read page 137-159).
• Sep 1 --- Primitive recursive functions (read class notes).
• Sep 6 --- Decidable languages (read page 165-170).
• Sep 8 --- Decidable languages (read page 170-173). One-to-one and onto functions. The diagonalization method (read page 173-178).
• Sep 13 --- Not all func's are primitive recursive (read class notes). Ackermann's func is not primitive recursive (read class notes). Halting is undecidable (read page 179-181). A Turing-unrecognizable language (read page 181-182). Reducibility, sorting <= convex hull.
• Sep 15 --- Reducibility, A_TM <= HALT_TM, A_TM <= REGULAR_TM, A_TM <= E_TM, E_TM <= EQ_TM (read page 189-192).
• Sep 20 --- A_TM <= 2_diff_TM. Reduction via computation history (read page 193-198). Post Correspondence Problem (read page 199-201).
• Sep 22 --- Time complexity (read page 247-251). The class of P (read page 256-262). Review of dynamic programming (matrix chain multiplication).
• Sep 27 --- Review of dynamic programming (read 262-263). k-tape TM and NTM (read page 254-256).
• Sep 29 --- The class of NP, the P vs NP question (read page 263-270). HC <= TSP
• Oct 4 --- Test 1.
• Oct 6 --- Stibitz meeting. Review for Test 1.
• Oct 11 --- Polynomial time reducibility (read page 270-273). VC <= IS, VC <= IS <= Clique, Set Partition <= Rectangle Packing, 3SAT <= Vertex Cover (read page 284-285).
• Oct 13 --- Hamiltonian Path <= Gene Cluster. NP-completeness (read page 271-273). All problems in NP <= Circuit SAT (informally). Circuit SAT <= SAT. SAT <= 3SAT (read page 282-283).
• Oct 18 --- Gene Cluster-2 is in NP. 3SAT <= Clique (read page 274-275). Approximation algorithms (VC). Approximation algorithms (geometric TSP).
• Oct 20 --- 3SAT <= Subset-Sum (read page 292-294). Turing reductions.
• Oct 25 --- Approximation algorithms (geometric TSP, diameter). Inapproximability proofs (TSP).
• Oct 27 --- Test 2.
• Nov 1 --- High-level description of NP, etc (covered by Rocky).
• Nov 3 --- Inapproximability proofs (3-color). 3SAT <= ZBD.
• Nov 8 --- co-NP. Introduction to FPT algorithms.
• Nov 10 --- Introduction to FPT algorithms. PSPACE problems, Savitch's theorem (read page 303-309).
• Nov 15 --- More polynomial reduction examples (VC <= mLCS, IS <= mLCS).
• Nov 17 --- Approximation algorithms (MLUC, MLUCP).
• Nov 22 --- Review for Test 3, question-answering.
• Nov 24 --- No class---Thanksgiving Holiday.
• Nov 29 --- Test 3 (everything covered since Oct 25).
• Dec 1 --- Project presentations.
• Dec 6 --- Project presentations.
• Dec 8 --- Project presentations.

Tests (45%)

• CS538 - test 1 (Test 1 is scheduled on Oct 4, during regular class time.)
• CS538 - test 2 (Test 2 is scheduled on Oct 27, during regular class time.)
• CS538 - test 3 (Test 3 is scheduled on Nov 29, during regular class time.)

Assignments (40%)

• CS538 - assignment 1 (pdf) or CS538 - assignment 1 (ps) (Due: Sep 27, 2011.)
• CS538 - assignment 2 (pdf) or CS538 - assignment 2 (ps) (Due: Oct 25, 2011.)
• CS538 - assignment 3 (pdf) or SOLUTION (pdf) (Due: Nov 22, 2011.)

Project (15%)

Final Grade