4 ms·

Theoretical Computer Science Cheat Sheet [pdf]

65 points by kdrakon 12y ago

brooksbp 12y ago
Jaehyun Park's Stanford ACM-ICPC resources: http://web.stanford.edu/~liszt90/acm/ http://web.stanford.edu/~liszt90/acm/
elf_m_sternberg 12y ago
Interesting, but woefully incomplete since it doesn't include a single turnstile-based statement. I'm still looking for the cheat sheet that includes an explanation for how to read and comprehend anything written by Simon Peyton-Jones.
- soganess 12y ago
  Robert Harper has a great introductory(1) book on the matter 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-Languages-Professor/dp/1107029570/ref=sr_1_1?s=books&ie=UTF8&qid=1426799460&sr=1-1&keywords=robert+harper 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...
- noblethrasher 12y ago
  http://siek.blogspot.com/2012/07/crash-course-on-notation-in-programming.html http://siek.blogspot.com/2012/07/crash-course-on-notation-in...
hugelgupf 12y ago
This seems more like a cheat sheet of applied mathematics with CS flavoring than a theoretical CS cheat sheet...
- j2kun 12y ago
  Seriously. Five pages of calculus? Come on. A real cheat sheet might have: * 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...
  - kleer001 12y ago
    please do :)
  - mrcactu5 12y ago
    this has lots of useful formulas that are useful when you are stuck but no THEOREMS to really guide your work. jkun, you have the honors?
kleer001 12y ago
Sheets. 10 of them.
peter303 12y ago
I recall for out PhD written exams we were allowed on leter-size cheat sheet. 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.
- robotresearcher 12y ago
  Not ironic. Instructors allow cheat sheets for this reason as much as for actually looking stuff up. Instructors were students too. We don't forget.
- agumonkey 12y ago
  I got that very early on. The dedication to craft cheating devices (even in primary schools) and cram information as densely as possible meant you had to read it a lot, categorize, prune and simplify it to the point you basically knew it backwards. 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.
- yessertuto 12y ago
  Do PhD students have written exams? I thought they did research and wrote papers? How can you write an exam to test a PhD student when they are the ones coming up with the knowledge in the area?
  - honorious 12y ago
    PhD students take classes, and some of them do have written exam (in CS theory more than other parts of CS). In the US, where the PhD is 5 years, you spent a good portion of the first 2 years taking classes. Before coming up with new knowledge you need to know what's already out there.
serve_yay 12y ago
Sheesh, I'm glad I didn't go to whatever school you guys went to.
valbaca 12y ago
what is the grid of numbers on the last page in the bottom right? (above Fib numbers)
- Someone 12y ago
  10x10 magic square, I guess (tested that by summing a few rows and columns modulo 10; got 5 everywhere. Rows and columns should add up to 4950/10, so that doesn't disprove the hunch)
mastax 12y ago
After a single page, it usually becomes quicker to just google it.
mastax 12y ago
After a single page, it usually becomes quicker to just google it.

65 points by kdrakon 12y ago

Jaehyun Park's Stanford ACM-ICPC resources: http://web.stanford.edu/~liszt90/acm/ http://web.stanford.edu/~liszt90/acm/

Interesting, but woefully incomplete since it doesn't include a single turnstile-based statement. I'm still looking for the cheat sheet that includes an explanation for how to read and comprehend anything written by Simon Peyton-Jones.

soganess 12y ago
Robert Harper has a great introductory(1) book on the matter 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-Languages-Professor/dp/1107029570/ref=sr_1_1?s=books&ie=UTF8&qid=1426799460&sr=1-1&keywords=robert+harper 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...
noblethrasher 12y ago
http://siek.blogspot.com/2012/07/crash-course-on-notation-in-programming.html http://siek.blogspot.com/2012/07/crash-course-on-notation-in...

hugelgupf 12y ago

This seems more like a cheat sheet of applied mathematics with CS flavoring than a theoretical CS cheat sheet...

j2kun 12y ago
Seriously. Five pages of calculus? Come on. A real cheat sheet might have: * 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...
- kleer001 12y ago
  please do :)
- mrcactu5 12y ago
  this has lots of useful formulas that are useful when you are stuck but no THEOREMS to really guide your work. jkun, you have the honors?

kleer001 12y ago

Sheets. 10 of them.

peter303 12y ago

I recall for out PhD written exams we were allowed on leter-size cheat sheet. 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.

robotresearcher 12y ago
Not ironic. Instructors allow cheat sheets for this reason as much as for actually looking stuff up. Instructors were students too. We don't forget.
agumonkey 12y ago
I got that very early on. The dedication to craft cheating devices (even in primary schools) and cram information as densely as possible meant you had to read it a lot, categorize, prune and simplify it to the point you basically knew it backwards. 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.
yessertuto 12y ago
Do PhD students have written exams? I thought they did research and wrote papers? How can you write an exam to test a PhD student when they are the ones coming up with the knowledge in the area?
- honorious 12y ago
  PhD students take classes, and some of them do have written exam (in CS theory more than other parts of CS). In the US, where the PhD is 5 years, you spent a good portion of the first 2 years taking classes. Before coming up with new knowledge you need to know what's already out there.

serve_yay 12y ago

Sheesh, I'm glad I didn't go to whatever school you guys went to.

valbaca 12y ago

what is the grid of numbers on the last page in the bottom right? (above Fib numbers)

Someone 12y ago
10x10 magic square, I guess (tested that by summing a few rows and columns modulo 10; got 5 everywhere. Rows and columns should add up to 4950/10, so that doesn't disprove the hunch)

mastax 12y ago

After a single page, it usually becomes quicker to just google it.

mastax 12y ago

After a single page, it usually becomes quicker to just google it.