CSC 341 – Fall 2023

Instructor: Dawn Nye
Office Hours: MWF 11:50 – 12:50 and 1:50 – 2:50 at Noyce 2811 or Noyce 3820 (to be determined by observation)
Mentor: Will Chapin
Mentor Sessions: to be determined
Meeting Times: MWF 3-3:50 pm at Noyce 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.


Order of Topics and Readings

Topic*Associated Reading†
REVIEW
Introductions
What is Computation?
ProofsChapter 0
Proofs++
AUTOMATA AND LANGUAGES
Formal Languages
Regular Expressions
Regular Grammars
Typed Regularity Notes (ignore the todo bubbles)
Section 1.3 (after 1.1 and 1.2)
Deterministic Finite AutomataSection 1.1
NondeterminismSection 1.2
DFA and NFA Equivalence
Closure Properties
Decidable Properties
Irregular LanguagesSection 1.4
Myhill-Nerode TheoremProblems 1.51 and 1.52
Kolmogorov ComplexityA New Approach to Formal Language Theory by Kolmogorov Complexity (via ProQuest Central) [Suggested]
Section 6.4 [for the ambitious]
Context-Free and Context Sensitive LanguagesChapter 2 [Suggested]
COMPUTABILITY THEORY
Turing MachinesSection 3.1
Variants, Other Models, and the Church Turing ThesisSections 3.2 and 3.3
DecidabilitySection 4.1
DiagonalizationSection 4.2
UndecidabilitySections 5.1
Rice’s TheoremProblem 5.28
Reducibility & ReductionsSection 5.3
Language Cheat Sheet
The Post-Correspondence ProblemSection 5.2
The Arithmetic HierarchySection 6.3
COMPLEXITY THEORY
AsymptoticsSection 7.1
PSection 7.2
NPSection 7.3
Graphs
NP-CompleteSection 7.4
Section 7.5
NP vs co-NP
Space ComplexitySection Introduction
Savitch’s TheoremSection 8.1
PSPACE
L and NL
Space-Time HierarchySection 9.1 [Suggested Skim]
SELECTED TOPICS
Circuit ComplexitySection 9.3
Probabilistic AlgorithmsSection 10.2
Approximation Algorithms

* Some subject material may be omitted 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
      • 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