20 ms·

Equations True Computer Science Geeks Should (at Least Pretend to) Know

288 points by gmoes 15y ago

orenmazor 15y ago
I know all those. ish. thanks for morning ego boost!
pork 15y ago
The Y Combinator and the pumping lemma seem a bit contrived on that list, especially the former. I would add the maximum margin separation equation, which underlies many modern machine learning methods like SVMs and MMMF, and the P=NP equality question.
- Homunculiheaded 15y ago
  Understanding the pumping lemma is essential to really understanding why regular languages are limited. Which in the real world is important for quickly assessing the question of "can I hack this solution together with some clever regexps or do I need a real parser?" I'll agree that the y-combinator is less essential, however if you even have a sense of what's going on it means that you have an understanding of the basic framework of functional programming and a minimal grasp of the lambda calculus
  - makomk 15y ago
    Not really. You can understand why regular languages are limited with a simple counting argument; the pumping lemma follows on from that relatively easily, but it doesn't really add much understanding IMO.
  - wging 15y ago
    The pumping lemma is cool, but the Myhill-Nerode theorem is more powerful (as someone mentioned). I think, too, that what was meant by 'contrived' was that the pumping lemma is not really an equation. But you don't get hits if you talk about the top ten theorems CS geeks should know...
rcfox 15y ago
It'd be nice if the author actually stated why these algorithms are important to know. Give a use case, rather than "this comes up sometimes."
- sk5t 15y ago
  Agreed, this article was a very poor read from the perspective of a programmer (yours truly) having a working familiarity with only two or three of these concepts. Given the article's slapdash, loosely-coherent English and tendency to pad out each equation's section with references to even more equations--and not explanation of usefulness--I wish I hadn't tried to read it, for it was very frustrating. I suppose the article might provoke interesting discussion among the mathy set, the same way that a list of "top patterns" might start a discussion among OO fans.
  - krobertson 15y ago
    I had to actually double check if the author was from the US or not, since in some places it was just so incomprehensible. I agree the applications were glossed over or skipped, but that is probably the most interesting aspect of the equations as well. Without practical information, the article is sorely missing true sustenance.
    - ChuckMcM 15y ago
      This effect is often true for people whose native language is math :-) But to be fair most disciplines have their own jargon, math happens to have its own keyboard too.
      - slowpoke 15y ago
        Most other disciplines don't try to force their jargon onto other fields though. Math often does. Also, I'd generally say that almost all jargon is bad. A quote that's frequently attributed to Einstein says that "If you cannot explain something in simple terms, you do not have adequately understood it". Math and science in general should take this to heart, because I feel that many people have forgotten this or never really understood it in the first place.
deleted 15y ago
[deleted]
cfontes 15y ago
This kind of list popped in HN a few weeks ago, almost the same stuff but with 10 equations.
robinhouston 15y ago
I would take issue with the pumping lemma for regular languages here. The formal statement of the lemma is outrageously complicated, which makes it really difficult to understand and use. The only good justification I’ve heard for including this result in a CS curriculum is that it’s a good warm-up for the pumping lemma for context-free languages, which is more useful. If you actually ever find yourself needing to show that a particular language is non-regular, it’s almost always clearer to use an ad hoc argument or appeal to the Myhill-Nerode theorem. Actually the latter is much better, because Myhill-Nerode completely characterises the regular languages, whereas there are non-regular languages that pass the pumping lemma test.[1] 1. http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Lemma_not_sufficient http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_langu...
- algorias 15y ago
  >there are non-regular languages that pass the pumping lemma test Can you give an example of that? You may be right, but I'm having a hard time coming up with a language that is not regular but fulfils the pumping lemma.
  - robinhouston 15y ago
    Sure, there’s an example in the Wikipedia article linked from the footnote in my comment above: the language consisting of all strings over the alphabet {0,1,2,3} with a substring of length 3 including a duplicate character, as well as all strings over this alphabet where precisely 1/7 of the string's characters are 3's. As you can see, this example is a little complicated – and I don’t know a simpler one, so I’m not surprised you struggled to just come up with an example off the top of your head.
