The irony is the act of compiling such a sheet meant you temporarily memorized the information on the sheet and didnt really need the sheet.
Instructors were students too. We don't forget.
It failed in high school when I got a graphing calc capable of storing "large" corpus of text. You didn't have to think a lot (mostly careful typing) and it grew too large to even remember everything you typed in.
Before coming up with new knowledge you need to know what's already out there.
* Optimal asymptotic time/space efficiencies for the most important problems
* The best known exponent for matrix multiplication
* Names and definitions of some popular complexity classes
* Some common but not obvious big/little O comparisons
* Dual conversions from optimization
* Probabilistic bounds used all over CS (Chernoff, Chebyshev)
* Basic facts about spectral graph theory
* The most often used inequalities like (1-x) < e^{-x} that follow from Taylor expansions
* Best known approximation ratios for various problems
* Central open conjectures like P vs NP and the unique games conjecture
* VC/margin bounds from learning theory
I could go on...
You should have a reasonably complete treatment of what you are looking for by the time you reach the chapter on PCF.
http://www.amazon.com/Practical-Foundations-Programming-Lang...
1: I call it "introductory" because many of the relevant proofs are left as an exercise to the reader. But truthfully, people I've spoken to with a direct influence on the book have mentioned many a time that harper excludes them because he expects you to know them or be able to figure them...
