CSC 341 – Automata, Formal Languages, and Computational Complexity (Fall 2022)

Instructor: Dawn Nye
Office Hours: MWF 4:00 PM – 5:00 PM (or by request/whenever my door is open)
Mentor: Moiz Yousufi
Mentor Sessions: TBD
Meeting Times: MWF 1:00 PM – 1:50 PM (Science 3820)
Textbook: Introduction to the Theory of Computation (3rd Edition) by Michael Sipser

Computer science is as much concerned with the analysis of computation as it is with implementation. In the study of algorithms, for example, we frequently analyze best, worst, and (when appropriate) average and amortized case runtimes. We might instead analyze the space requirements of an algorithm. For example, most sorting algorithms can be done in place requiring no more than linear space. Reachability (roughly speaking finding a path) can be done in as little as log space. Pursuing a formalization of these notions allows us to argue about the relative difficulty/tractability of problems or to determine if they are impossible outright.

In this course, we study the theory of computation to formally model problems and study their relationships with one another. In doing so, we can gain insight into not just a problem but all related problems. We can also identify problems which are intractable and might require probabilistic or approximation algorithms to solve with reasonable resources. Some problems, we will discover, can provably never have a solution, a fact which an imprecise understanding can often obscure.


Schedule

DateTopic*Reading†Assignments
8/26Introductions
8/29ProofsChapter 0
8/31Proofs
9/2Formal Languages
Deterministic Finite Automata
Section 1.1HW1
9/5NondeterminismSection 1.2
9/7DFA and NFA Equivalence
9/9Closure PropertiesHW2
HW1 Due
9/12Regular ExpressionsSection 1.3
9/14Decidable Properties
9/16Irregular LanguagesSection 1.4HW3
HW2 Due
HW1 Resubmission Due
9/19Myhill-Nerode TheoremProblems 1.51 and 1.52
9/21Kolmogorov ComplexityA New Approach to Formal Language Theory by Kolmogorov Complexity (via ProQuest Central) [Suggested]
Section 6.4 [for the ambitious]
9/23Context-Free and Context Sensitive LanguagesChapter 2 [Suggested]Exam 1
9/26Turing MachinesSection 3.1HW3 Due
9/28Variants, Other Models, and the Church-Turing ThesisSections 3.2 and 3.3
9/30DecidabilitySection 4.1HW4
HW2 Resubmission Due
10/3DiagonalizationSection 4.2Exam 1 Due
10/5UndecidabilitySections 5.1
10/7Rice’s TheoremProblem 5.28HW5
HW4 Due
10/10Reducibility & ReductionsSection 5.3
10/12The Post-Correspondence ProblemSection 5.2HW3 Resubmission Due
10/14Oracles & The Arithmetic HierarchySection 6.3HW5 Due
Fall Break
10/24AsymptoticsSection 7.1HW 6
10/26PSection 7.2
10/28NPSection 7.3
10/31Graph Notes
NP-Complete
Section 7.4HW7
HW6 Due
11/2The Cook-Levine Theorem
11/4A Classical Collection of NP-Complete ProblemsSection 7.5
11/7P vs NPExam 2
HW7 Due
HW4 Resubmission Due
11/9Space ComplexitySection Introduction
10/10HW5 Resubmission Due
11/11Savitch’s TheoremSection 8.1
11/14PSPACEHW8
Exam 2 Due
11/16L and NL
11/18NL Continued
11/21Space-Time HierarchySection 9.1 [Suggested Skim]HW9
HW8 Due
11/23Circuit ComplexitySection 9.3
Approximately Thanksgiving
11/28The Time-Circuit LinkHW10
HW9 Due
HW6 Resubmission Due
11/30The Cook-Levine Theorem Revisited
12/2AC and NC
12/5P/PolyExam 3
HW10 Due
12/7Probabilistic Algorithms
12/9Approximation AlgorithmsHW7 Resubmission Due???
HW8 Resubmission Due???
HW9 Resubmission Due???
HW10 Resubmission Due???
FinalsExam 3 Due at Scheduled Final Time

* Subject material on any given day may drift forward or back according to actual progress during class
† Supplemental readings beyond the scope of the textbook may appear at future dates


Learning Outcomes

  • Formal Automata and Languages
    • Represent a problem using finite automata
      • Deterministic and non-deterministic finite automata
      • Regular languages
      • Equivalence of NFAs and DFAs
    • Prove closure and algorithmic properties of the regular languages
    • Prove the irregularity of a problem
      • Pumping Lemma
      • Kolmogorov approach
      • Myhill-Nerode Theorem
    • Represent a problem using a context-free model of computation
      • Stack machines
      • CF grammars
    • Prove a language is not context-free
    • Represent a problem using a context-sensitive model of computation
      • Linear bounded automata
      • CS grammars
    • Represent a problem using a Turing machine
    • Prove closure and algorithmic properties of Turing machines
  • Computability Theory
    • Prove the decidability of a problem
      • Prove the decidability of a problem via an explicit construction
      • Prove the undecidability of a problem via a reduction
      • Prove the undecidability of a problem via Rice’s Theorem
    • Prove that a problem is recognizable, co-recognizable, or neither
    • Describe the practical ramifications of computational undecidability
      • Summarize the Church-Turing Hypothesis and Gödel’s Incompleteness Theorems
  • Computational Complexity
    • Prove that a problem is in a particular time complexity class
    • Prove that a problem is NP-complete by way of a reduction
    • Explain the practical ramifications of P vs NP
    • Describe practical problem-solving strategies for dealing with intractable problems
      • Approximation algorithms
      • Probabilistic algorithms
  • As Time Permits
    • Prove that a problem is in a particular space complexity class
      • Formally define each of the major complexity classes
      • Describe the essential characteristics of a problem belonging to each complexity class
      • Describe the practical relationships between various time/space complexity classes
    • Prove that a problem is in a particular circuit complexity
    • Understand and utilize oracle machines for higher levels of computation
    • Understand other models of computation and be able to generate new ones