numeromancer 15y ago
I should think the Master Theorem would be included: http://en.wikipedia.org/wiki/Master_theorem http://en.wikipedia.org/wiki/Master_theorem or better, http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method.
methodin 15y ago
I really wish my brain didn't gloss over the first time I see a math symbol. All of this stuff seems intriguing but it's almost as if I'm hardwired to translate all those symbols into mush. I'd be much more interested in seeing the equivalent code snippets these ideas express.
- GuiA 15y ago
  For several of the equations presented, there's not really a "code equivalent". And for most of the others, presenting it in code form would make it much more verbose and complex than it needs to be. In a way, it's already written in code – it's just been written by mathematicians :) It can be a bit daunting at first, but I find mathematical concepts and notation extremely useful tools for programmers, especially when designing algorithms. It allows you to express powerful, abstract ideas in a few lines whereas the same reasoning in pseudo-code would take much more time and effort. I'm glad my undergraduate program was heavy on the math (although I hated it at the time)– it made graduate CS courses easier to understand, and programming easier for me in the long term. I actually miss my pure math courses now.
  - stan_rogers 15y ago
    That's because mathematical notation is context-bound and telegraphic. Gerry Sussman has gone so far as to call it "Impressionistic". Beyond basic arithmetic and elementary algebra, it is much more concise than it is precise -- it is often inconsistent (the "power" in cos^2 x doesn't mean the same thing as it does in cos^-1 x, for instance), and there's a lot of hand-waviness (and sometimes some outright lies) in order to make the notation concise. It's a useful jargon for the initiated, but it is hardly self-explanatory even if you know what the individual symbols are supposed to mean. A code-like representation may have the disadvantage of being more verbose, but it has the advantage of being unambiguous. It gives up conciseness in favour of precision. And no, it is not impossible to represent mathematical concepts in a code-like manner -- it just forces you to actually say all of what you mean rather than using an ambiguous and incomplete shorthand.
- robbles 15y ago
  I've found http://en.wikipedia.org/wiki/Table_of_mathematical_symbols http://en.wikipedia.org/wiki/Table_of_mathematical_symbols to be helpful when deciphering formulas. It's hard to remember what all the notation means sometimes.
henning 15y ago
Since it seems like the multicore thing is here to stay, may I suggest that if you are doing anything parallel you should know about Amdahl's law: http://en.wikipedia.org/wiki/Parallel_computing#Amdahl.27s_law_and_Gustafson.27s_law http://en.wikipedia.org/wiki/Parallel_computing#Amdahl.27s_l...
- Splines 15y ago
  Huh, that's interesting. I never considered the similarities between parallel processing and people management until today.
  - jerf 15y ago
    http://en.wikipedia.org/wiki/Queueing_theory http://en.wikipedia.org/wiki/Queueing_theory
    - emmelaich 15y ago
      Relevant to Amdahl's Law (it being a more general form) and Queueing Theory is : http://en.wikipedia.org/wiki/Neil_Gunther#Universal_Law_of_Computational_Scalability http://en.wikipedia.org/wiki/Neil_Gunther#Universal_Law_of_C...
joezydeco 15y ago
I was hoping Fitts's Law would make the list, considering a lot of people here are doing UI/UX whether they realize it or not.
StavrosK 15y ago
I'm sorry for being somewhat off topic, but is it too hard to try and write coherently? The author's run-on, stream-of-consciousness style, together with the random use of punctuation marks, was tiring to read.
- grampajoe 15y ago
  Writing skills are always relevant. The lack of them in this article made me stop reading before getting to any actual content.
  - StavrosK 15y ago
    Indeed, and I'm not demanding that people be novelists or anything, you just have to master basic punctuation and spelling to make the reader's life easier.
psykotic 15y ago
More fundamental than Bayes's theorem is the probabilistic counterpart of modus ponens: P(A/\B) = P(B|A) P(A). This corresponds to the logical rule of inference A, A->B |- A/\B. Note that modus ponens is usually stated in the form A, A->B |- B. But this throws away useful information, namely that proposition A is true, so it's a weaker form. Bayes's theorem is a direct consequence of this axiom and the commutativity of conjunction.
- deleted 15y ago
  [deleted]
