CS3313: Theory of Computation (Fall 2023)

Announcement

PART I: Automata and Language

  1. Finite automata and regular language (pdf)
  2. Pushdown automata and context free language (pdf)
  3. (*) Deterministic Context-Free Languages (pdf)

PART II: Computability

  1. The Church-Turing Thesis (pdf)
  2. Decidability (pdf)
  3. Reducibility (pdf)
  4. (*) Goedel Number (pdf)

PART III: Computational Complexity

  1. Time Complexity (pdf)
  2. NP-completeness (pdf)
  3. Space Complexity (pdf)
  4. The log Space (pdf)
  5. Intractability (pdf)

    Assignments

    1. CANVAS

    References

    Last updated: Sep. 14, 2023