Hacker News new | ask | show | jobs
Theoretical Computer Science Cheat Sheet [pdf] (tug.org)
65 points by kdrakon 4109 days ago
8 comments

This seems more like a cheat sheet of applied mathematics with CS flavoring than a theoretical CS cheat sheet...
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...

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?

please do :)
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.
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-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...

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.

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.

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.

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?
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.

Jaehyun Park's Stanford ACM-ICPC resources:

http://web.stanford.edu/~liszt90/acm/

Sheesh, I'm glad I didn't go to whatever school you guys went to.
After a single page, it usually becomes quicker to just google it.
Sheets. 10 of them.
what is the grid of numbers on the last page in the bottom right? (above Fib numbers)
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)