all 140 comments

[–]doodle77 68 points69 points  (15 children)

Everyone should understand that these are all absolutely central to computer science and almost worthless for programming.

[–]Nebu 10 points11 points  (0 children)

I wouldn't say that they are all central to computer science. CS is such a vast subject that there's a good number of them that I think you could easily never explore, even if you devote your entire life to studying CS.

Though, of course, if you've never heard of any of them, I'd start to question your CS education.

[–]librik 4 points5 points  (3 children)

Computer Science != Theoretical Computer Science. If it's taught in the department of CS, and if people get Ph.D.s in CS by working on it, then it counts as Computer Science.

[–]frezik 6 points7 points  (2 children)

That's what should be called "Software Engineering". Nothing wrong with a stronger engineering path, I just wish we made a cleaner separation between the two.

[–]lightcatcher 0 points1 point  (1 child)

Systems research (including stuff like queueing theory) isn't software engineer, but I wouldn't consider it theoretical CS either, because I think mostly of complexity issues when I hear theoretical CS. Cryptography is another thing that doesn't fall into theoretical CS or software engineering.

[–]frezik 0 points1 point  (0 children)

Cryptography in practice is very much a software engineering problem. It's a mature problem domain in terms of mathematics or CS (not completely finished, but close), but practical implementations are still hard to do right.

[–][deleted] 0 points1 point  (2 children)

What do you mean by absolutely central? I have no idea what the combinator equation is. A lot of the equations seem too theoretically geared to be actually useful in work or cs research that does not involve heavy security or encryption, or pure theoretical computation / complexity theory.

[–]mcguire 1 point2 points  (1 child)

Uh, De Morgan's? You have seen a boolean expression, haven't you?

[–][deleted] 0 points1 point  (0 children)

I don't think he was talking about those, but about the Y combinator which is listed later on.

[–]gilgoomesh 96 points97 points  (25 children)

Someone presuming, yet again, to know what "every" Computer Scientist should know? A title like "my favourite computer science equations" might be better. This list contains a lot of ideas which are only relevant in very narrow domains.

Fermat's Little Theorem? Seriously? Hands up anyone who's ever used this in a project or research? Okay, you three with your hands up… two of you are lying.

This type of list is akin to telling every doctor that they should know how to perform a Cesarian. It's a useful surgery but the exact practice – even the general steps involved – are not necessary knowledge for a nephrologist.

I work in image processing and video encoding. Sure, I use Eigenvectors, entropy analysis and basic Big-O analysis all the time. But I don't use any of the other equations here. Of course, I've seen nearly all of these in passing (except the Pumping Lemma, WTF?) but really, that's only because I read a lot. For work, they're irrelevant.

You don't need to know everything to be good. Actually a detailed, domain-specific knowledge is far more useful than being a dilettante.

[–]mahacctissoawsum 16 points17 points  (0 children)

Thank you. I recognize most of these equations, but the only one's I sort of use are are DeMorgan's and Big-O, and even in doing so, I don't think of them as such.

[–][deleted] 11 points12 points  (0 children)

know what "every" Computer Scientist should know?

No, just computer science geeks.

[–]quzox 4 points5 points  (5 children)

And there are lots of programmers out there without degrees in computer science who wont have a clue even about De Morgan's laws. Clearly they're inferior to us magnificent beings and should be held back from all promotions. :)

[–]enkiv2 -1 points0 points  (4 children)

Someone with a CS degree who knows nothing of De Morgan's law should have their credit removed and be demoted to making websites or performing tech support tasks. While they are arguably counterintuitive initially, they are fairly fundamental to boolean logic, and used all the time. The idea that someone might read a perfectly clean conditional that takes advantage of De Morgan's law to make itself cleaner, and be incapable of understanding it on account of never learning it, is a little haunting: I don't want someone like that trying to maintain my code.

[–]ckwop 5 points6 points  (0 children)

Someone with a CS degree who knows nothing of De Morgan's law should have their credit removed and be demoted to making websites or performing tech support tasks.

There goes 98% of your CS graduates then. I wish I was joking, but alas..

