CSCI 338: Computer Science Theory

Fall 2020

Date Lecture Topic Reading Homework
18 Aug
20 Aug
Introduction/Background
DFA
 
31-40
 
 
25 Aug
27 Aug
DFA
NFA
40-44
47-54
HW 1 (Due 01 Sep)
 
01 Sep
03 Sep
NFA Equivalance
Regular Operations
54-63
44-47, 58-63
HW 2 (Due 08 Sep)
 
08 Sep
10 Sep
Regular Expressions
Pumping Lemma
63-76
77-82
HW 3 (Due 15 Sep)
 
15 Sep
17 Sep
Pumping Lemma
Pumping Lemma
77-82
77-82
HW 4 (Due 22 Sep)
 
22 Sep
24 Sep
Review & CFL/PDA
Quiz 1 (Online) (Solution)
101-124
 
 
 
29 Sep
01 Oct
Turing Machines
Decidability
165-172, 182-187
193-197
HW 5 (Due 06 Oct)
 
06 Oct
08 Oct
Decidability
Undecidability
197-200
201-210, 216-217
HW 6 (Due 13 Oct)
 
13 Oct
15 Oct
Undecidability
Undecidability
215-219
219-220
HW 7 (Due 20 Oct)
 
20 Oct
22 Oct
Review
Quiz 2 (Online) Solution
 
 
 
 
27 Oct
29 Oct
Time Complexity, P, NP
NP
275-298
 
HW 8 (Due 05 Nov)
 
03 Nov
05 Nov
Election Day - No Class
NP-Completeness
 
299-311
HW 9 (Due 10 Nov)
 
10 Nov
12 Nov
3SAT
Clique   Handout
311-322
Notes
HW 10 (Due 19 Nov)
 
17 Nov
19 Nov
Independent Set
Review
Notes
 
 
 
24 Nov Quiz 3 (Online)    
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.

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.

Sickness Accommodations

Masks

Per MSU: "Face coverings are required in all indoor spaces and all enclosed or partially enclosed outdoor spaces. MSU requires all students to wear face masks or cloth face coverings in classrooms, laboratories and other similar spaces where in-person instruction occurs. MSU requires the wearing of masks in physical classrooms to help mitigate the transmission of SARS-CoV-2, which causes COVID-19. The MSU community views the adoption of these practices as a mark of good citizenship and respectful care of fellow classmates, faculty, and staff. The complete details about MSU’s mask requirement can be found at https://www.montana.edu/health/coronavirus/index.html."