Theoretical Computer Science
1. Automata Theory
• 1.1 Formal Languages
o Alphabet, strings, languages
o Language operations
o Chomsky Hierarchy (Regular, Context-Free, Context-Sensitive,
Recursively Enumerable)
• 1.2 Regular Languages
o Finite Automata (DFA, NFA)
o Regular expressions
o NFA → DFA conversion
o Myhill–Nerode theorem
o Pumping lemma for regular languages
• 1.3 Context-Free Languages
o Context-free grammars (CFGs)
o Parse trees & ambiguity
o Pushdown automata (PDA)
o CYK parsing
o Pumping lemma for CFLs
• 1.4 Context-Sensitive Languages
o Linear bounded automata
o Context-sensitive grammars
• 1.5 Turing Machines
o Deterministic/Non-deterministic
o Multi-tape TMs
o Universal Turing machine
o Church–Turing thesis
• 1.6 Formal Grammars & Rewrite Systems
o Type-0 to Type-3 grammars
o Term rewriting systems
o Lambda calculus
• 1.7 Automata Minimization
o State minimization
o Myhill–Nerode equivalence classes
• 1.8 Advanced Automata
o Probabilistic automata
o Quantum automata
o Tree automata
o ω-automata (Büchi, Rabin, Streett)
2. Complexity Theory
• 2.1 Time Complexity
o Big-O, Big-Theta, Big-Omega
o Time-constructible functions
o Hierarchy theorems
• 2.2 Space Complexity
o PSPACE
o NL, L
o Savitch’s theorem
• 2.3 Complexity Classes (Full Set)
o P, NP, co-NP
o NP-Complete, NP-Hard
o EXP, EXPSPACE
o BPP, RP, ZPP
o PH (Polynomial Hierarchy)
o #P and Counting complexity
o AM, MA, IP (Interactive proofs)
o PCP theorem
• 2.4 Reductions
o Polynomial-time reductions
o Many-one reductions
o Turing reductions
• 2.5 Circuit Complexity
o Boolean circuits
o AC⁰, TC⁰, NC
o Lower bounds
• 2.6 Parameterized Complexity
o Fixed-parameter tractability (FPT)
o W-hierarchy
• 2.7 Communication Complexity
o Deterministic complexity
o Randomized protocols
o Quantum communication
• 2.8 Approximation Complexity
o APX
o PTAS
o Hardness of approximation
• 2.9 Descriptive Complexity
o Logic characterizations of P, NP
o Finite model theory
3. Quantum Computing Theory
• 3.1 Quantum Information Foundations
o Qubits
o Quantum gates
o Tensor products
o Entanglement
• 3.2 Quantum Circuits
o Universal gate sets
o Quantum circuit complexity
o Depth & size measures
• 3.3 Quantum Algorithms
o Shor’s algorithm
o Grover’s algorithm
o Quantum Fourier Transform
o Amplitude amplification
• 3.4 Quantum Complexity Classes
o BQP
o QMA
o QCMA
o QIP
o Quantum PCP conjecture
• 3.5 Quantum Error Correction
o Stabilizer codes
o Surface codes
o Fault tolerance
• 3.6 Quantum Cryptography
o QKD (BB84, E91)
o Post-quantum cryptographic implications
• 3.7 Quantum Automata
o Measure-once automata
o Measure-many automata
o QFA vs DFA power comparison
• 3.8 Hamiltonian Complexity
o Local Hamiltonian problem
o Adiabatic quantum computing
4. Computability Theory
• 4.1 Decidability
o Halting problem
o Rice’s theorem
o Diagonalization
• 4.2 Reducibility
o Many-one reductions
o Turing reductions
• 4.3 Recursion Theory
o Primitive recursive functions
o μ-recursive functions
o Arithmetical hierarchy
5. Logic in Computer Science
• 5.1 Propositional logic
• 5.2 First-order logic
• 5.3 Model theory
• 5.4 Proof systems
• 5.5 Lambda calculus & type systems
6. Algorithms & Complexity Foundations
• 6.1 Randomized Algorithms
• 6.2 Online Algorithms
• 6.3 Streaming Algorithms
• 6.4 Sublinear Algorithms
• 6.5 Distributed Algorithms
7. Formal Verification
• 7.1 Model Checking
• 7.2 Temporal Logic (LTL/CTL)
• 7.3 Hoare Logic
• 7.4 Type-based program verification
8. Type Theory
• 8.1 Dependent type theory
• 8.2 Curry–Howard correspondence
• 8.3 Type inference algorithms
• 8.4 Higher-order type systems
9. Category Theory for Computer Science
• 9.1 Monads & functors
• 9.2 Categorical semantics
• 9.3 Cartesian closed categories
10. Algorithmic Game Theory
• 10.1 Mechanism Design
• 10.2 Price of Anarchy
• 10.3 Computational equilibria
11. Computational Learning Theory
• 11.1 PAC learning
• 11.2 VC dimension
• 11.3 Online learning theory
12. Cryptography Theory (Complexity-based)
• 12.1 One-way functions
• 12.2 Random oracles
• 12.3 Cryptographic hardness assumptions