Home Page for CSCI 538 (Spring 2024)
Schedule
- Lecture: Tuesday, Thursday 8:00 - 9:15 am in AJM Johnson 251.
Textbook
- Introduction to the Theory of Computation (3rd edition), by Michael Sipser.
Instructor: Dr. Binhai Zhu
- Email: bhz@montana.edu
- Phone: 994-4836
- Office Hours: Monday, 10am - 11am; Wednesday & Thursday, 9:30 am - 10:25 am, or
by appointment.
- Office Hours will generally be done physically, but could be arranged by appointment (say at 10:05am) in advance and virtually:
Virtual Location
- Physical Location: Barnard 355
Syllabus by lecture
- This is mostly the syllabus from 2022, 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.
- Jan 18 --- Turing machines, Church-Turing thesis (read pages 165-187, 2nd edition: 137-159).
Course overview (pdf) ,
TM definition, etc. .
- Jan 23 --- Primitive recursive functions (read class notes).
- Jan 25 --- Decidable languages (read pages 193-198, 2nd edition 165-171).
- Jan 30 --- 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).
- Feb 01 --- 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).
- Feb 06 ---
Reducibility, sorting <= convex hull.
A_TM <= HALT_TM, A_TM <= FINITE_TM, A_TM <= E_TM (read pages 216-218, 2nd edition 188-191).
- Feb 08 --- A Turing-unrecognizable language (read pages 209-210, 2nd edition 181-182).
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).
Post Correspondence Problem (read pages 227-228, 2nd edition 199-200).
- Feb 13 --- Reduction via computation history (read pages 221-224, 2nd edition 193-196).
- Feb 15 --- Time complexity (reads pages 275-281, 2nd edition 247-253). The 3SUM problem.
The Crystal Ball Problem (pdf)
- Feb 20 --- The class of P (read pages 284-289, 2nd edition 256-261).
Review of dynamic programming (matrix chain multiplication).
Handout (pdf) .
- Feb 22 --- Review of dynamic programming (read pages 290-291, 2nd edition 262-263).
Handout (pdf) .
- Feb 27 --- The class of NP (read pages 292-296, 2nd edition 264-268).
Handout (pdf) .
- Feb 29 --- Test 1.
- Mar 05 --- 3-Partition. Polynomial time reducibility (read pages 299-304, 2nd edition 270-276). VC <= IS, VC <= Clique, IS <= Clique. HC <= TSP.
Set Partition <= Rectangle Packing.
- Mar 07 --- 3-Partition <= MCSP. NP-complete. 3SAT <= Vertex Cover (read pages 312-313, 2nd edition 284-285).
Handout (pdf) .
- Mar 19 --- 3SAT <= Subset-Sum (read pages 320-322, 2nd edition 292-294).
- Mar 21 --- IS <= Partial Vertex Cover. Approximation algorithm for VC. Example for Turing (Cook) reduction.
- Mar 26 --- 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).
Approximation algorithms (factor-2 approximation for geometrio TSP).
Handout (pdf) .
- Mar 28 --- Inapproximability proofs (TSP). 3SAT <= ZBD.
- Apr 02 --- Co-NP. PSPACE problems (read pages 331-337, 2nd edition 303-309).
- Apr 04 --- Inapproximability, L-reduction, mLCS.
- Apr 09 --- More PSPACE problems, Savitch's theorem (read pages 331-337, 2nd edition 303-309). Zero knowledge proof example. FPT: algorithms.
- Apr 11 --- FPT: hardness. Communication complexity example.
- Apr 16 --- Review for Test 2.
- Apr 18 --- Test 2.
Tests (40%)
-
CS538 - test 1
(Test 1 is scheduled on Feb 29, during regular class time. Contents: Everything covered before "NP-complete problem examples", i.e., up to Feb 27.
Open book, open notes.
-
CS538 - test 2
(Test 2 is scheduled on Apr 18, during regular class time. Contents: Everything covered since "NP-complete problem examples" up to Apr 16, not including approximation algorithms, and anything that was covered only with one example and is not in Assignment 3-4 (i.e., L-reductions, Turing reductions, zero knowledge proof, and communication complexity). Open book, open notes.
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 quality as well as the presentation.
(Project report is optional, but you have to submit sth, say, your
presentation slides.) For MS students in cybersecurity, the project must be
related to security. You should fix your project by around April 15.
Madie Munro and Tom McElroy, April 23: --- "System Design is NP-complete".
Zach Wadhams, April 23: --- "Complexity of the Diffie-Hellman Algorithm".
Caleb Eardley, Angelo Porcella and Riley Slater, April 23: --- "Approximation algorithms fo network design".
Allen Bross, Yvette Hastings and Jasmine Vang, April 25 : --- "Classic Nintendo games are Computationally Hard".
Brittany Boles and Garrett Perkins, April 25: --- "The Enigma Machine".
Garrett Figueroa, April 25: --- "Partial combinatory algebras and realizability".
Sultan Yarylgassimov, April 25: --- "Algorithms for solving SAT".
Daniel Olson, April 30: --- "Computational complexity of ray tracing".
Nicholas Call, April 30: --- "The package version selection problem.
Muhammad Ashfakur Arju, Apr 30: ---"Incremental server deployment for scalable NFV-enabled networks and complexity".
Andras Necz, Apr 30: ---"Optimal grain mixing is NP-complete".
Felicia Jayasaputra and Robert Jenko, May 2: --- "A Turing machine in Conway's Game Life".
Asibul Islam and Shahnaj Mou, May 2: --- "Wordle is NP-hard".
Ajayarvind Balasubramanian and Deepakvijiayan Balu, May 2: --- "The computational comlexity of enforceability validation for generic access control".
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