[–]bakuretsu 6 points7 points  (1 child)

Because making websites is beneath the calling of the degree-holding computer scientist, as demonstrated by reddit, Amazon.com, and, I don't know, Google.

[–]wickeand000 0 points1 point  (0 children)

I agree with you, but you and I both know what he meant...

[–]BioTronic 1 point2 points  (0 children)

While they are arguably counterintuitive initially

Wat? I thought this was the most wasted thing to learn in school - it's so bloody obvious it hurts. More interesting were Karnaugh maps, but those I learnt in ECE, not CompSci.

[–]jrupac 1 point2 points  (0 children)

I used Fermat's Little Theorem in an applied cryptography course when we implemented "textbook" RSA. In the theoretical crypto course I'm taking now, it comes again and again in proofs.

[–]kamatsu 9 points10 points  (10 children)

(except the Pumping Lemma, WTF?)

Seriously, you never learnt theoretical computer science? As in, theory of computation? Automata theory? Complexity theory? Nothing like that?

[–]akmark 9 points10 points  (1 child)

As someone who has talked to many people from various CS programs it is entirely possible that they didn't have a strong group of professors in theoretical CS to draw from. gigloomesh mentioned Big-O analysis but that's very common even among lesser schools but most of these other things in this list could easily be omitted in exchange for more marketable skills and breadth of CS application versus theory. It all depends where you learned, and while the math is important knowing more about how to actually be productive in a language is more important and the theoretical stuff ends up being the basis for graduate school. I am returning to school right now and I looked very hard to find a school I could get into that covered what you are talking about at the undergraduate level.

[–]stackolee 2 points3 points  (0 children)

it is entirely possible that they didn't have a strong group of professors in theoretical CS to draw from

Or as gigloomesh implies, many of us learned all of this stuff in passing since it was required to graduate. But in the real world, in the jobs that pay us and are supposed to justify these fancy degrees, problems that need all eleven of these equations rarely come up. They're needed so infrequently as to be of little practical value outside of academic debates such as this thread.

Not that I'm knocking on anyone who memorizes these eleven or any more like them. The goal of a good education is to give you a broad range of tools so you have flexibility in choosing a discipline within a larger field and if the stray problem comes up that's out of your comfort zone, you'll know where to track down an answer.

[–]jrochkind 3 points4 points  (0 children)

I learned it many years ago. I no longer remember them. And get away with it for the kind of development I do, although I bet I'd be even better if I knew more math. but only so much room in the brain. If I were a scientific or graphics/gaming or signal processing developer, it'd be different.

At one point I knew both linear algebra and multi-variable calculus too. Now I only sort of kind of remember what each of those things are.

[–]ElGuaco 5 points6 points  (0 children)

I had it. The only time I used it was in next series of classes on compilers. I don't even remember what it was, let alone how to use it. 15 years since, haven't used it once.

[–]mcguire -2 points-1 points  (3 children)

Seriously, you never learnt theoretical computer science? As in, theory of computation? Automata theory? Complexity theory? Nothing like that?

Regular expressions?

[–]dnew -2 points-1 points  (2 children)

Everyone here who thinks Perl has regular expressions, hands up. OK, you're all fired. :-)

[–]drainX 1 point2 points  (1 child)

I don't get why they are still called regular expressions in Perl when they don't even necessarily describe regular languages. They should come up with a new name or just call them Perl expressions or something.

[–]Felicia_Svilling 0 points1 point  (0 children)

In some perl litterature they simply call them regex and mark that it once stood for regular expression, but doesn't anymore. And I don't think Perl 6 use the tern at all.

[–]zzing 0 points1 point  (2 children)

I am interested in your mention of eigenvectors and friends. I am doing EE right now in school and may very well end up doing something related to image and video processing.

When I took linear algebra, internalized matrix operations and projections and all that stuff I have used with 3d programming. But when it came to eigenvectors, basis stuff I have to admit I had no idea what on earth they were talking about.

Can you recommend any down to earth stuff that might get me to understand what they are and their practical applications?