- snippyhollow 15y ago
  In other words, modus ponens is: P(A=true)=1, P(B=true|A=true)=1 |- P(B=true) = 1 Let P'(A) be the distribution on A when we know nothing about B (in a world with only A and B). Plausible reasoning is possible through Bayes/joint-conditional probability rule and yields: P(B=true|A=true)=1, P(B=true)=1 |- P(A=true) > P'(A=true) where logic alone can't conclude (A->B, B |- ?) Also: P(B=true|A=true)=1, P(A=false)=1 |- P(B=true) < P'(B=true)
peterwwillis 15y ago
So, I take it I shouldn't even consider getting a CS degree since I really suck at math?
- pnathan 15y ago
  There is a growing body of science that indicates talent matters a great deal less than hard work. Certainly I consider myself relatively slow, but with enough perseverance, I get told I am smart. :)
- vosper 15y ago
  Don't let this put you off! I have a CS degree, and I also pretty much suck at math (at least compared to many CS majors). There are many paths you can take through a CS degree, and it's entirely possible to come out with useful and applicable knowledge without having to deep-dive in math. It just means you're more likely to end up in, say, web-dev than building 3D graphics engines. For me that's been a perfectly acceptable outcome. And besides, a CS degree takes a few years - there's plenty of time to brush up on math if you're really interested.
- nassosdim 15y ago
  Don't let this be intimidating to you - instead of asking yourself "how come I don't know this?" ask yourself "how can I learn more about this?". This might sound cheesy and simplified but it's as simple as "nobody was born knowing this". I'm 31 and I wish I had the money to go back in education and learn all of this with the official way but for now I'm just picking resources on the web and who knows? It just might happen... Enough about me. If you want it, go get it. Period.
- georgieporgie 15y ago
  I have a CS degree, and a math minor. After over a decade of professional work, I remember hardly anything of my math minor, and very little of the mathematical content of my CS major. If you want to do 'interesting' stuff, you'll need solid math skills. If your goal is to make money, you will likely do fine with average math skills. Oddly, however, many employers currently interview for CS/math knowledge even though their jobs will never, ever make use of such knowledge.
kevinalexbrown 15y ago
Bayes Theorem isn't totally at the heart of Bayesian v non-Bayesian statistics. Bayes Theorem can still be true if you're in a strictly frequentist framework.
- lutorm 15y ago
  Bayes Theorem can still be true if you're in a strictly frequentist framework. Can?? When is it not true? It's a theorem, after all.
  - kevinalexbrown 15y ago
    Nitpick much? I meant more along the lines of when the assumptions aren't met, e.g. P(B) == 0. Or, where unitarity in physics isn't met: http://en.wikipedia.org/wiki/Unitarity_(physics) http://en.wikipedia.org/wiki/Unitarity_(physics)
king_magic 15y ago
Well, after 6 years of professional software engineering after finishing my BS in CS, the only things on that list that I've came anywhere close to using are the natural join and Demorgan's laws. I think this is a pretty silly post, to be honest. CS covers so much, and everytime I see a list of "things you should know", I have to resist the urge to roll my eyes and ignore it. But then I read it, and inevitably roll my eyes anyway.
- mmaunder 15y ago
  At two jobs now I've had a conversation with talented comp sci grads and we all agreed 99% of programming is drudgery and the 1% that requires you to turn off your music and sit in dead silence is rare and still not as challenging as comp sci syllabuses (syllabi?) would suggest. An unfortunate side-effect is that many people who could have become highly productive mid-level programmers are scared off because they don't know advanced math.
  - king_magic 15y ago
    I disagree. Programming is math. Highly advanced math, in fact. It's just a different type of math. And the 11 equations in the OP's article just barely touches on what CS is about. There is far more to it than that.
    - fragsworth 15y ago
      You can disagree all you want but it is pretty much objective fact that in practice, especially in the world of business, 99% of programming is not advanced at all. CS, which is not just programming, may be advanced, but you do not see the advanced concepts emerging very often in day-to-day programming.
      - tikhonj 15y ago
        However, the real question is whether there's no advanced stuff because of the domain or because of the people who work there. If enough people working at a company don't like advanced math, it means that they will not use it and if you use it, your code will be harder for them to maintain, so you don't use it either. I suspect if everybody had a better grasp of these ideas, you would see them used more often.
