Carl Sable

Professor of Computer Engineering

ECE 461: Theoretical Computer Science

Catalog Data:

In-depth exploration of the foundations of, the limitations of, and the open questions related to theoretical computer science and computation. Topics include models of computation such as deterministic and nondeterministic automata, context free grammars, pushdown automata and Turing machines; decidability and the halting problem; time and space complexity; the P=NP? question; NP-complete problems; reductions; randomness and probabilistic algorithms. Advanced topics vary across semesters.

Topics:

  1. Course introduction, notations, and terminology.
  2. Deterministic and non-deterministic finite automata; regular expressions.
  3. Non-regular languages; the pumping lemma.
  4. Context-free grammars and pushdown automata.
  5. Non-context-free languages and the pumping lemma.
  6. Turing machines.
  7. Decidable languages.
  8. Undecidability and diagonalization.
  9. Reductions and computation histories.
  10. The recursion theorem.
  11. Logical theories; introduction to oracles.
  12. Time complexity; Big-o notation; the class P.
  13. The classes NP and coNP; the P versus NP question.
  14. NP-complete problems, the Cook-Levin theorem, and (more) reductions.
  15. Space complexity; Savitch's theorem; the class PSPACE.
  16. PSPACE-complete problems.
  17. Intractable problems and hierarchy theorems.
  18. Relativization and (more about) oracles.
  19. Circuit complexity.
  20. Approximation algorithms.
  21. Randomization; probabilistic algorithms; the Class BPP.
  22. Interactive proof systems.

Course Outcomes:

Students will understand the fundamentals of computability theory and complexity theory. Students will be familiar with some of the most important unanswered questions in theoretical computer science. Students will gain a deep understand of certain complex proofs, and they will be able to prove simpler but non-trivial theoretical facts about computation on their own. Problem sets and quizzes will be used to evaluate various levels of knowledge of subtopics.

Students will attain:

  1. Knowledge of various subtopics of theoretical computer science, some in depth.
  2. Deep understanding of some important proofs within the fields of computability theory and complexity theory.
  3. Experience coming up with their own proofs for non-trivial theoretical facts about computation.

Assessment Methods:

Problem sets will be used to assess students' abilities to proof theoretical facts about computatoin. Quizzes will be used to asses students' knowledge of general facts about theoretical computer science and their conceptual understanding of ideas.