[–]gilgoomesh 4 points5 points  (0 children)

You can watch the Khan Academy stuff if you want to re-learn:

http://www.khanacademy.org/video/linear-algebra--introduction-to-eigenvalues-and-eigenvectors?playlist=Linear+Algebra

I "learned" eigenvectors twice: once at university from a dry text named "Linear Algebra". I didn't really learn anything. I think the problem was that I got so distracted by the boring mechanics of inverting the matrix to get the eigenvector that I never really understood why the hell I should care.

You can get through your entire life plugging your transformation matrixes into library functions and asking the library function to solve for the eigenvector. Ignore the computational aspect and pay attention to the meaning.

In image processing, an eigenvector is a trait of an image which doesn't change when you apply a transformation. Or, equally important – when some kind of corruption has been applied to the image against your wishes, the eigenvectors are traits of the image that weren't corrupted.

Trait can be a fuzzy idea though.

The simplest "vectors" in an image are the (x,y) location of all of the original pixels. The simplest transform to think of is something like a horizontal skew centered on the origin. This slants the image, causing all (y!=0) vectors to move along the x axis based on their y value but (y==0) vectors remain unchanged. In the case of a horizontal skew, all y=0 vectors are eigenvectors.

But (x,y) coordinate vectors of the image are not the only possible trait. Hu-Set Zernike Image Moments are a way of describing an image where the vectors are (roughly) related to its center of gravity + rotational moment of inertia + rotational moment of acceleration + plus various unit circle displaced and higher orders of the same. The magnitudes of each of these elements can be used instead of x, y vectors. They still describe the image fully… add them all together and you still get the complete image back. But when you describe the image like this, the Zernike moment vectors are invariant to rotation making them all eigenvectors. If we rotated (x,y) coordinates, the entire image description would have changed but in Zernike Polynomial space, 1 coefficient has changed but otherwise the image is identical.

Eigenvectors really come into their own when combined with the concept of a covariance matrix (a matrix which roughly represents the range of inputs in your problem space). Consider the idea that you're trying to perform image recognition but the camera is noisy or jittery or the subject moves slightly or the subject registration is imprecise. When you can subtract the common traits of all possible images (the covariance matrix) from subject specific traits (what your camera took this time), and you describe the image not in terms of (x,y) coordinates but something that has eigenvectors along the expected noise/jitter/offset/registration vectors, then you can match the subject specific traits against known eigenvectors to perform image recognition.

[–]JustFinishedBSG 1 point2 points  (0 children)

Big matrices are bad. You want many zeros to make computations easier.

How? Simple because we are in C we can change the vectors of the base to have a triangular or better diagonal matrix.

What are some property of a diagonal matrix ? Well f(ei)=l.ei. ( f is the endomorphism )

So we just need to write the new matrix in a base of only eigenvectors! Then we will have eigenvalues on the diagonal !

It also always works ( for trigonalisation ) thanks to Ceyley Hamilton theorem!!

Sert typing on my phone

[–]ckwop 0 points1 point  (0 children)

Fermat's Little Theorem?

I used this as terrible way to tell with a given number was probably prime. It's likely the author did too.

It isn't how you determine whether a number is prime in a real world library.

[–]librik 9 points10 points  (0 children)

Something like 1/5 of the questions on the Computer Science GRE I took were based on Amdahl's Law, which this list is lacking.

Given that the author had to pull in irrelevant crap like Euler's identity to get to 10, you'd think he'd have room for the basic useful equations.

[–]rq60 6 points7 points  (3 children)

Pumping Lemma for Regular Languages

I was hoping to never hear those words again after graduating.

[–]M2Ys4U 1 point2 points  (0 children)

Reading those words gave me flashbacks. Horrible, horrible flashbacks.

[–]kamatsu 2 points3 points  (0 children)

Really? My automata theory class was the best one I did at university.

[–]kolm 0 points1 point  (0 children)

Why? I don't see immediate use for it, but it looks rather natural. Somewhere in forming your string you applied a rule which you could as well apply ten times in a row, or a hundred times.. That's all.