cheez 15y ago
P(Poster is less than 30 years old) = .9999999999999
tomstuart 15y ago
Although they're not really "equations", I'd have liked to see some results from computation theory in this list, because they're often deep and beautiful without necessarily being difficult to formulate or understand. They also tend to be informative in a useful way rather than feeling too abstract to be relevant. For example: the halting problem. Isn't it interesting that you can't write a computer program which can decide (in general) whether another program terminates? The proof is simple and it gives you a real tool to help you avoid trying to solve impossible problems. It's good to know the limits of your craft.
lell 15y ago
There's a small error in the formula for O(N): the way he's written it it looks like for all n, there is a k such that kg(n) >= f(n), ie k depends on n so take k = f(n)/g(n) and all nonzero functions trivially satisfy it. It should be there exists a k such that for all n kg(n) >= f(n). Pedantic I know, but on the other hand I wouldn't call these "beautiful equations" associated with O(N), I'd instead call them the definition of O(N). There's also o(f(n)), g(n) is a member of o(f(n)) if the limit as n goes to infinity of g(n)/f(n) is zero. Finally, there is asymptotic equality: f(n) ~ g(n) if the limit as n goes to infinite of g(n)/f(n) = 1. O,o and ~ are all subtly different, but if you're just trying to prove upper bounds then O(f(n)) is the one that comes up most frequently, which is why it's probably the only sort of asymptotic analysis most CS grads know.
krupan 15y ago
Shannon's Information Theory, Eigenvector, DeMorgan's Laws, etc. None of those names are meaningful or descriptive. And then the greek letters and made up symbols. Math could learn something from Computer Science: https://www.google.com/search?q=readable+code https://www.google.com/search?q=readable+code
- anrope 15y ago
  Eigenvector isn't that bad, it's just not english: "The prefix eigen- is adopted from the German word "eigen" for "own"[1] in the sense of a characteristic description" (from wikipedia) I think Shannon's Information Theory is pretty fair too. It's about how much information is in a message. Plus, Computer Science has it's own grievous names: A* search, B* search, B tree, B+ tree, B* tree. That always drove me nuts.
  - eru 15y ago
    And lots of algorithms named after people. Which is fine (we have lots of things named after people in math, too), but not descriptive.
- eru 15y ago
  Most of math notation is optimized for allowing people talking to each other about abstract concepts to use blackboards and chalk as memory aids. Mathematical notation is always supposed to be used in a context similar to literal programming.
jergosh 15y ago
Oddly enough I never really used any of these while studying CS. Now that I'm in bioinformatics, some of the stuff is commonly used, particularly Bayes' theorem and information theory.
k4st 15y ago
I would prefer to see the Cook-Levin theorem in place of the pumping lemma.
raffi 15y ago
Nope.
mcshaner1 15y ago
Little's Law is probably CS folks should know too. It is relatively simple, but useful https://en.wikipedia.org/wiki/Little%27s_law https://en.wikipedia.org/wiki/Little%27s_law
hexagonc 15y ago
Here's a real simple and practical equation: 1+2+3+4 . . . N = N(N+1)/2 This equation represents the number of edges on a complete graph with N+1 vertices or the number of possible pairings given N+1 objects. Useful when estimating O(N) for certain algorithms that involve comparing an item to every other item in a set.
- eru 15y ago
  Please be careful how you use big-O notation here.
- Natsu 15y ago
  It's more useful if you know how to prove it: just add the series to itself written backwards, then divide by two. One of my math professors said that this and multiplying by things equal to one were among the tricks he used most often.
