CSCI 338: Computer Science Theory

Spring 2024

Date Lecture Topic Reading Homework Project

17 Jan
19 Jan

Introduction/Background
DFA
 
Notes
31-35
 
 
 
 
 
 
22 Jan
24 Jan
26 Jan
DFA
DFA
DFA
35-40
40-44
Notes
HW 1 (Due 29 Jan)
Solution
 
Proj 1 (Due 23 Feb)
Grading Script
 
29 Jan
31 Jan
02 Feb
NFA
NFA
DFA/NFA Equivalence
47-54
47-54
54-63
HW 2 (Due 05 Feb)
Solution
 
 
 
 
05 Feb
07 Feb
09 Feb
Regular Operations
Regular Expressions
Pumping Lemma
44-47, 58-63
58-63
77-82
HW 3 (Due 12 Feb)
Solution
 
 
 
 
12 Feb
14 Feb
16 Feb
Pumping Lemma (handout)
Pumping Lemma
Pumping Lemma
77-82
77-82
101-124
HW 4 (Due 21 Feb)
Solution
 
 
 
 
19 Feb
21 Feb
23 Feb
Presidents' Day - No Class
Review
Test 1
 
 
 
 
 
 
 
 
 
26 Feb
28 Feb
01 Mar
PDA
Turing Machines
Decidability
165-172, 182-187
193-197
193-197
HW 5 (Due 04 Mar)
Solution
 
Proj 2 (Due 27 Mar)
Grading Script
 
04 Mar
06 Mar
08 Mar
Decidability
Undecidability
Undecidability
197-200
201-210
201-210
HW 6 (Due 18 Mar)
Solution
 
 
 
 
11 Mar
13 Mar
15 Mar
Spring Break - No Class
Spring Break - No Class
Spring Break - No Class
 
 
 
 
 
 
 
 
 
18 Mar
20 Mar
22 Mar
Undecidability
Undecidability
Undecidability
 
215-220
 
HW 7 (Due 25 Mar)
Solution
 
 
 
 
25 Mar
27 Mar
29 Mar
Review
Test 2
"University Day" - No Class
 
 
 
 
 
 
 
 
 
01 Apr
03 Apr
05 Apr
Time Complexity, P, NP
NP
NP
 
275-298
 
HW 8 (Due 08 Apr)
 
 
Proj 3 (Due 01 May)
 
 
08 Apr
10 Apr
12 Apr
NP-Complete
Clique
Clique
299-311
311-322
311-322
HW 9 (Due 15 Apr)
 
 
 
 
 
15 Apr
17 Apr
19 Apr
Vertex Cover
Vertex Cover
Dominating Set
 
Notes
 
HW 10 (Due 22 Apr)
 
 
 
 
 
22 Apr
24 Apr
26 Apr
Dominating Set
Approximation Algorithms
Approximation Algorithms
 
Notes
 
HW 11 (Due 29 Apr)
 
 
 
 
 
29 Apr
01 May
03 May
Review
Test 3
Final Exam Review
 
 
 
 
 
 
 
 
 
08 May Final Exam, 10:00 - 11:50 am      
Schedule subject to change. Refresh webpage (or hit F5) to view current page.

Lecture

Instructor

Sean Yaw

Grader

Angelo Porcella

Textbook (not required)

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.