Home Page for CSCI 538 (Fall 2017)
Schedule
- Tuesday, Thursday, 1:40pm--2:55pm in Barnard 323.
Textbook
- Introduction to the Theory of Computation (3rd edition), by Michael Sipser.
Instructor: Dr. Binhai Zhu
- Office: Barnard 355
- Office hours: Wed: 9:00-10:00am, 3:00-4:00pm (or by appointment)
- Email: bhz@montana.edu
- Phone: X4836
Syllabus by lecture
- This is mostly the syllabus from 2015, 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 CSCI 338, try to
read through Chapter 0 during the first week.
- Aug 29 --- Turing machines, Church-Turing thesis (read pages 165-187, 2nd edition: 137-159).
Handout (pdf)
- Aug 31 --- Primitive recursive functions (read class notes).
- Sep 5 --- Decidable languages (read pages 193-198, 2nd edition 165-171).
- Sep 7 --- 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 12 --- 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).
- Sep 14 --- A Turing-unrecognizable language (read pages 209-210, 2nd edition 181-182).
Reducibility, sorting <= convex hull.
A_TM <= HALT_TM, A_TM <= FINITE_TM
(read pages 216-218, 2nd edition 188-191).
- Sep 19, 21 --- A_TM <= E_TM, A_TM <= REGULAR_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 26 --- Time complexity (reads pages 275-281, 2nd edition 247-253). The 3SUM problem.
- Sep 28 --- Review of dynamic programming (matrix chain multiplication).
- Oct 3 --- The class of P (read pages 284-289, 2nd edition 256-261).
Review of dynamic programming (read pages 290-291, 2nd edition 262-263).
- Oct 5 --- The class of NP (read pages 292-296, 2nd edition 264-268).
- Oct 10 --- NTM (read pages 283-284, 2nd edition 255-256).
k-tape TM (read page 282, 2nd edition 254).
- Oct 12 --- Test 1.
- Oct 17--- Polynomial time reducibility (read pages 299-304, 2nd edition 270-276).
The P vs NP question. HC <= TSP. VC <= IS, VC <= Clique, IS <= Clique.
- Oct 19 --- IS <= Partial Vertex Cover.
3SAT <= Vertex Cover (read pages 312-313, 2nd edition 284-285).
- Oct 24 --- 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).
- Oct 26 --- 3SAT <= Subset-Sum (read pages 320-322, 2nd edition 292-294).
Pseudo-polynomial time algorithm for Subset-Sum. Approximation algorithm for VC.
- Oct 31 --- Approximation algorithms (factor-2 and factor-1.5 approximation for geometrio TSP). Turing reduction.
- Nov 2 --- Co-NP. Inapproximability proofs (TSP). 3SAT <= ZBD. L-reduction.
- Nov 7,9 --- PSPACE problems, Savitch's theorem (read pages 331-337, 2nd edition 303-309).
- Nov 9 --- More reduction examples, mLCS.
- Nov 14 --- FPT: algorithms, hardness, approximation.
- Nov 16 --- Preview for Test 2.
- Nov 21 --- Test 2.
- Nov 28 --- Project presentations.
- Nov 30 --- Project presentations.
- Dec 5 --- Project presentations.
- Dec 7 --- Project presentations.
Tests (40%)
-
CS538 - test 1
(Test 1 is scheduled on Oct 12, during regular class time. Contents: Everything covered before "NP-complete problem examples" covered on Oct 3. Cheatsheet: 1 letter-sized cheatsheet, 2 sides, is allowed.)
-
CS538 - test 2
(Test 2 is scheduled on Nov 21, during regular class time. Contents: Everything covered since "polynomial-time reduction examples" covered on Oct 5 up to Nov 16, not including approximation, L- and Turing reductions. Cheatsheet: 1 letter-sized cheatsheet, 2 sides, is allowed.)
Assignments (40%)
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 four days for presentations are arranged: Nov 28,30, Dec 5,7.
Nov 28, Saidur Rahman: --- "Clouding computing is NP-complete".
Nov 28, Susmit Sengupta: --- Using cell phone keyboards is NP-hard.
Nov 28, Amy Peerlinck: --- Natural language processing and NP-completeness.
Nov 30, Shriyansh Kothari: --- Using genetic algorithms to solve NP-complete problems.
Nov 30, Rituparna Halder: --- Energy-aware routing in data center network.
Nov 30, Rohan Khante: --- Scrabble is PSPACE-complete.
Nov 30, Joe DeBruycker: --- Complexity of Bayesian inference.
Nov 30, Lucy Williams: --- Edit distance cannot be computed in strongly subquadratic time.
Dec 5, Taylor Heinecke: --- Inference complexity in continuous time Bayesian networks.
Dec 5, Anika Prima: --- On the construction of Data aggregation tree with minimum energy cost in wireless sensor networks: NP-completeness and approximation algorithm.
Dec 5, Alex Huleatt: --- Multi-agent path planning.
Dec 5, Fenil Patel: --- The critical-sqaure-grid coverage problem in wireless snsor network is NP-complete.
Dec 7, Hongchuan Wang: --- Quell.
Dec 7, Seraj Mostafa: --- QoS-aware replica placement for content distribution --- an NP-complete problem.
Dec 7, Prashanta Saha: --- Computational complexity in adaptive testing strategies.
Dec 7, David Rice : --- AC unification is NP-complete.
Dec 7, Neil Walton: --- Searching the k-change neighborhood for TSP is W[1]-hard.
Dr. Binhai Zhu
Professor
Gianforte School of Computing
Montana State University
Bozeman, MT 59717
Email: bhz@montana.edu
Office: Barnard 355
Phone: 406-994-4836