How much and what type of math is beneficial to programming?
January 29, 2015 12:04 AM   Subscribe

How much and what type of math is beneficial to programming? What are the prerequisites / pathways to grokking this kind of math?

Firstly, I know that you can be a perfectly productive, efficient and employable programmer with only rudimentary knowledge of math. I have a rudimentary knowledge of math. I finished studying math at the GCSE level in the UK, so I'm missing what ever would be taught at 'A' level math, or presumably VCE math in Australia (unsure of US equivalents).

But, I was interested in following the MIT opencourseware course for Introductions to Algorithms and int he first few minutes the prof states that the prior course, Math for Computer Science was a prerequisite. So I quit that video, and found video 1 for Math for CS...I could follow most of that, but felt I'd have an easier time if I took one more step back. The trouble is, I don't know what step that should be. I took a look at the Khan Academy tracks for math and the options were not helpful. Do I want to look at algebra, calculus, probability, or something else?

So please help me map out a sensible pathway for learning the math that will help with my main interest in programming and better understanding algorithms. We'll assume I can do arithmetic and basic algebra, and I can remember Pythagoras' theorem, and how to figure out the area of a circle, but not what sin, cos, tan mean or what they are used for.

If you mention an area in math worth pursuing, please suggest what area of programming it is beneficial for.
posted by man down under to Education (15 answers total) 23 users marked this as a favorite
Best answer: So in first year university, I failed math but got a near-perfect grade in programming. So the short answer (as you know) is, not a lot... however!

What I've found most valuable as a programmer (and, more distantly, as a student learning programming) have been:

- algebra (how to use variables is essentially algebra)
- basic matrices and linear algebra (this is a good foundation for arrays)
- basic statistics and probability is very useful for determining results of algorithms

More niche:
- vectors and vector arithmetic (the follow-on from matrices, from memory) are useful if you want to do 3D programming
- advanced stats/probability (although I would only pick this up if you needed to, if you keep going in programming)
- mod arithmetic is the core of cryptography and generally useful, but not essential for a beginner

Not useful unless you are given an assignment specifically for it (IMHO, YMMV):
- trigonometry (there are generally functions available if you really need to calculate sin(x) etc)
- calculus
posted by Xany at 12:39 AM on January 29, 2015 [3 favorites]

Xany has it pretty well covered. I'd add that Boolean algebra is essential, and basic trigonometry is often used in 2D graphics.

Calculus is the great nutcracker of mathematics, and it's well worth learning, but as far as I can tell it's of surprisingly little use in computer science outside of domain-specific problems. Digital signal processing is the most common application I can think of.
posted by neckro23 at 1:03 AM on January 29, 2015 [1 favorite]

What kinds of programming problems do you enjoy solving? Linear algebra and topology are useful for graphics programming. Differential geometry can be useful for map generation. Linear algebra and basic set theory are useful for algorithm design and bioinformatics (statistics) programming. Set and number theory are useful for cryptography.
posted by a lungful of dragon at 1:09 AM on January 29, 2015

Best answer: I would bump statistics and combunatorics up on that list. It's good for thinking about algorithmic performance but it's also super useful for any kind of analysis of all kinds of stuff that happens. Performance analysis is one example (the data is always noisy). Another is: the thing crashed one time in a hundred. How many times do I need to run it before I'm confident I fixed that?
posted by aubilenon at 1:12 AM on January 29, 2015 [3 favorites]

Best answer: If you mention an area in math worth pursuing, please suggest what area of programming it is beneficial for.

Logic - AND / NOT / OR etc is used all the time in all areas of programming. Some extremely rudimentary knowledge of algebra is helpful but not really essential.

You pretty much don't need Maths at all beyond this in a normal programming situation. There's some exceptions though.

Graphics - is extremely maths heavy - though an engine / libraries will hide most of the hard work from you. Vectors / Matrices / Quaternions / Mechanics all come into play here and it's mostly degree-level or beyond type stuff.

Some database stuff can be easier if you understand set theory.
posted by BigCalm at 3:42 AM on January 29, 2015 [1 favorite]

Best answer: I often teach the introductory math course for computer science majors here at Wisconsin, so I can tell you exactly what the CS department here thinks its students should know. It's pretty much in concordance with the answers here.

Logic (boolean operators, basic rules of inference, quantifiers)
Asymptotic notation (what the Landau notation "big-O" means, which functions grow more quickly than which other functions)
Basic number theory (probably less critical for most programmers, but explaining how RSA works is super-fun and demonstrates to novice programmers some basic ideas in crypto)
Mathematical induction
Basic graph theory (graphs, trees, counting trees, etc.)
Basic probability (notion of probability distribution and expected value and not much more -- e.g. no central limit theorem)
posted by escabeche at 4:26 AM on January 29, 2015 [8 favorites]

It depends on what kind of programming. When I worked in operating systems, I needed to understand queuing theory which means I needed to understand calculus and differential equations and various kinds of algebra and probability theory. I also needed to understand analysis of algorithms which meant combinatorics and graph theory. Obviously I needed to know how to deal is hexadecimal and octal and how to do XOR and such.

If you're doing graphics, you might need to know vectors and trigonometry (the latter is useful also in plotting the positions of things on maps or in the real world--a friend who writes iPhone apps uses a lot of trig for that reason).

If you're doing encryption, you need to know number theory and group theory. Also related is stuff involved in error correction and detection which uses group theory and information theory.

