Home Page for CSCI 538 (Fall 2015)

Schedule

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

Textbook

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

Instructor: Dr. Binhai Zhu

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

Syllabus by lecture

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

Tests (40%)

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

Assignments (40%)

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

Project (20%)

Class Averages for Each Assignment/Test