zerostar07 15y ago
Amusing how the original wired article calls the greek lambda "the triangle thing with no bottom"

288 points by gmoes 15y ago

I know all those. ish. thanks for morning ego boost!

pork 15y ago

The Y Combinator and the pumping lemma seem a bit contrived on that list, especially the former. I would add the maximum margin separation equation, which underlies many modern machine learning methods like SVMs and MMMF, and the P=NP equality question.

Homunculiheaded 15y ago
Understanding the pumping lemma is essential to really understanding why regular languages are limited. Which in the real world is important for quickly assessing the question of "can I hack this solution together with some clever regexps or do I need a real parser?" I'll agree that the y-combinator is less essential, however if you even have a sense of what's going on it means that you have an understanding of the basic framework of functional programming and a minimal grasp of the lambda calculus
- makomk 15y ago
  Not really. You can understand why regular languages are limited with a simple counting argument; the pumping lemma follows on from that relatively easily, but it doesn't really add much understanding IMO.
- wging 15y ago
  The pumping lemma is cool, but the Myhill-Nerode theorem is more powerful (as someone mentioned). I think, too, that what was meant by 'contrived' was that the pumping lemma is not really an equation. But you don't get hits if you talk about the top ten theorems CS geeks should know...

rcfox 15y ago

It'd be nice if the author actually stated why these algorithms are important to know. Give a use case, rather than "this comes up sometimes."

sk5t 15y ago
Agreed, this article was a very poor read from the perspective of a programmer (yours truly) having a working familiarity with only two or three of these concepts. Given the article's slapdash, loosely-coherent English and tendency to pad out each equation's section with references to even more equations--and not explanation of usefulness--I wish I hadn't tried to read it, for it was very frustrating. I suppose the article might provoke interesting discussion among the mathy set, the same way that a list of "top patterns" might start a discussion among OO fans.
- krobertson 15y ago
  I had to actually double check if the author was from the US or not, since in some places it was just so incomprehensible. I agree the applications were glossed over or skipped, but that is probably the most interesting aspect of the equations as well. Without practical information, the article is sorely missing true sustenance.
  - ChuckMcM 15y ago
    This effect is often true for people whose native language is math :-) But to be fair most disciplines have their own jargon, math happens to have its own keyboard too.
    - slowpoke 15y ago
      Most other disciplines don't try to force their jargon onto other fields though. Math often does. Also, I'd generally say that almost all jargon is bad. A quote that's frequently attributed to Einstein says that "If you cannot explain something in simple terms, you do not have adequately understood it". Math and science in general should take this to heart, because I feel that many people have forgotten this or never really understood it in the first place.

deleted 15y ago

[deleted]

cfontes 15y ago

This kind of list popped in HN a few weeks ago, almost the same stuff but with 10 equations.

robinhouston 15y ago

I would take issue with the pumping lemma for regular languages here. The formal statement of the lemma is outrageously complicated, which makes it really difficult to understand and use. The only good justification I’ve heard for including this result in a CS curriculum is that it’s a good warm-up for the pumping lemma for context-free languages, which is more useful. If you actually ever find yourself needing to show that a particular language is non-regular, it’s almost always clearer to use an ad hoc argument or appeal to the Myhill-Nerode theorem. Actually the latter is much better, because Myhill-Nerode completely characterises the regular languages, whereas there are non-regular languages that pass the pumping lemma test.[1] 1. http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Lemma_not_sufficient http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_langu...

algorias 15y ago
>there are non-regular languages that pass the pumping lemma test Can you give an example of that? You may be right, but I'm having a hard time coming up with a language that is not regular but fulfils the pumping lemma.
- robinhouston 15y ago
  Sure, there’s an example in the Wikipedia article linked from the footnote in my comment above: the language consisting of all strings over the alphabet {0,1,2,3} with a substring of length 3 including a duplicate character, as well as all strings over this alphabet where precisely 1/7 of the string's characters are 3's. As you can see, this example is a little complicated – and I don’t know a simpler one, so I’m not surprised you struggled to just come up with an example off the top of your head.