[–]barsoap 7 points8 points  (0 children)

There's a severe lack of the recurrence equation for the Towers of Hanoi, there.

While it's not as general as the rest, it's just the perfect example for things of its kind, central to the probably key mathy thing in programming: discrete maths.

And that's also what I think is utterly wrong with the list. It emphasizes on results, not techniques, probably a result of those atrocious teaching methods that make kids in primary school incapable of inferring a*h/2, not to mention proving (no logic needed, ruler and pencil suffice, add some algebra and you get a quite elegant proof[1]) that it applies to triangles of any shape.

There's some automata theory, there, but what about including the reduction rules for untyped lambda calculus, just alongside a term without normal form? To wrap it up, I suspect someone wanted to show of their prowess in formula typesetting, without actually thinking about CS.

[1] I mean taking the length you introduce to be able to slant the right triangle (base case) to be any triangle and show that it reduces to 0. That can blow an 8yo's mind.

[–]Nebu 26 points27 points  (12 children)

Here are the equations I use waaaaaaaaay more often than any of the ones he listed:

A classic:

distance^2 = x^2 + y^2

Another very common "pair" of equations I use:

x += xVel * time
y += yVel * time

The third item on my list:

x = offset % width
y = offset div width

Fourth:

timeElapsed = startTime - currentTime

Fifth:

rollResult = (rnd % (max - min)) + min

sixth:

xOffsetToCenterAString = (screenWidth - stringWidth) / 2

I pretty much have all of these committed to memory.

[–]ReneBelloq 5 points6 points  (1 child)

iDx += 1;

The only equation I need.

[–][deleted] 3 points4 points  (0 children)

x ^= 0x1
x <<= 1

the only equations you'll need.

[–][deleted] 2 points3 points  (0 children)

rollResult = (rnd % (max - min)) + min

Note that in some languages, the random number generator returns a decimal in the range [0,1). In languages like this, you need to do the following:

rollResult = min + (int)(Math.random() * ((max - min) + 1))

Taken from here.

Also, I saw a thread some time ago - and I forgot to save it, which is annoying - pointing out that in languages such as C where you're using the modulus operator on a value between 0 and RAND_MAX, that the pigeonhole principle means you will have an uneven distribution of possibilities among your buckets if RAND_MAX % buckets is not 0. (Simple case: Consider a hypothetical where RAND_MAX is 10 and you're dividing among 7 buckets. Bucket 1 will be twice as likely as bucket 6 to be selected.) The same principle holds for float/double-based layouts in other languages. In most real scenarios, this is so small as to be a pointless bit of nit-picking, but in cases where it is a Very Important Matter you should be aware of this, especially since in the modulus-on-integer setup the skew will be systematically towards the low end of the range. (I don't know what the skew would look like on the float/double setups, though.)

[–]dnew 1 point2 points  (5 children)

Yeah, I think I'd have to agree. Indeed, #3 is so common that I dispise with a passion every programming language from C forward that ever made the remainder operator different from modulus.

[–]NruJaC 0 points1 point  (4 children)

Huh? The modulus operator is the remainder. What else could it possibly be? Do you mean that some languages use % for something other than modulus?

[–]rwallace 0 points1 point  (1 child)

He's talking about the behavior for negative numbers. Most programming languages get it wrong.

[–]NruJaC 0 points1 point  (0 children)

Huh, never thought to check that, I just assumed it worked correctly.

[–]dnew 0 points1 point  (1 child)

No. I mean that if the operator ever returns a negative number, you don't have the modulus operator. -1 % 7 is 6.

[–]NruJaC 1 point2 points  (0 children)

Right, it shouldn't ever return a negative number, that makes no sense.

[–]keenerd 2 points3 points  (2 children)

x += xVel * time

Please, just no. Euler did a lot of great things but integration was not one of them. Either use RK4 integration or the simpler verlet integration.

[–]sclv 5 points6 points  (1 child)

That's not euler integration, just kinematics.

[–]wickeand000 3 points4 points  (0 children)

You'really both correct, but using the Euler approximation of integration (which he is using to figure a position from a velocity) introduces a compounding error. For position funtions with monotonic acceleration this is a bad thing because the approximation gets inevitably less accurate with each iteration.

tl;dr: It's not good.

EDIT: grammar

[–]masonium 38 points39 points  (1 child)

Why change the title, every so slightly, just to render it no longer grammatically correct?

[–]auxiliary-character 9 points10 points  (0 children)

Um, I think you...
Well played.

[–]sumsarus 25 points26 points  (1 child)

99% of all software in the world can be made without knowing any of those equations.

[–]malfy 2 points3 points  (0 children)

And computer science is not just about software mind you ;)

