News for hackers. Stuff that matters.
Re:Theoretical Computer Science Cheat Sheet [pdf] by hugelgupf on Thursday March 19, 2015 @02:20PM (#9233668)
This seems more like a cheat sheet of applied mathematics with CS flavoring than a theoretical CS cheat sheet...
Re:Theoretical Computer Science Cheat Sheet [pdf] by j2kun on Thursday March 19, 2015 @02:34PM (#9233742)
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...

Re:Theoretical Computer Science Cheat Sheet [pdf] by mrcactu5 on Thursday March 19, 2015 @04:54PM (#9234548)
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?

Re:Theoretical Computer Science Cheat Sheet [pdf] by kleer001 on Thursday March 19, 2015 @03:38PM (#9234087)
please do :)
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.
Re:Theoretical Computer Science Cheat Sheet [pdf] by noblethrasher on Thursday March 19, 2015 @01:53PM (#9233516)
Re:Theoretical Computer Science Cheat Sheet [pdf] by soganess on Thursday March 19, 2015 @05:16PM (#9234646)
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...

Re:Theoretical Computer Science Cheat Sheet [pdf] by peter303 on Thursday March 19, 2015 @03:52PM (#9234172)
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.

Re:Theoretical Computer Science Cheat Sheet [pdf] by robotresearcher on Thursday March 19, 2015 @04:21PM (#9234355)
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.

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 brooksbp on Thursday March 19, 2015 @01:20PM (#9233335)
Jaehyun Park's Stanford ACM-ICPC resources:

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

Re:Theoretical Computer Science Cheat Sheet [pdf] by serve_yay on Thursday March 19, 2015 @04:06PM (#9234264)
Sheesh, I'm glad I didn't go to whatever school you guys went to.
Re:Theoretical Computer Science Cheat Sheet [pdf] by mastax on Friday March 20, 2015 @01:47AM (#9236395)
After a single page, it usually becomes quicker to just google it.
Re:Theoretical Computer Science Cheat Sheet [pdf] by kleer001 on Thursday March 19, 2015 @03:38PM (#9234088)
Sheets. 10 of them.
Re:Theoretical Computer Science Cheat Sheet [pdf] by valbaca on Thursday March 19, 2015 @04:13PM (#9234300)
what is the grid of numbers on the last page in the bottom right? (above Fib numbers)
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)