Theory of Computation

• Automata Theory https://en.wikipedia.org/wiki/Automata_theory

  • Finite State Machines

  • Deterministic Finite Automata

  • Non-deterministic Finite Automata

  • Conversion of NFA to DFA and their equivalence

  • Mealy Machine

  • Moore Machine

• Formal Languages

  • Formal Language

  • Regular Expression

  • Context Free Languages

  • Turing Machine

1. Computability Theory (Recursion theory)

• Computation by abstract devices

• Decidability

• Tractability

1. Complexity Theory

• Analysis of algorithms

  • Numerical algorithms

  • Non-numerical algorithms

• Complexity of algorithms

• Tradeoffs between complexity measures