Theoretical Computer Science Cheat Sheet [pdf](tug.org)
tug.org
Theoretical Computer Science Cheat Sheet [pdf]
https://www.tug.org/texshowcase/cheat.pdf
65 comments
I am confused, this seems more like a general math cheatsheet. The only thing that truly has anything to do with theoretical CS are the definitions for the O-notation on the first page (and most CS students don't need a cheat-sheet for that) and the master theorem. Nothing on P, NP, NP-hardness or completeness, formal languages (Chomsky hierarchy?), finite automata, Turing machines, halting problem, decision problem, reduction proofs, Pumping lemma, Gödels incompleteness theorem, etc. This sheet would have been of very little help in any theoretical computer science exam I ever took. The only cheat sheet I ever needed in theoretical CS was Schönings book "Theoretische Informatik - kurz gefasst" ("A short overview of theoretical CS", well, it has ~180 pages...), which is pretty standard in German universities. It was completely worn out after my first semester + exam of theoretical CS... here is a TOC: http://www.gbv.de/dms/hebis-mainz/toc/094349797.pdf
More of a "Math for CS" cheatsheet. I agree that we can't call it a CS sheet as it has very few actual CS concepts (besides the O notation, I would also consider Graph Theory as CS), but I also wouldn't call it a general math sheet because it encompasses only an arbitrary small subset of math. Having said that, as a Math-for-CS sheet I found the section on matrices a bit light (missing quite a lot of linear algebra), and I missed the Fourier transform.
Isn't graph theory a very general (and generally used) math concept that is useful in CS, not the other way around?
Yes, and so is asymptotic analysis and the associated big-O notation.
Yes
Maybe it's just me, but when a cheatsheet reaches 10 pages and includes multiple areas like this one I'd just split it up into multiple ones. It almost feels like this needs a table of contents.
And I think a bit more theoretical CS stuff, maybe a few diagrams, would be more helpful than e.g. the Pythagorean theorem or the powers of 2 which shouldn't be a problem to just memorize at that level.
And I think a bit more theoretical CS stuff, maybe a few diagrams, would be more helpful than e.g. the Pythagorean theorem or the powers of 2 which shouldn't be a problem to just memorize at that level.
This is only a showcase of TeX, the actual value of this cheat-sheet seems pretty low.
I used to know most of this when I was in uni, including how to derive it when I needed it. Back then this kind of cheat-sheet would not have helped me apply my knowledge. The actual knowledge was very clear in my head from solving problems, or I remembered some key idea used during derivation and from there could work out the rest.
If you need this kind of cheat-sheet you don't understand the concepts deep enough.
Unfortunately most of this knowledge is now 15 years later either very fuzzy or completely lost from my mind. I guess that happens when it is not being refreshed/applied during the career I chose.
This cheat-sheet serves a reminder of how much knowledge I have lost ;)
I used to know most of this when I was in uni, including how to derive it when I needed it. Back then this kind of cheat-sheet would not have helped me apply my knowledge. The actual knowledge was very clear in my head from solving problems, or I remembered some key idea used during derivation and from there could work out the rest.
If you need this kind of cheat-sheet you don't understand the concepts deep enough.
Unfortunately most of this knowledge is now 15 years later either very fuzzy or completely lost from my mind. I guess that happens when it is not being refreshed/applied during the career I chose.
This cheat-sheet serves a reminder of how much knowledge I have lost ;)
I dunno, this seems like a perfectly reasonable tool. Saying "what was the double angle formula for sin, again?" or "what was the error term in Stirling's approximation" doesn't mean that you don't understand the fundamentals.
I find I don't really need to remember trig as long as i remember how imaginary exponentials and the unit circle works.
Def agree on Stirling's though.
Def agree on Stirling's though.
> I find I don't really need to remember trig as long as i remember how imaginary exponentials and the unit circle works.
Or, to phrase it differently, trigonometry is just a different language for the restriction of the complex exponential to the imaginary axis, and you are remembering the facts in translated form. (Which I agree is much better—it's certainly the only way I can ever remember the thicket of identities! But I'd argue that it's still remembering trigonometry.)
Or, to phrase it differently, trigonometry is just a different language for the restriction of the complex exponential to the imaginary axis, and you are remembering the facts in translated form. (Which I agree is much better—it's certainly the only way I can ever remember the thicket of identities! But I'd argue that it's still remembering trigonometry.)
I clearly remember my heureka moment when I discovered back in university that I don't have to actually learn and remember all that stuff that was taught but to recognize patterns and tricks that will reduce the problem domain down to a few things from which everything else can be deduced. After that most of the lectures boiled down to: ok, what is important to learn and remember here :-)
I was expecting something like known NPC problems and their reductions plus complexity of algorithms and data structures.
This seems like a math cheat sheet that can be improved removing simple derivations of some formulas.
However it can be handy.
This seems like a math cheat sheet that can be improved removing simple derivations of some formulas.
However it can be handy.
Engineering version is a whole huge book with lots of interesting things to search for:
https://link.springer.com/book/10.1007/978-94-010-9314-9
Not just math, but properties of matter, physical constants, thermodynamics and fluids (oblique shocks!), electricity (Semiconductors, Verilog!), solid mechanics, and random stuff like screw threads.
They had us get this in undergrad, all the Engineering students at Oxford know it as HLT.
https://link.springer.com/book/10.1007/978-94-010-9314-9
Not just math, but properties of matter, physical constants, thermodynamics and fluids (oblique shocks!), electricity (Semiconductors, Verilog!), solid mechanics, and random stuff like screw threads.
They had us get this in undergrad, all the Engineering students at Oxford know it as HLT.
I own this one. More relevant in my opinion:
https://www.amazon.com/Handbook-Mathematics-Computational-Sc...
https://www.amazon.com/Handbook-Mathematics-Computational-Sc...
Do you have a cheat sheet for this cheat sheet?
It's nice, but it doesn't cover any topic of Theoretical Computer Science [1]. It's just the math required for undergrad general CS courses.
[1] - https://en.wikipedia.org/wiki/Theoretical_computer_science
[1] - https://en.wikipedia.org/wiki/Theoretical_computer_science
I have to wonder about the big-O notation.
Do people really write f(x) = O(g(x)) ?
Because that doesn't seem to make sense. It could make sense if we read O as an operator (so f is the upper bound on g, but the definition is the other way around) but saying that a function is equal to an upper bound is just odd, even leaving aside the fact that the definition uses "f(x)", i.e., the application of f, to express the function itself.
Do people really write f(x) = O(g(x)) ?
Because that doesn't seem to make sense. It could make sense if we read O as an operator (so f is the upper bound on g, but the definition is the other way around) but saying that a function is equal to an upper bound is just odd, even leaving aside the fact that the definition uses "f(x)", i.e., the application of f, to express the function itself.
Yes they do, and yes this is wrong and everyone knows it, and no we can't do anything about it.
It's not wrong, they just overloaded the = operator for the RuntimeComplexity class ;-P
Jokes aside, in my college we would write something like:
O( f(n) ) = O(n^2) + O(n)
Jokes aside, in my college we would write something like:
O( f(n) ) = O(n^2) + O(n)
Anything using = for a relation that is not symmetric is cursed IMO. More generally, any relation using a symbol that is visually vertically symmetric should be symmetric.
If you use big O notation at both sides, as in my example, it becomes symmetric.
In the same way that ceiling(1.2) = ceiling(1.9) is symmetric, even if their contents are not equal.
In the same way that ceiling(1.2) = ceiling(1.9) is symmetric, even if their contents are not equal.
Yeah, like centered ° for function composition is a pet peeve of mine...
> O( f(n) ) = O(n^2) + O(n)
Naively, one would assume that that implies O( f(n) ) - O(n) = O(n^2), which is not correct. However, O( f(n) ) = O(n^2) + O(n) implies O( f(n) ) = O(n^2), which would have been obvious if proper notation had been used.
Naively, one would assume that that implies O( f(n) ) - O(n) = O(n^2), which is not correct. However, O( f(n) ) = O(n^2) + O(n) implies O( f(n) ) = O(n^2), which would have been obvious if proper notation had been used.
Some textbooks use set membership notation instead: f(x) ∈ O(g(x)). This makes sense if you think of O(g(x)) as the set of all functions with that upper bound. However, the (abuse of) equality notation is often more convenient. For example, f(x) = x^2 + O(x) reads “f(x) is x^2 plus (something bounded by) a linear term”. Writing f(x) = x^2 + g(x) where g(x) ∈ O(x) is more of a hassle.
Is there not a special symbol for the usage you are using for error? A sorta cursive O rather than the standard O.
I prefer O to remain the set of functions usually.
I prefer O to remain the set of functions usually.
It's a convention. Same with small-o and e.g. Taylor polynomials in first-year calculus. Writing e.g. sin(x) = sin(a) + (x - a)cos(a) + o(x - a). We used an equals sign, even though the meaning of this string of characters is "belonging to a class" and not "being equal". It's kind of convenient for long calculations.
It reminds me of the cheatsheets we used to make before math competitions. Many of those things are forever etched in my brain. The only difference is that the ones I made tended to have a lot more freaking triangles.
This seems to be the original publication: https://dl.acm.org/doi/10.1145/242581.242585
A nice collection formuleas that seem usefull when doing theoretical computer science. Maybe could improve it with adding the definition for NP-complete, context free grammars, Turing complete, and such.
I never ran into Escher’s knot before although Im somewhat familiar wit Esche’s work. Does anyone know what its relevance in this context?
Just like the quotes sprinkled around the pages, it seems to be there to avoid a white gap while keeping a more uniform content density across cells.
On which side does it land on the question of utility or futility as to ORM or SQL?
Also, how does the picture of it become useful in the way that all the formulas are useful?
Does any gentlemember have something similar for statistics?
Anybody knows what the grid of numbers on the last page, grouped under "Fibonacci Numbers", is?
Google (Books) yields this: https://books.google.de/books?id=6fJdDwAAQBAJ&pg=PA11&lpg=PA...
An Eulerian Square of order 10.
An Eulerian Square of order 10.
No definition of the Y Combinator ;-)
1. I was a pure math major so I've always liked neat representations of pi such as Wallis' identity and Brouncker's continued fraction, both given on that cheat sheet, but I've never actually seen them used for anything. Where do they come up in CS?
2. If you have to deal with a lot of sums involving hypergeometric terms (such as a many series involving binomial coefficients), the book "A=B" by Marko Petkovsek, Herbert Wilf, and Doron Zeilberger might be of interest. It is downloadable from Wilf's site [1].
[1] https://www2.math.upenn.edu/~wilf/AeqB.html
2. If you have to deal with a lot of sums involving hypergeometric terms (such as a many series involving binomial coefficients), the book "A=B" by Marko Petkovsek, Herbert Wilf, and Doron Zeilberger might be of interest. It is downloadable from Wilf's site [1].
[1] https://www2.math.upenn.edu/~wilf/AeqB.html
it's just cs math, not cs?
My thoughts exactly. Where are the lambda functions, ADTs, lattices, pre/post conditions for formal derivations, category theory? Boolean logic?
Yeah it lacks a few layers. But the embedded ~basics are worth it
It's just math. In my view, CS theory is about computations as a whole. That is – formalisations, languages, algorithms, structures, and design principles.
I don’t know if Pythagorean theorem needs to go on any cheat sheet, whether it’s Math or CS. If you can’t remember that, maybe you are in the wrong place to begin with!
For anyone complaining about the length of the document, I suggested it as a shorter alternative to a original submission [0] where apparently a 212 page document was called a cheatsheet and in fact TCS Cheat Sheet was seen as too concise!
[0] https://news.ycombinator.com/item?id=27468908
[0] https://news.ycombinator.com/item?id=27468908
[deleted]
I just had this thought that it might be super interesting to see a cheat sheet with the current state of academic knowledge in computer science compressed to as few pages as possible. Things that we didn't know at - let's say - 10 or 20 years ago in a format that could be understood by people from those times.
As someone who has no training at all in related subject I really like the graphical aspect of this pdf, it brought me a sense of complete alienness and makes me want to explore. It almost look like something you can find at an art book fair.
The formula for the nth prime number has a bound of O(n / ln n) which makes the lesser terms noise (?) Same w pi(x) (?) Using a bound is more useful:
n ln n + n(ln ln n - 1) < p_n < n ln n + n ln ln n (for n >= 6)Is this generated with LaTeX and is there a source for this? I love the arrangement of cells
Seems to be here: https://www.tug.org/texshowcase/cheat-20131114.tar.gz
(via https://www.tug.org/texshowcase/)
(via https://www.tug.org/texshowcase/)
Thanks!
The original source is very old. Written in plain TeX. Most source files in the TUG TeX Showcase archive [1] are dated 1998. Undoubtedly the first versions were much earlier.
As the TeX Showcase master page [2] notes, the author was Steve Seiden, from LSU. He died in a bike accident in 2002.
[1] https://www.tug.org/texshowcase/cheat-20131114.tar.gz
[2] https://www.tug.org/texshowcase/
As the TeX Showcase master page [2] notes, the author was Steve Seiden, from LSU. He died in a bike accident in 2002.
[1] https://www.tug.org/texshowcase/cheat-20131114.tar.gz
[2] https://www.tug.org/texshowcase/
Thanks! And sorry to hear that...
No mention of (Shannon) entropy? Sort of an important concept.
Seems like some eager undergrad's notebook; an exercise in productive procrastination.
Not sure how useful this is in practice. Probably not very. Thanks nonetheless
Not sure how useful this is in practice. Probably not very. Thanks nonetheless
Maaaan, I was expecting friendly pictures and stuff. Every computer science book looks like this cheat sheet!
It's like the front section of CRC Handbook of Chemistry & Physics. Very dense.
More like a cheat booklet ;-)
Very nice!
Feels like this exists mostly as a prop for immature CS students to "impress" people with.