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

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

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

- 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.

- 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.)

- 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.)

Dr. Binhai Zhu

Professor

Department of Computer Science

Montana State University

Bozeman, MT 59717

Email: bhz@cs.montana.edu

Office: EPS 355

Phone: 406-994-4836

Fax: 406-994-4376