Computer science
Amdahl’s law
Relates the speedup of a sub-task to the resulting speedup of the whole. Trivially true, but often needed to knock down false intuition.
on Wikipedia, long with examples
on MathWorld, short without examples
Asymptotic notation
Used to abstract away units and fixed overhead when analyzing resource usage.
on Wikipedia, long
cheat sheet from the same article
Deterministic finite state automata
Traditional square one of theoretical computer science, with many practical applications.
on Wikipedia, definition and example
homework with solutions (PDF)
The pumping lemma for regular languages
Illustrates many recurring themes. Understanding the proof and usage of the pumping lemma will help you understand and apply more famous, advanced results (e.g. anything involving Turing Machines).
at Penn Engineering, explanation and examples
handout (PDF) with concise statement and examples
Cantor’s diagonal argument
An astonishingly elegant technique for proving certain kinds of theorems. Originally introduced by the mathematician Georg Cantor to show that the set of real numbers is uncountable – that is, there is no one-to-one correspondence between real numbers and natural numbers, but was later found to generalize to several other contexts. Perhaps the most notable uses of this technique, in addition to Cantor’s proof, are Alan Turing’s answer to the Halting problem, and Gödel’s proof of his famous first incompleteness theorem.
on Wikipedia, definition and a step-through of the proof
Halting Problem
at Michigan State, problem, theorem, and proof
University of Edinburgh, explanation of proof
Links
Books
How Everything Works: Making Physics out of the Ordinary by Louis Bloomfield (no math though)
Videos
Khan Academy 800+ Youtube videos covering everything from basic arithmetic and algebra to differential equations, physics, and finance
Blog posts
Creating The Simple Math of Everything by Matt Simpson, calling for more contributions on the topic.
Eric Drexler on Learning About Everything by Vladimir Nesov