CS315 - Theory of Computation

---

Course Description:
This is an undergraduate-level course on the Theory of Computation. We will cover the basic ideas of computation, state machines like DFA and NFA, Streaming Algorithms, Turing Machines and Complexity Theory.

Prerequisites:

• An undergraduate course in Discrete Mathematics, Data Structures, Algorithms and Probability
• Strong problem solving skills and some background in programming.

Textbook(s)/Supplementary Readings:

• Introduction to the Theory of Computation 3rd Edition Michael Sipser

Lectures:

Topic	Slides	Notes	Problem Sets
Background Review Discrete Mathematics Algorithm Design & Analysis	Slides Slides	Notes
Introduction to Computation What is Computation Why Study Theory Formalizing Computation Computability Complexity Cryptography	Slides
Computation, Encoding, and Languages Computational Problems Binary Data Encoding Languages Versions of Computational Problems Computational Problems as Languages Models of Computation	Slides Slides Slides Slides Slides Slides
Finite Automata DFA DFA Language Regular Languages NFA NFA and DFA Equivalence Closure of Regular Languages Regular Expressions DFA, NFA and Regexps Equivalence Pumping Lemma Minimizing DFA	Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides
Push Down Automata Push Down Automata PDA versus DFA NPDA DPDA	Slides
Streaming Algorithms Streaming Model of Computation Streaming Algorithms and DFA Randomized Streaming Algorithms Synopsis: Sliding Window, Histograms and Wavelets Sampling from Stream: Reservoir Sampling Linear Sketch Count-Min Sketch AMS Sketch	Slides Slides Slides Slides Slides Slides Slides Slides	Notes
Turing Machines Turing Machine as a Computation Model Anatomy and Working Formal Definition and Rules of Computation Recognizable and Decidable Languages Levels of Abstraction Variants of Turing Machines and Church Turing Thesis Non-Deterministic Turing Machines	Slides Slides Slides Slides Slides Slides Slides
Decidability and Recognizability Universal Turing Machine Computability Halt Problem using Diagonalization Accept Problem using Diagonalization Unrecognizable Problems Reduction Mapping Reductions More Undecidable and Unrecognizable Problems Non Turing Machine Undecidable Problems Rice Theorem	Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides
Asymptotic Analysis Runtime Analysis Big Oh Relational Properties: Big Omega, Big Theta, Little Oh Curse of Exponential Time	Slides Slides Slides Slides	Notes	PS
Intractable Problems Efficiently Solvable vs. Hard (Intractable) Problems Clique, Independent Set Vertex Cover, Set Cover, Set Packing Hamiltonian Cycle, Path and TSP Coloring and Partitioning Numeric and Number Theoretic Problems Satisfiability Problems	Slides Slides Slides Slides Slides Slides Slides	Notes	PS
Complexity Theory Time Complexity Complexity Classes Time Hierachy Theorem Polynomial Time P Nondeterministic polynomial Time NP Polynomial Time Verification P vs NP Question The Classes coNP and EXP	Slides
Polynomial Time Reduction Polynomial Time Reduction Definition Reduction by Equivalence Reduction from Special Cases to General Case Reduction by Encoding with Gadgets Transitivity of Reductions Decision, Search, and Optimization Problems and Self Reducibility	Slides Slides Slides Slides Slides Slides	Notes	PS
NP-Hard and NP-Complete Problems NP-Hard and NP-Complete Problems A first NP-Complete Problem: circuit-sat(C) The Cook-Levin Theorem: sat is NP-Complete NP-Complete Problems from known Reductions NP-Complete Applications Dir-Ham-Cycle is NP-Complete Dir-Ham-Path is NP-Complete Ham-Cycle is NP-Complete TSP is NP-Complete Subset-Sum is NP-Complete Partition is NP-Complete	Slides Slides Slides	Notes	PS
Randomized Algorithms Deterministic and Randomized Algorithms Probability Review Probabilistic Analysis of Quick-Sort Algorithm Randomized-Select Max-Cut Min-Cut Max-3-Sat and Derandomization Closest Pair Randomized Complexity Classes	Slides Slides Slides Slides Slides Slides Slides Slides Slides	Notes	PS
Approximation Algorithms Approximation Algorithms for Optimization Problems Absolute Approximation Algorithms Inapproximability by Absolute Approximate Algorithms Relative Approximation Algorithm Inapproximability by Relative Approximate Algorithms Polynomial Time Approximation Schemes Fully Polynomial Time Approximation Schemes	Slides Slides Slides Slides Slides Slides Slides	Notes	PS

Back to Top