CSCI 338: Computer Science Theory

Fall 2024

Date Lecture Topic Reading Homework Project

22 Aug

Introduction/Background
 
Notes
 
 
 
 
27 Aug
29 Aug
DFA
DFA
31-40
40-44
HW 1 (Due 03 Sep)
 
Proj 1 (Due 26 Sep)
 
03 Sep
05 Sep
NFA
NFA Equivalance
47-54
54-63
HW 2 (Due 10 Sep)
 
 
 
10 Sep
12 Sep
Regular Expressions
Pumping Lemma
44-47, 58-63
77-82
HW 3 (Due 17 Sep)
 
 
 
17 Sep
19 Sep
Pumping Lemma
Pumping Lemma
77-82
77-82
HW 4 (Due 24 Sep)
 
 
 
24 Sep
26 Sep
Review
Test 1
101-124
 
 
 
 
 
01 Oct
03 Oct
Turing Machines
Decidability
165-172, 182-187
193-197
HW 5 (Due 08 Oct)
 
Proj 2 (Due 24 Oct)
 
08 Oct
10 Oct
Decidability
Undecidability
197-200
201-210, 216-217
HW 6 (Due 15 Oct)
 
 
 
15 Oct
17 Oct
Undecidability
Undecidability
215-219
219-220
HW 7 (Due 22 Oct)
 
 
 
22 Oct
24 Oct
Review
Test 2
 
 
 
 
 
 
29 Oct
31 Oct
Time Complexity, P, NP
NP
275-298
 
HW 8 (Due 05 Nov)
 
Proj 3 (Due 21 Nov)
 
05 Nov
07 Nov
3SAT
Clique
299-311
311-322
HW 9 (Due 12 Nov)
 
 
 
12 Nov
14 Nov
Vertex Cover
Dominating Set
Notes
Notes
HW 10 (Due 19 Nov)
 
 
 
19 Nov
21 Nov
Review
Test 3
 
 
HW 11 (Due 10 Dec)
 
 
 
26 Nov
28 Nov
Thanksgiving - No Class
Thanksgiving - No Class
 
 
 
 
 
 
03 Dec
05 Dec
Approximation Algorithms
Review for Final
 
 
 
 
 
 
10 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.