Re:Theoretical Computer Science Cheat Sheet [pdf]
by elf_m_sternberg on Thursday March 19, 2015 @01:23PM
(#9233348)
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.
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...
Re:Theoretical Computer Science Cheat Sheet [pdf]
by agumonkey on Thursday March 19, 2015 @04:45PM
(#9234499)
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.
Re:Theoretical Computer Science Cheat Sheet [pdf]
by yessertuto on Friday March 20, 2015 @12:42AM
(#9236257)
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?
Re:Theoretical Computer Science Cheat Sheet [pdf]
by honorious on Friday March 20, 2015 @03:43AM
(#9236581)
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.
Re:Theoretical Computer Science Cheat Sheet [pdf]
by Someone on Thursday March 19, 2015 @05:32PM
(#9234731)
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)
* 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...
jkun, you have the honors?
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...
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.
http://web.stanford.edu/~liszt90/acm/