numeromancer 15y ago

I should think the Master Theorem would be included: http://en.wikipedia.org/wiki/Master_theorem http://en.wikipedia.org/wiki/Master_theorem or better, http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method.

methodin 15y ago

I really wish my brain didn't gloss over the first time I see a math symbol. All of this stuff seems intriguing but it's almost as if I'm hardwired to translate all those symbols into mush. I'd be much more interested in seeing the equivalent code snippets these ideas express.

GuiA 15y ago
For several of the equations presented, there's not really a "code equivalent". And for most of the others, presenting it in code form would make it much more verbose and complex than it needs to be. In a way, it's already written in code – it's just been written by mathematicians :) It can be a bit daunting at first, but I find mathematical concepts and notation extremely useful tools for programmers, especially when designing algorithms. It allows you to express powerful, abstract ideas in a few lines whereas the same reasoning in pseudo-code would take much more time and effort. I'm glad my undergraduate program was heavy on the math (although I hated it at the time)– it made graduate CS courses easier to understand, and programming easier for me in the long term. I actually miss my pure math courses now.
- stan_rogers 15y ago
  That's because mathematical notation is context-bound and telegraphic. Gerry Sussman has gone so far as to call it "Impressionistic". Beyond basic arithmetic and elementary algebra, it is much more concise than it is precise -- it is often inconsistent (the "power" in cos^2 x doesn't mean the same thing as it does in cos^-1 x, for instance), and there's a lot of hand-waviness (and sometimes some outright lies) in order to make the notation concise. It's a useful jargon for the initiated, but it is hardly self-explanatory even if you know what the individual symbols are supposed to mean. A code-like representation may have the disadvantage of being more verbose, but it has the advantage of being unambiguous. It gives up conciseness in favour of precision. And no, it is not impossible to represent mathematical concepts in a code-like manner -- it just forces you to actually say all of what you mean rather than using an ambiguous and incomplete shorthand.
robbles 15y ago
I've found http://en.wikipedia.org/wiki/Table_of_mathematical_symbols http://en.wikipedia.org/wiki/Table_of_mathematical_symbols to be helpful when deciphering formulas. It's hard to remember what all the notation means sometimes.

henning 15y ago

Since it seems like the multicore thing is here to stay, may I suggest that if you are doing anything parallel you should know about Amdahl's law: http://en.wikipedia.org/wiki/Parallel_computing#Amdahl.27s_law_and_Gustafson.27s_law http://en.wikipedia.org/wiki/Parallel_computing#Amdahl.27s_l...

Splines 15y ago
Huh, that's interesting. I never considered the similarities between parallel processing and people management until today.
- jerf 15y ago
  http://en.wikipedia.org/wiki/Queueing_theory http://en.wikipedia.org/wiki/Queueing_theory
  - emmelaich 15y ago
    Relevant to Amdahl's Law (it being a more general form) and Queueing Theory is : http://en.wikipedia.org/wiki/Neil_Gunther#Universal_Law_of_Computational_Scalability http://en.wikipedia.org/wiki/Neil_Gunther#Universal_Law_of_C...

joezydeco 15y ago

I was hoping Fitts's Law would make the list, considering a lot of people here are doing UI/UX whether they realize it or not.

StavrosK 15y ago

I'm sorry for being somewhat off topic, but is it too hard to try and write coherently? The author's run-on, stream-of-consciousness style, together with the random use of punctuation marks, was tiring to read.

grampajoe 15y ago
Writing skills are always relevant. The lack of them in this article made me stop reading before getting to any actual content.
- StavrosK 15y ago
  Indeed, and I'm not demanding that people be novelists or anything, you just have to master basic punctuation and spelling to make the reader's life easier.

psykotic 15y ago

More fundamental than Bayes's theorem is the probabilistic counterpart of modus ponens: P(A/\B) = P(B|A) P(A). This corresponds to the logical rule of inference A, A->B |- A/\B. Note that modus ponens is usually stated in the form A, A->B |- B. But this throws away useful information, namely that proposition A is true, so it's a weaker form. Bayes's theorem is a direct consequence of this axiom and the commutativity of conjunction.

