CSCI 338: Computer Science Theory

Fall 2022

Date Lecture Topic Reading Homework Project

25 Aug

Introduction/Background
 
Notes
 
 
 
 
30 Aug
01 Sep
DFA
DFA
31-40
40-44
HW 1 (Due 06 Sep)
 
Proj 1 (Due 29 Sep)
 
06 Sep
08 Sep
NFA
NFA Equivalance
47-54
54-63
HW 2 (Due 13 Sep)
 
 
 
13 Sep
15 Sep
Regular Operations
Pumping Lemma
44-47, 58-63
77-82
HW 3 (Due 20 Sep)
 
 
 
20 Sep
22 Sep
Pumping Lemma
Pumping Lemma
77-82
77-82
HW 4 (Due 27 Sep)
 
 
 
27 Sep
29 Sep
Review & CFL/PDA
Quiz 1
101-124
 
 
 
 
 
04 Oct
06 Oct
Turing Machines
Decidability
165-172, 182-187
193-197
HW 5 (Due 11 Oct)
 
Proj 2 (Due 27 Oct)
 
11 Oct
13 Oct
Decidability
Undecidability
197-200
201-210, 216-217
HW 6 (Due 18 Oct)
 
 
 
18 Oct
20 Oct
Undecidability
Undecidability
215-219
219-220
HW 7 (Due 25 Oct)
 
 
 
25 Oct
27 Oct
Review
Quiz 2
 
 
 
 
 
 
01 Nov
03 Nov
Time Complexity, P, NP
NP
275-298
 
HW 8 (Due 10 Nov)
 
Proj 3 (Due 08 Dec)
 
08 Nov
10 Nov
Election Day - No Class
NP-Completeness
 
299-311
HW 9 (Due 15 Nov)
 
 
 
15 Nov
17 Nov
3SAT
Clique
311-322
Notes
HW 10 (Due 29 Nov)
 
 
 
22 Nov
24 Nov
Thanksgiving - No Class
Thanksgiving - No Class
 
 
 
 
 
 
29 Nov
01 Dec
Vertex Cover
Approximation Algorithms
Notes
Notes
HW 11 (Due 06 Dec)
 
 
 
06 Dec
08 Dec
Review
Quiz 3
 
 
 
 
 
 
13 Dec Final Exam, 2:00 - 3:50 pm      
Schedule subject to change. Refresh webpage (or hit F5) to view current page.

Lecture

Instructor

Sean Yaw

Textbook

Course Prerequisites

Course Objectives

MSU course description: Formal languages, theory, automata, Turing Machines, computability, the Church-Turing thesis, computational complexity, and NP-completeness.

At the end of the course, my goal is for you to be able to:

  1. Understand what NP-Complete problems are, have an intuition for the solvability of new problems, and have familiarity with techniques to deal with NP-Complete problems.
  2. Given a problem, understand it and develop a clear, efficient plan to solve it.
  3. Be comfortable proving statements and formulating clear arguments.
  4. Understand that some problems cannot be solved.
  5. Understand various computational models and their inherit limitations.

Grading

At the end of the semester, grades will be determined (after any curving takes place) based on your class average as follows:

Late Policy

If you submit a homework assignment late, but within 12 hours of being due, the maximum credit you can receive is 50%. After 12 hours, you receive 0. If you submit a project late, but within 24 hours, the maximum credit you can receive is 70%. After 24 hours, you receive 0.

Collaboration Policy

Failure to abide by these rules will result in everyone involved being reported to the Dean of Students and could result in failing the course.