Home / Learn / Theory & Discrete Math

∑ Theory & Discrete Math

Logic, automata, computability. 51 topics, from beginner to advanced.

Theory of computation and discrete mathematics provide the formal foundation of computer science. Logic, sets, proofs, graphs, automata and computability tell us what problems a computer can solve, how hard they are, and how to prove that an algorithm is correct. These ideas underpin compilers, cryptography and algorithm design.

Who this area is for

Students of theoretical computer science, anyone studying for algorithms or complexity courses, and programmers who want to know what computers cannot do.

Real-world use cases

Using logic to write precise conditions for database queries and program assertions.
Modeling a text-matching or parsing task with a finite automaton.
Proving that an algorithm always terminates and returns the right answer.
Designing a regular expression that matches valid email addresses and nothing else.
Recognizing that a scheduling problem is NP-complete, so an exact fast algorithm is unlikely to exist.

Topics in Theory & Discrete Math

Beginner (17)

Propositional Logic — Reasoning with statements that are true or false.
Predicate Logic — Logic with quantifiers over objects and relations.
Sets and Set Operations — Collections and operations like union and complement.
Functions and Relations — Mappings and pairings between sets.
Mathematical Induction — Proof technique establishing a statement for all naturals.
Proof Techniques — Direct, contradiction and contrapositive reasoning.
Counting Principles — Rules for product, sum and inclusion-exclusion.
Permutations and Combinations — Counting ordered and unordered selections.
Pigeonhole Principle — If more items than boxes, some box holds two.
Recurrence Relations — Equations defining sequences in terms of earlier terms.
Graph Theory Basics — Vertices, edges, degrees and paths.
Trees in Graph Theory — Connected acyclic graphs.
Euler and Hamilton Paths — Traversals covering every edge or every vertex once.
Graph Coloring — Assigning colors so adjacent vertices differ.
Modular Arithmetic — Arithmetic where numbers wrap around a modulus.
Number Theory Basics — Divisibility, primes and gcd.
Alphabets and Languages — Symbol sets and the sets of strings over them.

Intermediate (17)

Finite Automata — Abstract machines with finitely many states.
Deterministic Finite Automata — Machines with exactly one transition per symbol and state.
Nondeterministic Finite Automata — Machines allowing multiple or empty transitions.
Regular Languages — Languages recognized by finite automata.
Regular Expressions in Theory — Algebraic notation describing regular languages.
Pumping Lemma for Regular Languages — Tool proving certain languages are not regular.
Context-Free Grammars — Rules generating strings via recursive productions.
Parse Trees — Trees showing how a grammar derives a string.
Pushdown Automata — Automata with a stack recognizing context-free languages.
Chomsky Hierarchy — Classification of grammars by expressive power.
Turing Machines — Abstract machine with infinite tape modeling computation.
Church-Turing Thesis — Claim that Turing machines capture all effective computation.
Decidability — Whether an algorithm can always answer a yes/no question.
Halting Problem — Undecidable question of whether a program terminates.
Reductions — Transforming one problem into another to compare difficulty.
Rice's Theorem — Every nontrivial semantic program property is undecidable.
Complexity Classes — Groupings of problems by resource requirements.

Advanced (17)

Class P — Problems solvable in polynomial time.
Class NP — Problems whose solutions can be verified quickly.
NP-Completeness — Hardest problems in NP to which all NP reduces.
Cook-Levin Theorem — Result proving SAT is NP-complete.
P vs NP — Open question whether quick verification implies quick solving.
SAT Problem — Deciding whether a Boolean formula can be satisfied.
Space Complexity Classes — PSPACE, L and related memory-bounded classes.
Randomized Complexity — Classes like BPP using probabilistic machines.
Approximation and Inapproximability — Limits on how closely hard problems can be approximated.
Parameterized Complexity — Analyzing hardness relative to structural parameters.
Lambda Calculus — Minimal formal system of function abstraction and application.
Information Theory — Quantifying information and entropy.
Kolmogorov Complexity — Length of the shortest program producing a string.
Communication Complexity — Cost of computing when inputs are split between parties.
Interactive Proofs — Verification via dialogue between prover and verifier.
PCP Theorem — Characterization of NP by probabilistically checkable proofs.
Category Theory for Programmers — Abstract language of objects, arrows and composition.

How to study Theory & Discrete Math

Work through proofs by hand with a pencil, one step at a time. For automata and grammars, draw the machine or the parse tree before you write any formal notation. Test each claim on small examples before trusting it.

Frequently asked questions

Why study discrete math for computer science?

Discrete math deals with countable structures such as integers, graphs and logic statements, which is exactly what computers manipulate. It also trains careful proof writing.

What is the halting problem?

The halting problem asks whether a given program will eventually stop for a given input. Alan Turing proved no general algorithm can answer this for every program.

What is the difference between P and NP?

P is the set of problems solvable in polynomial time. NP is the set of problems whose solutions can be checked in polynomial time. Whether P equals NP is an open question.

Why study theory if I want to build products?

Theory tells you which problems have efficient solutions and which do not. That saves time when you choose an approach, and it explains why some features are hard or impossible.

Is discrete math the same as calculus?

No. Discrete math studies countable structures such as graphs, sets and integers, while calculus studies continuous change. Computing relies mostly on discrete math.

Open the interactive Theory & Discrete Math area Take the Theory & Discrete Math quiz