[HN Gopher] Theoretical Computer Science Cheat Sheet [pdf]
___________________________________________________________________
Theoretical Computer Science Cheat Sheet [pdf]
Author : truly
Score : 282 points
Date : 2021-11-26 06:12 UTC (16 hours ago)
(HTM) web link (www.tug.org)
(TXT) w3m dump (www.tug.org)
| choeger wrote:
| 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.
| FeepingCreature wrote:
| Yes they do, and yes this is wrong and everyone knows it, and
| no we can't do anything about it.
| TuringTest wrote:
| 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)
| reuben364 wrote:
| 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.
| TuringTest wrote:
| 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.
| BlueTemplar wrote:
| Yeah, like centered deg for function composition is a pet
| peeve of mine...
| bjourne wrote:
| > 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.
| yakubin wrote:
| 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.
| mk12 wrote:
| 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.
| whimsicalism wrote:
| 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.
| killjoywashere wrote:
| It's like the front section of CRC Handbook of Chemistry &
| Physics. Very dense.
| gonzus wrote:
| Anybody knows what the grid of numbers on the last page, grouped
| under "Fibonacci Numbers", is?
| Item_Boring wrote:
| Google (Books) yields this:
| https://books.google.de/books?id=6fJdDwAAQBAJ&pg=PA11&lpg=PA...
|
| An Eulerian Square of order 10.
| waynecochran wrote:
| 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)
| rattyc wrote:
| I don't understand any of that
| [deleted]
| tzs wrote:
| 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
| eloeffler wrote:
| Is this generated with LaTeX and is there a source for this? I
| love the arrangement of cells
| garethl wrote:
| Seems to be here:
| https://www.tug.org/texshowcase/cheat-20131114.tar.gz
|
| (via https://www.tug.org/texshowcase/)
| eloeffler wrote:
| Thanks!
| stevesimmons wrote:
| 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/
| eloeffler wrote:
| Thanks! And sorry to hear that...
| xore wrote:
| 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.
| LoyCgg wrote:
| Do you have a cheat sheet for this cheat sheet?
| W0lf wrote:
| 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 :-)
| tester34 wrote:
| it's just cs math, not cs?
| TuringTest wrote:
| My thoughts exactly. Where are the lambda functions, ADTs,
| lattices, pre/post conditions for formal derivations, category
| theory? _Boolean logic?_
| agumonkey wrote:
| Yeah it lacks a few layers. But the embedded ~basics are
| worth it
| dandanua wrote:
| It's just math. In my view, CS theory is about computations as
| a whole. That is - formalisations, languages, algorithms,
| structures, and design principles.
| monopoledance wrote:
| Maaaan, I was expecting friendly pictures and stuff. Every
| computer science book looks like this cheat sheet!
| raxxorrax wrote:
| Useful. I would add maybe abstract algebra, definitions of
| fields, rings, etc. and their respective operations.
| LaPlace/Z-Transformation from system theory.
| sannee wrote:
| Generating functions are already there (that is just math-speak
| for the Z-transform).
| lqet wrote:
| 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, Godels 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 Schonings 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
| SkeuomorphicBee wrote:
| 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.
| emteycz wrote:
| Isn't graph theory a very general (and generally used) math
| concept that is useful in CS, not the other way around?
| zazen wrote:
| Yes, and so is asymptotic analysis and the associated big-O
| notation.
| whimsicalism wrote:
| Yes
| tartoran wrote:
| 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?
| lordnacho wrote:
| Also, how does the picture of it become useful in the way that
| all the formulas are useful?
| gxnxcxcx wrote:
| 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.
| antegamisou wrote:
| 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
| g42gregory wrote:
| 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!
| d33 wrote:
| 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.
| BruceEel wrote:
| More like a cheat booklet ;-) Very nice!
| qsort wrote:
| 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.
| arethuza wrote:
| No definition of the Y Combinator ;-)
| fjfaase wrote:
| 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.
| alpaca128 wrote:
| 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.
| AstroDogCatcher wrote:
| Feels like this exists mostly as a prop for immature CS students
| to "impress" people with.
| mdp2021 wrote:
| Does any gentlemember have something similar for statistics?
| nlitsme wrote:
| This seems to be the original publication:
| https://dl.acm.org/doi/10.1145/242581.242585
| pyentropy wrote:
| 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
| lordnacho wrote:
| 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.
| GuB-42 wrote:
| Interesting that the periodic table doesn't go beyond element
| 103 (as Lw, not Lr), we are at 118 (Og) now. Periodic table are
| a good way to date things. Looking at the footnote, the edition
| is from 1972.
|
| How can you have Verilog, btw? It is from 1984.
| lordnacho wrote:
| I found an updated version online
| jonsen wrote:
| I own this one. More relevant in my opinion:
|
| https://www.amazon.com/Handbook-Mathematics-Computational-Sc...
| unbanned wrote:
| 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
| Tade0 wrote:
| No mention of (Shannon) entropy? Sort of an important concept.
| osivertsson wrote:
| 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 ;)
| OskarS wrote:
| 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.
| whimsicalism wrote:
| 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.
| JadeNB wrote:
| > 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.)
___________________________________________________________________
(page generated 2021-11-26 23:02 UTC)