- Tuesday, Thursday, 2:10pm--3:30pm in Gaines 148.

- Introduction to the Theory of Computation (3rd edition), by Michael Sipser.

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

- This is mostly the syllabus from 2014, 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 25 --- Turing machines, Church-Turing thesis (read pages 165-187, 2nd edition: 137-159).
- Aug 27 --- Primitive recursive functions (read class notes).
- Sep 1 --- Decidable languages (read pages 193-198, 2nd edition 165-171).
- Sep 3 --- Decidable languages (read pages 199-201, 2nd edition 171-173). One-to-one and onto functions. The diagonalization method (read pages 202-206, 2nd edition 174-178).
- Sep 8 --- Not all func's are primitive recursive (read class notes). Ackermann's func is not primitive recursive (read class notes). Halting is undecidable (read pages 207-209, 2nd edition 179-181). A Turing-unrecognizable language (read pages 209-210, 2nd edition 181-182). Reducibility, sorting <= convex hull.
- Sep 10 --- Reducibility, sorting <= convex hull, A_TM <= HALT_TM, A_TM <= FINITE_TM, A_TM <= REGULAR_TM (read pages 216-219, 2nd edition 188-191).
- Sep 15, 17 --- A_TM <= E_TM, E_TM <= EQ_TM (read pages 218-220, 2nd edition 190-192). Map reduction (read pages 234-238, 2nd edition 206-210). Reduction via computation history (read pages 221-224, 2nd edition 193-196). Post Correspondence Problem (read pages 227-228, 2nd edition 199-200).
- Sep 17 --- Time complexity (reads pages 275-281, 2nd edition 247-253). The 3SUM problem.
- Sep 22, 24 --- The class of P (read pages 284-289, 2nd edition 256-261). Review of dynamic programming (matrix chain multiplication). Review of dynamic programming (read pages 290-291, 2nd edition 262-263).
- Sep 24 --- VC <= IS, VC <= Clique, IS <= Clique.
- Sep 29 --- The class of NP (read pages 292-296, 2nd edition 264-268). NTM definition. k-tape TM (read page 282, 2nd edition 254). IS <= Partial Vertex Cover.
- Oct 1 --- NTM (read pages 283-284, 2nd edition 255-256). Polynomial time reducibility (read pages 299-304, 2nd edition 270-276). The P vs NP question. HC <= TSP.
- Oct 6 --- NP-completeness (read pages 299-304, 2nd edition 271-276). All problems in NP <= Circuit SAT (informally). Circuit SAT <= SAT. SAT <= 3SAT (read pages 310-311, 2nd edition 282-283). 3SAT <= Vertex Cover (read pages 312-313, 2nd edition 284-285).
- Oct 8 --- Test 1.
- Oct 13 --- 3SAT <= Subset-Sum (read pages 320-322, 2nd edition 292-294). Pseudo-polynomial time algorithm for Subset-Sum. Approximation algorithm for VC.
- Oct 15 --- Approximation algorithms (factor-2 and factor-1.5 approximation for geometrio TSP).
- Oct 20 --- Greedy approximation for Partial VC. Co-NP.
- Oct 22 --- Inapproximability proofs (TSP). 3SAT <= ZBD. L-reduction.
- Oct 27 --- PSPACE problems, Savitch's theorem (read pages 331-337, 2nd edition 303-309). Turing reduction.
- Oct 29, Nov 3 --- FPT: algorithms, hardness, approximation.
- Nov 3 --- Preview for Test 2.
- Nov 5 --- Test 2.
- Nov 10 --- More reduction examples, mLCS.
- Nov 12 --- Project presentations.
- Nov 17 --- Project presentations.
- Nov 19 --- Project presentations.
- Nov 24 --- Project presentations.
- Dec 1,3 --- No class.

- CS538 - test 1 (Test 1 is scheduled on Oct 8, during regular class time. Contents: Everything covered before "polynomial-time reduction examples" covered on Sep 24. Cheatsheet: 1 letter-sized cheatsheet, 2 sides, is allowed.)
- CS538 - test 2 (Test 2 is scheduled on Nov 5, during regular class time. Contents: Everything covered since "polynomial-time reduction examples" covered on Sep 24 up to Oct 29, not including approximation, L- and Turing reductions. Cheatsheet: 1 letter-sized cheatsheet, 2 sides, is allowed.)

- CS538 - assignment 1 (pdf) (Due: Sep 15, 2015.)
- CS538 - assignment 2 (pdf) (Due: Oct 1, 2015.)
- CS538 - assignment 3 (pdf) (Due: Oct 20, 2015.)
- CS538 - assignment 4 (pdf) (Due: Nov 3, 2015.)

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