deleted 15y ago
[deleted]
snippyhollow 15y ago
In other words, modus ponens is: P(A=true)=1, P(B=true|A=true)=1 |- P(B=true) = 1 Let P'(A) be the distribution on A when we know nothing about B (in a world with only A and B). Plausible reasoning is possible through Bayes/joint-conditional probability rule and yields: P(B=true|A=true)=1, P(B=true)=1 |- P(A=true) > P'(A=true) where logic alone can't conclude (A->B, B |- ?) Also: P(B=true|A=true)=1, P(A=false)=1 |- P(B=true) < P'(B=true)

peterwwillis 15y ago

So, I take it I shouldn't even consider getting a CS degree since I really suck at math?

pnathan 15y ago
There is a growing body of science that indicates talent matters a great deal less than hard work. Certainly I consider myself relatively slow, but with enough perseverance, I get told I am smart. :)
vosper 15y ago
Don't let this put you off! I have a CS degree, and I also pretty much suck at math (at least compared to many CS majors). There are many paths you can take through a CS degree, and it's entirely possible to come out with useful and applicable knowledge without having to deep-dive in math. It just means you're more likely to end up in, say, web-dev than building 3D graphics engines. For me that's been a perfectly acceptable outcome. And besides, a CS degree takes a few years - there's plenty of time to brush up on math if you're really interested.
nassosdim 15y ago
Don't let this be intimidating to you - instead of asking yourself "how come I don't know this?" ask yourself "how can I learn more about this?". This might sound cheesy and simplified but it's as simple as "nobody was born knowing this". I'm 31 and I wish I had the money to go back in education and learn all of this with the official way but for now I'm just picking resources on the web and who knows? It just might happen... Enough about me. If you want it, go get it. Period.
georgieporgie 15y ago
I have a CS degree, and a math minor. After over a decade of professional work, I remember hardly anything of my math minor, and very little of the mathematical content of my CS major. If you want to do 'interesting' stuff, you'll need solid math skills. If your goal is to make money, you will likely do fine with average math skills. Oddly, however, many employers currently interview for CS/math knowledge even though their jobs will never, ever make use of such knowledge.

kevinalexbrown 15y ago

Bayes Theorem isn't totally at the heart of Bayesian v non-Bayesian statistics. Bayes Theorem can still be true if you're in a strictly frequentist framework.

lutorm 15y ago
Bayes Theorem can still be true if you're in a strictly frequentist framework. Can?? When is it not true? It's a theorem, after all.
- kevinalexbrown 15y ago
  Nitpick much? I meant more along the lines of when the assumptions aren't met, e.g. P(B) == 0. Or, where unitarity in physics isn't met: http://en.wikipedia.org/wiki/Unitarity_(physics) http://en.wikipedia.org/wiki/Unitarity_(physics)

king_magic 15y ago

Well, after 6 years of professional software engineering after finishing my BS in CS, the only things on that list that I've came anywhere close to using are the natural join and Demorgan's laws. I think this is a pretty silly post, to be honest. CS covers so much, and everytime I see a list of "things you should know", I have to resist the urge to roll my eyes and ignore it. But then I read it, and inevitably roll my eyes anyway.

mmaunder 15y ago
At two jobs now I've had a conversation with talented comp sci grads and we all agreed 99% of programming is drudgery and the 1% that requires you to turn off your music and sit in dead silence is rare and still not as challenging as comp sci syllabuses (syllabi?) would suggest. An unfortunate side-effect is that many people who could have become highly productive mid-level programmers are scared off because they don't know advanced math.
- king_magic 15y ago
  I disagree. Programming is math. Highly advanced math, in fact. It's just a different type of math. And the 11 equations in the OP's article just barely touches on what CS is about. There is far more to it than that.
  - fragsworth 15y ago
    You can disagree all you want but it is pretty much objective fact that in practice, especially in the world of business, 99% of programming is not advanced at all. CS, which is not just programming, may be advanced, but you do not see the advanced concepts emerging very often in day-to-day programming.
    - tikhonj 15y ago
      However, the real question is whether there's no advanced stuff because of the domain or because of the people who work there. If enough people working at a company don't like advanced math, it means that they will not use it and if you use it, your code will be harder for them to maintain, so you don't use it either. I suspect if everybody had a better grasp of these ideas, you would see them used more often.