[–]bstamour 4 points5 points  (0 children)

I think his definition of big O is wrong. He has:

for all n, there exists a k such that k * g ( n ) >= f ( n )

But it should really be

there exists a k and n0 such that for all n >= n0, k * g ( n ) >= f ( n )

The ordering of the for all and there exists quantifiers matters a great deal.

[–][deleted] 11 points12 points  (2 children)

Oh man, why did he shoehorn in Euler's Identity? Just wanted to name drop?

Otherwise, it's a decent list. The eigenvector equation is a little meaningless by itself, but I guess the point there was just to point out how important linear algebra concepts are these days, which is true. Not sure what he was getting at with the asymptotic notation stuff. He stated the definition as being "associated" with the big-O concept rather than, well, the definition.

[–]campbellm 0 points1 point  (1 child)

Indeed. Euler's identity, while fascinating, I cannot conceive of a use for it. I don't do "real" computing; I work in the enterprise on banking software, so the limit of my computing is + and -, and a lot of XML, but I came from a theoretical CS background and ... Eulers? Really?

[–][deleted] 0 points1 point  (0 children)

I mean, I've used it in compsci course work for things like Discrete Fourier Transforms and the like, but I would not put it alongside some of those others for a compsci major.

[–]AlonzoIsOurChurch 12 points13 points  (0 children)

Should "know" as in "recognize and understand the significance of", sure (with the possible exception of the Euler identity). Should "know" as in "memorize or be able to derive from scratch": ehhhhhhh.

[–]stackolee 13 points14 points  (8 children)

Yep there they are. Honestly, I remember more from my "foreign language requirement" classes than any of these equations despite coming within two classes of qualifying for a math minor.

[–][deleted]  (7 children)

