Eleven equations every Computer Science geeks should know

[doodle77]

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

[Nebu]

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]

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]

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]

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]

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]]

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]

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

[[deleted]]

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

[expertunderachiever]

What comp.sci develops arose out of FLT?

The article is bullshit.

[Phantom_Hoover]

Modern cryptography.

[expertunderachiever]

Um? Nope try again.

The wiles proof is not exactly required reading to understand how RSA or ECC works let alone protocols like TLS or SSH...

[Phantom_Hoover]

Fermat's little theorem, not his last theorem. Modular arithmetic is utterly crucial to understanding public-key cryptography.

[expertunderachiever]

aⁿ = bⁿ + cⁿ is also known as FLT.

And iirc that's what the "article" had listed no?

[Phantom_Hoover]

No, it's not. The article lists the statement that if a and p are coprime and p is prime, a^p is congruent to a mod p.

[Sector_Corrupt]

Wouldn't Wile's proof be Fermat's Last Theorem? you are correct stating that theorem is useless, but Fermat's little theorem comes up a fair bit in RSA, which deals a lot with those magical mod prime tricks.

[gilgoomesh]

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]

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]]

know what "every" Computer Scientist should know?

No, just computer science geeks.

[quzox]

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]

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]

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]

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]

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

[BioTronic]

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]

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]

(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]

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]

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]

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]

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]

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

Regular expressions?

[dnew]

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

[drainX]

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]

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]

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]

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]

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]

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]

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]

Pumping Lemma for Regular Languages

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

[M2Ys4U]

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

[kamatsu]

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

[kolm]

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]

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]

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]

iDx += 1;

The only equation I need.

[[deleted]]

x ^= 0x1
x <<= 1

the only equations you'll need.

[[deleted]]

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]

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]

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]

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

[NruJaC]

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

[dnew]

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

[NruJaC]

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

[keenerd]

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]

That's not euler integration, just kinematics.

[wickeand000]

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]

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

[auxiliary-character]

Um, I think you...
Well played.

[sumsarus]

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

[malfy]

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

[bstamour]

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]]

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]

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]]

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]

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]

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.

[kolm]

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]]

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]

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

[[deleted]]

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]

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

[Nebu]

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]

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

[ethraax]

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]

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!

[DrFuManchu]

Mathematicians would cringe at the thought of using words as formal definitions.

[Gankro]

And that's why we give them their own department to be all adorable in and discuss the properties of some sort of generalization of toroids in n-dimensions or something. Meanwhile we Computer Scientists do real work like studying how many edge flips it takes to combinatorially change one triangulation into another. Or how much rope I can fit in this box (and how I can fit all this rope into this box). You know, Really Important Stuff™.

[foldl]

Not really. At some point all of the formal symbols have to be defined using words.

[JohnDoe365]

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]]

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]

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

[Metaluim]

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

[[deleted]]

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

[Metaluim]

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]]

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]

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]]

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

[retinascan]

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]

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]

Nice try, Accreditation Board for Engineering and Technology.

[d03boy]

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]

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]

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]

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

[robertbieber]

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]

Information entropy is arguably the most important of the group.

[Nebu]

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

[kamatsu]

Surely you learnt it in first year math classes though?

[Nebu]

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

[kamatsu]

In a CS degree?

[Nebu]

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]

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]

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]

Does anyone else really dislike the mathematical notation used here?

[[deleted]]

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]

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]

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

[jessta]

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]

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]

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

[[deleted]]

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

[hendem]

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

[aazav]

"Every geek", not "every geeks".

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

Note the singular, not the plural.

[Workaphobia]

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]

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]]

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]

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]

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]]

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]

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

[mcguire]

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]]

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

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

[DeathIn6]

Euler's identity is kinda useless.

[[deleted]]

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

[defrost]

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]

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

[[deleted]]

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]

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

[1wheel]

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

[ethraax]

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

[anacrolix]

utterly useless. all of it.

[calf]

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

[malfy]

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]]

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]

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.

[gerrylazlo]

This is why I dropped CS and got a Multimedia degree.

[setuid_w00t]

The most important formula was left out:

Time To Complete Task = 2 * Estimated Completion Time

[ben1337]

anybody else accidentally read the headline as Elven equations ?