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

## Project (20%)

• You will need to participate in a course project. Choose a topic in computability/complexity theory and conduct an independent study. The evaluation is based on the project report as well as the presentation. The following five days for presentations are arranged (note that I am gone the week of Nov 30---Dec 4).
• Nov 12, Jici Huang: --- MIS on 2-interval and 2-track interval graphs.
• Nov 12, Peng Zou: --- Independent DS has no FPT approximation.
• Nov 17, Letu Qingge: --- DS on 2-interval and 2-track interval graphs.
• Nov 17, Rollie Goodman: --- Using cell phone keyboards in NP-hard.
• Nov 17, Killian Smith: --- AC unification is NP-complete.
• Nov 17, Sam Mirka: --- Maximum-lifetime data gathering tree in sensor networks: NP-completeness and approximation algorithm.
• Nov 17, Manasa Boosa: --- NP-completeness of list coloring and precoloring extension on the edges of planar graphs.
• Nov 19, John McIntosh: --- Energy-aware routing in data center network.
• Nov 19, Tao Huang: --- Searching the k-change neighborhood for TSP is W[1]-hard.
• Nov 19, Aidan Bickford: --- Edit distance cannot be computed in strongly subquadratic time.
• Nov 19, Monica Thornton: --- Inference complexity in continuous time Bayesian networks.
• Nov 24, Kathryn Manning and Leah Thompson: --- Scrabble is PSPACE-complete.
• Nov 24, Janet Rounds: --- Quell.
• Nov 24, Yi Xu: --- The critical-square-grid coverage problem in wireless sensor networks is NP-complete.
• Nov 24, Asha Nalluri: --- Using DNA to solve NP-complete problems.
• Nov 24, Vasudev Ravula: --- "Clouding computing is NP-complete".
• Dec 7 (in CS Conference Room), Faisal Khan: --- Capacity of wireless networks.
• ## Class Averages for Each Assignment/Test

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