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.
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.
I assume you overlooked O(n). You've probably used Bayes' theorem and the binomial coefficient, if only indirectly.
But I tend to agree with you: many of these are skewed by the author's perspective on what should be considered foundational. Someone doing webdev will not ever calculate eigenvectors. Someone doing machine learning will not be able to avoid them.
I think it's important in this situations to not confuse Computer Science with what we, as "software engineers" or "applications developers" or "programmers", do for 99.9% of our day. For most of us, what we do is as much Computer Science as the use of a protractor is geometry.
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]
>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.
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.
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.
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.
I have the same problem, but I think I figured out a way around it.
You have to fight the gloss-over effect. It takes conscious effort. Remember that "deliberate practice" all those blog entries say it takes to master something? Well, same thing. You have to deliberately overcome your brain's tendency to go "math is hard, let's go shopping!" Eventually you'll be able to look at an equation and recognize patterns. When I hit the link I was like "Oh, man, MATH, so bo-- hey wait, that's Bayes's theorem! I know this!" (Yes, just like the Jurassic Park girl.)
So keep working at it. Maybe you'll want to try -- gasp! -- actually cracking a math book and studying the material they present.
I pretty much feel the same way but I feel like I'm up for the challenge and I keep trying to cover as much as possible I can in my free time (a side-effect of my unemployment).
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.
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)
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.
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.
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
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:
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.
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.
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.
Mathematics is just a ladder of abstractions. If a piece of mathematics seems intimidating, it's just because you're looking too far up the ladder from where you're currently standing. Anyone can climb it, one careful step at a time, to reach a level they're interested in; by the time they get there, they'll have learned enough of the underlying abstractions to make the intimidating thing now seem obvious, or at least sensible.
So don't be afraid! (And besides, there are certainly many CS degrees which don't require anywhere near the amount of mathematical sophistication mentioned in this article.)
If you suck at math, you SHOULD get a math heavy degree if the subject interests you. That's what I did, with my EE degree. To be fair, it isn't that I sucked at math so much as I didn't know very much of it.
Still, I think you should look at college as a way to learn what you don't know and get better where you suck, rather than bolster your strengths and avoid your weaknesses. For example, I wrote really well in high school and at one point wanted to get an English degree. Then I thought, "I already know how to write, let's put that tuition money to better use" and started considering math and science heavy options.
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.
Thanks everyone for the words of encouragement, but when I was going to school it would take me 4 hours to complete 15 simple homework math equations, even with the ritalin. 'Hard work' in the form of 4 years of that stuff would make me commit suicide.
Moreover, I just don't care to understand complex math. I do want to know how to design compilers and write embedded kernel drivers. If advanced math is required to be able to do these things, CS isn't for me.
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.
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.
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.
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.
[+] [-] king_magic|14 years ago|reply
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|14 years ago|reply
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.
[+] [-] kleiba|14 years ago|reply
[+] [-] abscondment|14 years ago|reply
But I tend to agree with you: many of these are skewed by the author's perspective on what should be considered foundational. Someone doing webdev will not ever calculate eigenvectors. Someone doing machine learning will not be able to avoid them.
[+] [-] docgnome|14 years ago|reply
[+] [-] henning|14 years ago|reply
[+] [-] Splines|14 years ago|reply
[+] [-] robinhouston|14 years ago|reply
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_langu...
[+] [-] algorias|14 years ago|reply
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.
[+] [-] rcfox|14 years ago|reply
[+] [-] sk5t|14 years ago|reply
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.
[+] [-] methodin|14 years ago|reply
[+] [-] GuiA|14 years ago|reply
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.
[+] [-] bitwize|14 years ago|reply
You have to fight the gloss-over effect. It takes conscious effort. Remember that "deliberate practice" all those blog entries say it takes to master something? Well, same thing. You have to deliberately overcome your brain's tendency to go "math is hard, let's go shopping!" Eventually you'll be able to look at an equation and recognize patterns. When I hit the link I was like "Oh, man, MATH, so bo-- hey wait, that's Bayes's theorem! I know this!" (Yes, just like the Jurassic Park girl.)
So keep working at it. Maybe you'll want to try -- gasp! -- actually cracking a math book and studying the material they present.
[+] [-] robbles|14 years ago|reply
[+] [-] nassosdim|14 years ago|reply
[+] [-] randysavage25|14 years ago|reply
[+] [-] numeromancer|14 years ago|reply
http://en.wikipedia.org/wiki/Master_theorem
or better,
http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method.
[+] [-] psykotic|14 years ago|reply
Bayes's theorem is a direct consequence of this axiom and the commutativity of conjunction.
[+] [-] snippyhollow|14 years ago|reply
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)
[+] [-] unknown|14 years ago|reply
[deleted]
[+] [-] tomstuart|14 years ago|reply
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.
[+] [-] pork|14 years ago|reply
[+] [-] Homunculiheaded|14 years ago|reply
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
[+] [-] krupan|14 years ago|reply
https://www.google.com/search?q=readable+code
[+] [-] anrope|14 years ago|reply
"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|14 years ago|reply
Mathematical notation is always supposed to be used in a context similar to literal programming.
[+] [-] joezydeco|14 years ago|reply
[+] [-] StavrosK|14 years ago|reply
[+] [-] grampajoe|14 years ago|reply
[+] [-] cheez|14 years ago|reply
[+] [-] lell|14 years ago|reply
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.
[+] [-] hexagonc|14 years ago|reply
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.
[+] [-] Natsu|14 years ago|reply
One of my math professors said that this and multiplying by things equal to one were among the tricks he used most often.
[+] [-] eru|14 years ago|reply
[+] [-] peterwwillis|14 years ago|reply
[+] [-] tomstuart|14 years ago|reply
So don't be afraid! (And besides, there are certainly many CS degrees which don't require anywhere near the amount of mathematical sophistication mentioned in this article.)
[+] [-] drcube|14 years ago|reply
Still, I think you should look at college as a way to learn what you don't know and get better where you suck, rather than bolster your strengths and avoid your weaknesses. For example, I wrote really well in high school and at one point wanted to get an English degree. Then I thought, "I already know how to write, let's put that tuition money to better use" and started considering math and science heavy options.
[+] [-] vosper|14 years ago|reply
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.
[+] [-] peterwwillis|14 years ago|reply
Thanks everyone for the words of encouragement, but when I was going to school it would take me 4 hours to complete 15 simple homework math equations, even with the ritalin. 'Hard work' in the form of 4 years of that stuff would make me commit suicide.
Moreover, I just don't care to understand complex math. I do want to know how to design compilers and write embedded kernel drivers. If advanced math is required to be able to do these things, CS isn't for me.
[+] [-] nassosdim|14 years ago|reply
Enough about me. If you want it, go get it. Period.
[+] [-] mquander|14 years ago|reply
[+] [-] pnathan|14 years ago|reply
Certainly I consider myself relatively slow, but with enough perseverance, I get told I am smart. :)
[+] [-] georgieporgie|14 years ago|reply
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.
[+] [-] mcshaner1|14 years ago|reply
https://en.wikipedia.org/wiki/Little%27s_law
[+] [-] zerostar07|14 years ago|reply
[+] [-] jergosh|14 years ago|reply
[+] [-] kevinalexbrown|14 years ago|reply