If you're doing accounts receivables, you just need arithmetic (but keep in mind that there's a lot of mathematics involved in understanding errors involved in rounding--how floating point calculations can lose a lot of digits which turns into a lot of money, or if you're programming for scientists, a lot of data precision).

If you're programming for Wall Street, they want you to understand probability and statistics which, in turn requires calculus.

A lot of the time you can get away with using programming libraries that other who understood the mathematics already wrote for you.
posted by Obscure Reference at 4:35 AM on January 29, 2015

The topics section from the wikipedia article on discrete mathematics gives a pretty excellent overview of what math is actually used and how.

Of those listed I personally would say that logic and set theory are probably the most introductory topics. Computability is also a really basic (basic as in basic computer fundamentals, not basic as in it's easy to understand) and really fascinating topic that builds off of both logic and set theory and will likely really help with an algorithms course.

I would also agree with the above posters that looking into asymptotic notation/complexity analysis is probably vital to your understanding of an algorithms course as well. I don't even know where that fits in with math, but it's something most CS students learn in their first year or so, and it just becomes assumed knowledge after that.

After you have all those you will probably have enough of an understanding to know where to look when you start having issues with the algorithms course, which is probably exactly where many students in the MIT course would also be when taking it (if it's anywhere like where I did undergrad).

From there pick a topic you're interested in and match the math to it. Machine learning? Statistics! Networking? Graph theory! Doing all the math is probably overkill after the basics unless you're really into math.
posted by Krop Tor at 4:44 AM on January 29, 2015

Really depends on what you're doing. I very rarely use anything beyond basic arithmetic, but that said, I found more abstract topics like abstract algebra, topology, number theory and category theory useful for understanding how to think about problems. Not necessarily studying them, but reading about them.
posted by empath at 5:46 AM on January 29, 2015

Best answer: escabeche's answer should mirror the Math for Computer Science course pretty closely. Most people are telling you things not relevant to your basic computer science courses. When I took the equivalent course (ours was called Discrete Math, which is a pretty common name), I think the prerequisite was "sufficient mathematical maturity" which means "nothing specific, but the class isn't dead easy". These courses probably tacitly assume the ability to multiply matrices, so I'd maybe use learning about matrices as a way to get back into the math groove. Discrete math tends to be really different to what you saw in school (you probably did some of the basic probability stuff and have forgotten*) and my guess is that you need to plod through the Math for Compute Science course slowly but surely. If you want more prep, the first three sections from the Khan Academy probability and combinatorics will get you in the right mindset. (It's really part of that standard undergrad discrete math material, but doing more won't hurt you.)

(Technically the asymptotic stuff requires limits, but I think people tend to handwave the limits in undergrad CS classes.)

*In the US, permutations and combinations are always taught with problems like "how many ways can you arrange the letters in MISSISSIPPI" and "how many license plates are there that fit requirements X, Y, Z", the latter especially being irrelevant in Britain, but maybe that triggers some vague memory. Very basic probability is coin flips.
posted by hoyland at 5:55 AM on January 29, 2015 [1 favorite]

The reason I said big-O and not little-o is that you can define big-O precisely without limits, but little-o is trickier unless you are willing to handwave about limits or something equivalent to limits. Trust me, I learned this the hard way.
posted by escabeche at 8:02 AM on January 29, 2015 [1 favorite]

Discrete math is the big one. It's less a branch of math than a pedagogically-convenient grouping of a bunch of different branches that deal with structures that aren't continuous, unlike e.g. calculus which depends on the continuous nature of the real numbers. It seems to me that most discrete math classes open with a discussion of proof technique, which is IMO the most important part -- a lot of the things you cover in discrete math, like graph theory, start from simple premises (a graph is just a bunch of nodes with connections between some of them) but build to complex implications which require a solid and rigorous reasoning ability to work through.

Some other subdomains of programming that make use of certain branches of math:

Machine learning -- basic linear algebra, but especially statistics
Audio programming -- depending on how low-level you get, basically everything relating to DSP, which is a lot: trigonometry, some calculus, information theory, numeric methods (basically, the study of approximating mathematical operations that can't be computed precisely because they require infinite precision), ...
Programming language design -- type theory, category theory, automata theory
posted by invitapriore at 12:39 PM on January 29, 2015 [1 favorite]

My CS undergrad math was two quarters of calculus plus one quarter of discrete math (competency in algebra and basic trigonometry was assumed).

I have used what I learned in discrete math throughout my career. I have yet to use anything I learned in calculus. The only other math-related skill that has come in handy is statistics which I would recommend if available to you. I've done mostly embedded systems programming so perhaps my experience isn't universal (i.e. YMMV).
posted by tommasz at 12:52 PM on January 29, 2015

There is something to know about business math. Stuff like how interest is calculated and when a percentage, e.g. a commission, is rounded to the nearest cent.

I was once told to write a program for mortgage that would find the combination of options that would allow largest loan amount. Among other thongs, it required an understanding of local and endpoint optimums.
posted by SemiSalt at 1:05 PM on January 29, 2015

Response by poster: These are all great answers and exactly what I was looking for!

Escabeche - It was Big-O notation that got me thinking about all of this in the first place. Simply trying to speed up one function I wrote opened up a whole world of algorithm analysis that was much more interesting than the function itself :)

Thanks all - I'm going to retreat into a math cave now.
posted by man down under at 1:12 PM on January 29, 2015

« Older Likable to all except single men?   |   Is voluntary quadruple amputation possible? Newer »
This thread is closed to new comments.