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

http://www.elegantcoding.com/2011/11/eleven-equations-true-computer-science.html

by gmoes • 15 years ago

288 96 15 years ago

pork• 15 years 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• 15 years 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• 15 years 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• 15 years 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• 15 years 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• 15 years 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• 15 years 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.

robinhouston2• 15 years 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_langu...

algorias• 15 years 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.

robinhouston2• 15 years 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• 15 years ago

I should think the Master Theorem would be included:

http://en.wikipedia.org/wiki/Master_theorem

or better,

http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method.

methodin3• 15 years 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• 15 years 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• 15 years 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• 15 years ago

I've found 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.

randysavage25• 15 years ago

You better toughen up and immerse yourself in math

methodin3• 15 years ago

I actually surround myself in math all the time since I do a lot of game development. A poster above pointed to the math symbol list on wikipedia and I think "Great. I need to scour a daunting page to find the meaning of an obscure symbol?" It's pretty similar to reading a post in another language and I'm not sure it's worth my time considering by the time I figure that out I would have spent an hour decyphering the equations. Google translate for math, perhaps? I'd use it.

nassosdim2• 15 years ago

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).

bitwize• 15 years ago

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.

methodin3• 15 years ago

Seems like a lot of effort for an unknown gain - to me. It's about the same as reading a code block in Scala. It may or may not be useful to me but to figure that out I have to go off into a completely different world. I just wish the mathematical symbols weren't hiding so much meaning. Can I really guess what a backwards-E-equals-looking symbol is? Nope. I get it wrong every time.

henning• 15 years 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_l...

Splines• 15 years ago

Huh, that's interesting. I never considered the similarities between parallel processing and people management until today.

jerf• 15 years ago

http://en.wikipedia.org/wiki/Queueing_theory

joezydeco• 15 years 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.

StavrosK2• 15 years 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• 15 years ago

Writing skills are always relevant. The lack of them in this article made me stop reading before getting to any actual content.

StavrosK2• 15 years 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• 15 years 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.

snippyhollow• 15 years 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)

peterwwillis2• 15 years ago

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

vosper• 15 years 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.

nassosdim2• 15 years 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• 15 years 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.

pnathan• 15 years 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. :)

drcube• 15 years ago

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.

tomstuart2• 15 years ago

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.)

mquander• 15 years ago

Actually, the purpose of going to school and studying for four years is to learn things which you aren't already good at.

peterwwillis2• 15 years ago

(Damn it, I wish I could edit old posts...)

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.

alexholehouse• 15 years ago

The not caring is kind of crucial, beyond anything else. If you don't care, it's not interesting to you, and if it's not interesting to you it's probably not worth dedicating your time to. Life is short - do what you love.

THAT SAID I totally agree with what people have said, and the amount of "maths" you need beyond basic arithmetic in CS depends very much on your chosen field of interest, which, given that you don't care about complex maths, probably won't be too mathematically heavy.

kevinalexbrown2• 15 years 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• 15 years 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.

kevinalexbrown2• 15 years 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)

king_magic4• 15 years 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• 15 years 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_magic4• 15 years 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.

kleiba2• 15 years ago

Fair enough, but note that the list doesn't say "true software engineers should know" but "true computer science geeks should know".

king_magic4• 15 years ago

My response to this is that I am a "true computer science geek". Why isn't P=NP (or P!=NP) on that list? Why not more about set theory? Why not proof by induction? How about lambda calculus?

There is far more to CS than what that list implies. I realize that it's not supposed to be all-encompassing, but seriously, saying it's "something all CS geeks should know", in my mind is unfair - I have little understanding of most of the OP's article, but still consider myself to have a very solid understanding of CS, based on my level of education.

I don't need to know most of the things in the article. There are plenty of other things in CS, however, that I do need to know.

I think putting together lists like this does a disservice to people just about to enter the field. You can't possible break down CS into a list of 11 equations.

abscondment• 15 years ago

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.

docgnome• 15 years ago

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.

cheez• 15 years ago

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

tomstuart2• 15 years 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• 15 years 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.

orenmazor• 15 years ago

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

krupan• 15 years 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

anrope• 15 years 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.

eru4• 15 years 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.

eru4• 15 years 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• 15 years 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• 15 years ago

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

raffi• 15 years ago

Nope.

mcshaner1• 15 years 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

hexagonc• 15 years 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.

eru4• 15 years ago

Please be careful how you use big-O notation here.

Natsu• 15 years 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• 15 years ago

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

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

Related Stories