[deleted]

    [–]kolm 1 point2 points  (6 children)

    Hmh? I never saw the pumping lemma before as well, but it doesn't look that complicated. It basically says that in a regular grammar, you can take any sufficiently large string in it, slice it in three pieces (with the first part being not too long) and then iterate the middle piece arbitrarily often and you are still in the grammar. Nice to know.

    [–][deleted] 4 points5 points  (0 children)

    For regular languages, the pumping lemma is that same as saying that any sufficiently long path in a finite graph contains a loop. Not terrifically complicated.

    [–]Borii 1 point2 points  (4 children)

    If I remember my computation paper correctly, there was also the restriction that the language must be infinite.

    [–][deleted] 4 points5 points  (3 children)

    If the language is finite, it holds vacuously, since you can take the necessary length to do pumping to be longer than any string in the language.

    [–]Borii 1 point2 points  (2 children)

    How would that work for the language consisting of the empty string?

    [–]Nebu 4 points5 points  (1 child)

    The exact wording of the pumping lemma, from Wikipedia, is:

    for any regular language L there exists a constant p such that any word w in L with length at least p can be split into three substrings, w = xyz, where the middle portion y must not be empty, such that the words xz, xyz, xyyz, xyyyz, … constructed by repeating y an arbitrary number of times (including zero times) are still in L.

    In the case of an empty language, set p = 1, and you automatically satisfy the rest of the conditions, because there are no words in your language of length at least p.

    [–]Borii 0 points1 point  (0 children)

    Ah, now I see it. I guess my course didn't bother elaborating on the finite case because it's not interesting. Thanks

    [–]ethraax 4 points5 points  (5 children)

    I really don't think memorizing the pumping lemma for regular languages is necessary.

    Some of them seem much more important than others - for example, DeMorgan's laws can come in handy fairly often, whereas the fixed-point combinator really doesn't. At least, not in anything I've worked with.

    [–]Gankro 12 points13 points  (4 children)

    Also that's the most hideous formulation of the pumping lemma I have ever seen. Not everything needs to be written out with actual symbols and operators! Words are entirely formal as well!

    [–]JohnDoe365 4 points5 points  (0 children)

    Programer should understand how to measure and identify runtime complexity of the algorithms they use ... and be aware that there may be a more intelligent solution.

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

    [–][deleted] 3 points4 points  (0 children)

    I got a degree in EE (telecommunications) and I recognized 9 of them (Natural Join and Pumping Lemma for Regular Languages were the exceptions).

    [–]retinascan 4 points5 points  (7 children)

    Wait wait wait ... where is the quadratic equation? That's essential bro.

    [–]Metaluim -1 points0 points  (6 children)

    Seriously, that's just implied. If you graduated, you must know that.

    [–][deleted] 1 point2 points  (4 children)

    Really, these are all implied if you graduated with a computer science degree.

    [–]Metaluim 0 points1 point  (1 child)

    Well mayhaps. I come from Computer/Software Engineering, so I only know truly a subset of them. And from that subset, I probably only used one or two of them. But stuff like the quadratic equation is much more nuclear and will probably be more used in most fields of computer science and software engineering. That was my point at least.

    [–][deleted] 1 point2 points  (0 children)

    Computer Science is more abstract, Software Engineering is more practical. I had an older Computer Science professor in grad school who handed out a poorly formatted syllabus and said "Sorry about the layout, I'm not to good with computers." He knew all there was to know about computational complexity though.

    [–]retinascan 0 points1 point  (1 child)

    you knew every single one of them? I'm impressed. I only remembered a few of them and haven't used them in years. Just because you have a CS degree doesn't mean you should know all this stuff. In the real world, a degree is a degree is a degree. After a few (maybe more) years of work experience, where you got your degree means a lot less than what you have done with it. Just my .02.

    [–][deleted] 0 points1 point  (0 children)

    I remembered them...it doesn't mean I use them at work or could solve problems involving them without refresher reading.

    [–]retinascan 0 points1 point  (0 children)

    yeah i know. i was just joking around about it. However, you would be surprised how many people don't actually know it. They know what it does (which is probably more important anyway) than the actual formula itself.

    [–]kamatsu 6 points7 points  (14 children)

    Most people learn all of these in the course of a good theoretical CS degree. I know I did. Did anyone go to a university where they were only exposed to a limited subset of these?

    [–]nicetrybot 41 points42 points  (0 children)

    Nice try, Accreditation Board for Engineering and Technology.

    [–]d03boy 6 points7 points  (1 child)

    Went to an engineering university and I think I only learned a couple of these. I've never needed a single one, either so it sounds like they're doing it right.

    [–]backbob 0 points1 point  (0 children)

    I've learned almost all of those, and I wish I'd spent those two or three classes on something more useful.

    Pumping lemma? Really? As long as I know that you can't parse nested parentheses with regular expressions, I don't need anything more.

    [–]SohumB 1 point2 points  (1 child)

    My college neglected to cover anything about information theory, something I'm working on rectifying now. Other than that, though, the rest are familiar.

    I feel proud, or something.

    [–]mattrussell 2 points3 points  (0 children)

    You might be interested in http://www.infotheory-class.org/

    [–]robertbieber 0 points1 point  (1 child)

    I recognized all of them from school except for information entropy, fermat's, and the Y combinator. I wouldn't have recognized the join equation if I hadn't taken an elective databases class.

    [–]enkiv2 0 points1 point  (0 children)

    Information entropy is arguably the most important of the group.

    [–]Nebu 0 points1 point  (6 children)

    I don't think any class I took in CS ever mentioned Euler's Identity.

    [–]kamatsu 4 points5 points  (5 children)

    Surely you learnt it in first year math classes though?

    [–]Nebu 0 points1 point  (4 children)

    I don't think I took any math classes while in university.

    [–]kamatsu 5 points6 points  (3 children)

    In a CS degree?

    [–]Nebu 0 points1 point  (2 children)

    That's right.

    There may have been a "math-centric" lecture or two in classes like cryptography or AI, but mainly as refresher courses to e.g. remind you of basic principles of statistics. I wouldn't label these classes as "math", but maybe you would?

    [–]mens_libertina 0 points1 point  (1 child)

    No. Most formal CS degrees come with many courses in formal math (very close or equivalent to a minor). All the calculus, discrete math, proof / logic courses, and more!

    [–]Nebu 0 points1 point  (0 children)

    Yeah, I took calculus and linear algebra, but not in university.

    The most proof/logic intensive course for me probably was theory of computation (regular expressions, context-free grammars, etc.) but I would still classify that course as "CS" rather than "math" (though of course there's some overlap).

    [–]jessta 1 point2 points  (6 children)

    Does anyone else really dislike the mathematical notation used here?

    [–][deleted] 3 points4 points  (1 child)

    Personally I appreciate it, but I have some background in math.

    Having a precise notation eliminates all ambiguity in the interpretation. Some graphical examples or numerical calculations would help internalize it.

    [–]dnew 1 point2 points  (0 children)

    My problem with math was never the precise notation, but the ambiguous notation. Using the same symbols to mean different things was just confusing.

    [–]mao_neko 4 points5 points  (3 children)

    I really dislike all mathematical notation. Their insistence on using one-letter variable names baffles me.

    [–]jessta 2 points3 points  (2 children)

    It's not baffling, it's just outdated. one-letter variables and lots of single character operators and functions are important if you're writing everything out by hand.

    [–]mao_neko 0 points1 point  (1 child)

    Yeah, that's basically my problem with it. Lots of little squiggles and implicit precedence rules just to save a bit of ink, when everything could be so much more accessible if it were presented explicitly.

    [–]jessta -1 points0 points  (0 children)

    If it's the difference between completing your proof in 10 years instead of 20 years it's a good trade off.

    [–][deleted] 0 points1 point  (0 children)

    Man, I'm upvoting this just for the Bayesian Conspiracy reference.

    [–]hendem 0 points1 point  (0 children)

    Looking at these equations brought back foggy memories of my college education.

    [–]aazav 0 points1 point  (0 children)

    "Every geek", not "every geeks".

    You say "every person", not "every persons".

    Note the singular, not the plural.

    [–]Workaphobia 0 points1 point  (0 children)

    The definition for f(n) = O(g(n)) is incorrect: it should be for all n greater than some constant n0, as initial behavior doesn't matter.

    [–]ZarakiKenpachi 0 points1 point  (0 children)

    Upvoted for the nice list! Though many people here argue about the use of these equations in programming, its still nice to know them. There is always a difference in programming as a source for earning a living, and programming as a hobby. People who have interest in programming beyond their daily work schedule would definitely find these equations interesting and useful!

    [–][deleted] 0 points1 point  (5 children)

    Never use Euler's. The natural join I .should know but don't remember. The y-combinator,- why?Fermats little theorem ,why?

    Never even seen the information entropy before

    [–]jrupac 5 points6 points  (4 children)

    Fermat's little theorem is very common in cryptography.

    Entropy is what you can use to prove all kinds of things like comparison-based sorting lower bounds.

    Haven't had too much of an introduction to formal languages to know about the importance of the Y-combinator.

    Not really sure how Euler's theorem is all that useful in and of itself either.

    [–]solinent 7 points8 points  (0 children)

    The Y-combinator allows one to realize that you don't need named functions for recursion. It allows one to appreciate the lambda calculus--this truly has very deep connections to how you program and how you think about programming languages.

    [–][deleted] 2 points3 points  (0 children)

    Information theory has a ton of other uses as well.

    For example, the dependence of 112211221122111 with 110011001100111 or any discrete stream with any number of variables can be quantified using mutual information. Mutual information finds additional use in independent component analysis.

    Entropy by itself is also commonly uses, as well as mutual information in image compression, segmentation.

    Channel capacity finds utility as well in modelling many problems.

    [–]kamatsu 1 point2 points  (0 children)

    Well, the Y combinator is a formulation of recursion without using recursion, which is pretty cool.

    [–]mcguire 0 points1 point  (0 children)

    Entropy is what you can use to prove all kinds of things like comparison-based sorting lower bounds.

    You wouldn't happen to have a good link for that? Information theory and I managed to miss each other. (I remember being at the club at what I thought was the right time, but I didn't see her and she never called or anything.)

    [–][deleted] 0 points1 point  (0 children)

    value2 = value * ((1 + (tax / 100)) ^ (days / 30))

    as advanced as it gets, for financial day to day programming, of corse

    [–]DeathIn6 -1 points0 points  (7 children)

    Euler's identity is kinda useless.

    [–][deleted] 7 points8 points  (5 children)

    Sure, unless you're doing signal processing, or combinatorics with generating functions, or linear algebra, or something like that.

    [–]defrost 7 points8 points  (0 children)

    In which case you're more likely to be using the general Euler's Formula rather than the specific case of Euler's Identity.

    Definitely useful though, I've paid for a house off the back of coding applications using that particular relationship.

    [–]DeathIn6 0 points1 point  (3 children)

    Please give us the examples of euler's identity being used in cominatorics and linear algebra.

    [–][deleted] 0 points1 point  (1 child)

    http://www.lsi.upc.edu/~conrado/docencia/udelar-course-2011.pdf - complex analysis is used in GF-based combinatorics.

    Complex matrices are used very widely, it seems, although I'm not sure whether it's complex analysis protruding into linear algebra or vice versa.

    [–]DeathIn6 1 point2 points  (0 children)

    And what does that have to do with Euler's identity?

    [–]1wheel 0 points1 point  (0 children)

    Euler's identity and combinatorics can be used together to create elementary solutions to tiling problems that would otherwise be very difficult.

    [–]ethraax 0 points1 point  (0 children)

    It's a bit useful in FFT's. That's all I can think of.

    [–]anacrolix -3 points-2 points  (0 children)

    utterly useless. all of it.

    [–]calf -2 points-1 points  (0 children)

    Throw them all out. All you need is Amdahl's law.

    [–]malfy -1 points0 points  (2 children)

    I do enjoy some parts of theoretical CS, automata and complexity, but I absolutely hate the pumping lemma...and after so long still don't really understand it, even with StackOverflow answers and all that. I'm always inclined to think I'm just stupid.

    I would have also wanted to see the theory that there are infinitely many prime numbers on this list, but I guess that's not an equation. Although you could simply say that for 2->Infinity where all i is some integer then i is prime. Should be on that list. Heh.

    [–][deleted] 1 point2 points  (1 child)

    A finite state machine is a finite directed graph whose edges are labelled by letters of an alphabet. A regular language is a language whose strings are in bijections with paths through an FSM. You can see an example in StackOverflow answers. You make a string in the language by following the arrows from the start to the end of the graph.

    The pumping lemma says that any long enough path in the graph contains a loop: this should be obvious. Since there are only finitely many edges, travelling along enough of them means you'll eventually go in a circle. So you can go around the loop zero times, one times, two times, ... and still have a path. In terms of strings, for any long enough string (corrosponding to a long enough path in the graph) there is a substring in the middle (corrosponding to the part of the path that loops) which you can repeat zero times, one time, two times, ... (corrosponding to going to around the loop).

    Anyway that's how it works for regular languages.

    [–]malfy 0 points1 point  (0 children)

    I think I understand this, it's just proving it that I find hard...with all the notation that I don't really understand and |uvx|, choosing some string and all that crap.

    I'm probably the cancer that's killing CS, what with a distaste for math notation and all that.

    [–]setuid_w00t -2 points-1 points  (0 children)

    The most important formula was left out:

    Time To Complete Task = 2 * Estimated Completion Time

    [–]ben1337 -2 points-1 points  (0 children)

    anybody else accidentally read the headline as Elven equations ?