cheez 15y ago

P(Poster is less than 30 years old) = .9999999999999

tomstuart 15y ago

Although they're not really "equations", I'd have liked to see some results from computation theory in this list, because they're often deep and beautiful without necessarily being difficult to formulate or understand. They also tend to be informative in a useful way rather than feeling too abstract to be relevant. For example: the halting problem. Isn't it interesting that you can't write a computer program which can decide (in general) whether another program terminates? The proof is simple and it gives you a real tool to help you avoid trying to solve impossible problems. It's good to know the limits of your craft.

lell 15y ago

There's a small error in the formula for O(N): the way he's written it it looks like for all n, there is a k such that kg(n) >= f(n), ie k depends on n so take k = f(n)/g(n) and all nonzero functions trivially satisfy it. It should be there exists a k such that for all n kg(n) >= f(n). Pedantic I know, but on the other hand I wouldn't call these "beautiful equations" associated with O(N), I'd instead call them the definition of O(N). There's also o(f(n)), g(n) is a member of o(f(n)) if the limit as n goes to infinity of g(n)/f(n) is zero. Finally, there is asymptotic equality: f(n) ~ g(n) if the limit as n goes to infinite of g(n)/f(n) = 1. O,o and ~ are all subtly different, but if you're just trying to prove upper bounds then O(f(n)) is the one that comes up most frequently, which is why it's probably the only sort of asymptotic analysis most CS grads know.

krupan 15y ago

Shannon's Information Theory, Eigenvector, DeMorgan's Laws, etc. None of those names are meaningful or descriptive. And then the greek letters and made up symbols. Math could learn something from Computer Science: https://www.google.com/search?q=readable+code https://www.google.com/search?q=readable+code

anrope 15y ago
Eigenvector isn't that bad, it's just not english: "The prefix eigen- is adopted from the German word "eigen" for "own"[1] in the sense of a characteristic description" (from wikipedia) I think Shannon's Information Theory is pretty fair too. It's about how much information is in a message. Plus, Computer Science has it's own grievous names: A* search, B* search, B tree, B+ tree, B* tree. That always drove me nuts.
- eru 15y ago
  And lots of algorithms named after people. Which is fine (we have lots of things named after people in math, too), but not descriptive.
eru 15y ago
Most of math notation is optimized for allowing people talking to each other about abstract concepts to use blackboards and chalk as memory aids. Mathematical notation is always supposed to be used in a context similar to literal programming.

jergosh 15y ago

Oddly enough I never really used any of these while studying CS. Now that I'm in bioinformatics, some of the stuff is commonly used, particularly Bayes' theorem and information theory.

k4st 15y ago

I would prefer to see the Cook-Levin theorem in place of the pumping lemma.

raffi 15y ago

Nope.

mcshaner1 15y ago

Little's Law is probably CS folks should know too. It is relatively simple, but useful https://en.wikipedia.org/wiki/Little%27s_law https://en.wikipedia.org/wiki/Little%27s_law

hexagonc 15y ago

Here's a real simple and practical equation: 1+2+3+4 . . . N = N(N+1)/2 This equation represents the number of edges on a complete graph with N+1 vertices or the number of possible pairings given N+1 objects. Useful when estimating O(N) for certain algorithms that involve comparing an item to every other item in a set.

eru 15y ago
Please be careful how you use big-O notation here.
Natsu 15y ago
It's more useful if you know how to prove it: just add the series to itself written backwards, then divide by two. One of my math professors said that this and multiplying by things equal to one were among the tricks he used most often.

zerostar07 15y ago

Amusing how the original wired article calls the greek lambda "the triangle thing with no bottom"