CS Theory — Placement Preparation
Foundational computer science theory for interviews.
Chapters
| Topic | File |
|---|---|
| Sets, Relations & Functions | Set operations, relations, function types |
| Logic | Propositional & predicate logic, truth tables |
| Proof Techniques | Induction, contradiction, pigeonhole |
| Complexity Classes | P, NP, NP-complete, reductions |
| Turing Machines | Turing machine model, decidability |
| Computability | Halting problem, recursion theory |
| Formal Languages | Regular, context-free, Chomsky hierarchy |
| Formal Methods | TLA+, Alloy, Coq, model checking, abstract interpretation |
| Comparison Sorting Lower Bound | Ω(n log n) information-theoretic bound |
Why CS Theory Matters
- Tests fundamental reasoning ability
- Required for algorithm correctness proofs
- P vs NP appears in interviews as a discussion topic
- Proof techniques help in algorithm design
- Sets/relations/logic form the basis of databases, type systems, and formal methods