what are the basic math skills for computer programming
July 2, 2006 12:09 PM   Subscribe

What are the most helpful basic math skills for the self taught recreational programmer?

I'm considering offering a 4 week math class for programmers at my art gallery (we teach various fun things there - programming, electronics, sewing, etc). Our audience is mostly artists using technology, or technologists doing something art-like (think make magazine). It was suggested to me that we have a math class for people who may have picked up some programming skills in life and forgot to learn any math. I'm a recreational programmer + math ignoramous myself so this idea is exciting, and I've found some eager math people willing to teach. Can anyone advise me on what might be good for us to focus on, or what kind of (basic) math you use more often as a programmer that everyone should know?
posted by puppy kuddles to Computers & Internet (32 answers total) 9 users marked this as a favorite
 
Discrete Mathematics is the most broadly applicable across all branches and levels of programming. It lays the fundamentals for all computer science concepts. Unfortunately it's also pretty dry and esoteric, and can't be covered adequately in 4 weeks unless you take an intensive approach.

You might want to focus on Mathematical Logic which is a manageable topic and can be somewhat interesting and intelligible. The material is even taught in the curricula of many freshman philosophy courses, indicating its widespread relevance.
posted by randomstriker at 12:22 PM on July 2, 2006


Proof by induction.
There is so little mathy-math that most programmers need to use, but having a good understanding of how to prove that something works from a base case and a step case is vital for reasoning about complex looping, which is the biggest problem a casual programmer is likely to face.
posted by ch1x0r at 12:24 PM on July 2, 2006


(note that mathematical and philosophical logic are different topics but with relevance to each other and with some overlap)
posted by randomstriker at 12:26 PM on July 2, 2006


I'd taken a few programming courses, i remember using a lot of discrete mathematics (especially algorithmics), some linear algebra, and calculus not so much (which I thought was a little over emphasised relative to how much it came up).
posted by bobo123 at 12:39 PM on July 2, 2006


Discrete math is very useful, but you really need a longer course for it.

I'd really go for teaching Big-Oh notation and complexity theory though. If they can understand that, that'll help them a huge amount with any algorithms/etc they use/write.

The things I see over and over and over again that I wish I knew math-wise are, in the following order of occurance (some overlap):
- A strong understanding of linear algebra - especially for anything in 3D, this is insanely necessary.
- A better understanding of digital signal processing, including FFTs
- More about bit operations, especially how they can [more] efficiently be used to do mathematical operations. There are shitloads of techniques, and it really expands your horizons past the regular bitflags/etc.
posted by devilsbrigade at 12:43 PM on July 2, 2006


Yeah, definitely Discrete Mathematics including boolean logic and proof-by-induction, as suggested.

It's not traditionally taught as 'math', but algorithms (sort being the classic here) and algorithm analysis (Big-O notation) is also a very important and generally useful formal concept.

Most of the 'actual' math you use in programming depends on your application. For instance, if you do a lot of sound or signal processing, you need to know all about Fourier Transforms. Problem solving often requires numerical techniques. Various kinds of physical modeling require calculus and differential equations. If you do a lot of graphics, you'll need to know some linear algebra (operations using vectors, including especially dot and cross products, and 4x4 matrices, including especially multiplication and inverses.) Stochastic techniques (like Monte Carlo,) which involve some calculus reasoning, are useful for ray tracing and statistical analysis.

People also like fractals; writing a Mandelbrot set generator is a fairly easy, satisfying little project (but is really kind of a dead-end in terms of practicality.)
posted by blenderfish at 12:44 PM on July 2, 2006


Interesting story - when I was learning calculus, it was after I'd been programming for a long time, and I found the concepts I'd learned from that (especially dealing with iteration) helped me with the basic ideas of calculus a huge amount. That said, the reverse has never been true - I've had to compute an indefinite integral exactly once for programming, and Maxima whipped that out pretty fast.
posted by devilsbrigade at 12:45 PM on July 2, 2006


Actually, the two you list are related. A good understanding of linear algebra (The DFT transform is really just multiplying by an orthonormal matrix, and then by its conjugate transpose to get back.) will help tremendously in grasping DFTs (and thus, FFTs.)
posted by blenderfish at 1:04 PM on July 2, 2006


Definitely. A lot of it is interconnected, although there's a lot more to DSP than DFTs, & there's a lot more to linear algebra than the matrices you use for DFTs.

Great suggestion with stochastic techniques though. At least understanding how stuff like Monte Carlo works is really useful.
posted by devilsbrigade at 1:10 PM on July 2, 2006


Teach some physics while you're at it. How to make things move realistically with distance, velocity and acceleration. Also, how to calculate angles with sin and cosine.
posted by hooray at 1:29 PM on July 2, 2006


I hate to go against the grain here, as I have the utmost respect for mathematicians who become programmers (don't know why that is... perhaps because they can appreciate the beauty of an efficient algorithm). That said, I don't think most "high" mathematics is going to be very useful, as you can almost always find someone who's done the legwork for the complex programatic math algorithms. For example, if you were to code a game in 3D, you can already find excellent procedures for transformation matrices.

It certainly won't hurt to have a better understanding of the underlying principles, but I don't think 4 weeks is nearly enough time to actually do anything that hasn't already been coded, optimized, and GPL'd for public consumption.

If I were teaching a math-for-programmers course, I'd concentrate on binary logic and iterations. I can't think of a single program of any practical use that doesn't use an FOR/WHILE loop or AND/OR logic.
posted by Civil_Disobedient at 1:49 PM on July 2, 2006


I'd forgo the discreet mathematics and teach something more like binary number systems, octal systems, hexadecimal systems, then go onto logic and truth tables (.e.g. conjuction (p ^ q, disjunction p v q, negation ~p, etc...), some boolean algebra, logic gates, and if people are still eager from there, go on vectors, matrices, subscripted variables, etc.
posted by furtive at 1:49 PM on July 2, 2006


What I wrote is in line with what Civil_Disobedient just said.
posted by furtive at 1:50 PM on July 2, 2006


Beyond a basic understanding of computational complexity, I can't really see discrete mathematics being very helpful to these people, to be honest. The basic mechanics that hooray suggests (along with the necessary trigonometry) will be vastly more useful. If you can get them through the necessary to understand 3D co-ordinate systems and viewing transforms that would be wonderful. Some of the other suggestions here (like FFTs) would be good to discuss in a "here are some of the things math can do for you" sense but there's no way someone with a normal math background is going to understand Fourier theory in four weeks.
posted by teleskiving at 2:08 PM on July 2, 2006


If I were teaching a math-for-programmers course, I'd concentrate on binary logic and iterations. I can't think of a single program of any practical use that doesn't use an FOR/WHILE loop or AND/OR logic.

I totally agree that teaching higher math to recreational programmers in a 4 week course is folly, but I don't quite see how iterations are "math". You might as well just call the class a programming class at that point.
posted by ch1x0r at 2:16 PM on July 2, 2006


if you were to code a game in 3D, you can already find excellent procedures for transformation matrices.

Yes, but for one, you won't understand it (and therefore won't remember it or be able to properly apply or optimize it,) and two, when you need to derive new math to solve some new problem, you'll hit a brick wall. I never put something in a codebase that I don't understand, and if I knew that someone I worked with did, that would raise some serious doubts.

It certainly won't hurt to have a better understanding of the underlying principles, but I don't think 4 weeks is nearly enough time to actually do anything that hasn't already been coded, optimized, and GPL'd for public consumption.

I think you're right about 4 weeks being an awfully short time, so the scope of what you could teach would be limited, but schooling is all about doing things people have done before, at least until you hit the postgraduate level.

One major question, given 4 weeks, is whether you want to go deep on a narrow topic, or give a broad overview of topics.

In terms of what many people mean by 'discrete math', here is a random Uni discrete math class.
posted by blenderfish at 2:21 PM on July 2, 2006


As someone who has occasionally had to teach science to people who (for a variety of differing reasons) fall into the category of "math ignoramuses", I can tell you that the overwhelming majority of problems result from a lack of fundamentals.

Make sure that these students know basic stuff, like algebra, geometry, and trigonometry. They're useful in their own right, and absolutely essential in case one wants to eventually pursue more advanced math. From my experience, your students will probably remember little to nothing of these subjects. The upside is that they are naturally related to the subject at hand. Algebra and programming both involve "correct" manipulation of variables and equations, and geometry and trigonometry are both intimately tied to graphics and motion. If your students are considerably more advanced than most "I don't know math" types, and already know this stuff, then I'd vote in favor of linear algebra.
posted by Humanzee at 2:25 PM on July 2, 2006


I'd vote for discrete mathematics... it will be more accessible to an audience with a limited mathematics background than linear algebra (lin alg isn't too hard, but they'll hate the arithmetic), and its probably more immediately interesting than a geometry/calculus review. The first third or so of Godel, Escher Bach provides a killer introduction to formal logic... read through it for ideas about how to make the material engaging (you might even want to use it directly in the course). The mathematics of cryptography is also fun... you could teach them how to implement the RSA algorithm in a week.
posted by gsteff at 2:56 PM on July 2, 2006


but I don't quite see how iterations are "math". You might as well just call the class a programming class at that point

Yeah, you're right. Though, iterations in programming have a lot in common with algebra or even calculus (at least, in the abstract). You have a function that does something to a variable; in order to understand what the result is, you have to follow the variable through the method, and watch how it changes from start to finish (which can be tricky when the function is recursive).

Yes, but for one, you won't understand it (and therefore won't remember it or be able to properly apply or optimize it,)

Agree with the first point, but the time constraint is going to limit any fundamental "understanding" that will give you the confidence to optimize a routine. Plus, just about any mathematical routine common enough to rear its head in your normal programming day has already been optimized. No point re-inventing the wheel. I can see how it would be useful to know various testing methodologies, if you were presented with a couple of ways to solve a problem and you wanted to know which was fastest, for example. But then again it becomes a "programming" problem and not a "math" problem.
posted by Civil_Disobedient at 2:57 PM on July 2, 2006


Factor high order polynomials for a while, and try to develop a general program that can do this for any polynomial. Seems like programming, but it turns into algebra; then, seems like algebra, but turns into programming. Back and forth, back and forth.

In perhaps 4 weeks, you develop lots of respect for both number theorists and programmers.
posted by paulsc at 3:35 PM on July 2, 2006


Basic Algebra is essential. As is basic logic, although if people don't "get it" intuitively, I'm not sure how much a class will help. Geometry could be useful, considering you're at an art gallery. Big O notation is very useful even if it's not technically math.

Linear algebra's probably too hard for non-math people and completely unnecessary for most recreational programmers.
posted by callmejay at 3:54 PM on July 2, 2006


Big O notation is very useful

Big O notation is interesting but useless for most recreational programmers. Machines are too goddamn fast.
posted by gsteff at 4:38 PM on July 2, 2006


gsteff: Machines have gotten a few thousand times faster in the time I've been programming them, and understanding computational complexity (big-O and friends) will help you see why that isn't really such a big change.

Humanzee's got a good point that fundamentals are important. Calculus (of the Newtonian integrals-and-differentials sort) isn't as big a deal as algebra, linear algebra, and some discrete math. In four weeks you won't be able to teach very much, but perhaps you'll be able to get enough information across that when one of your students later encounters a problem, they have a chance of figuring out what field of mathematics will help them with it. Then they can go find a book or a mathematically-inclined friend.

Along with the things others have mentioned, I'd suggest introducing people to some areas that lead to useful programming abstractions: lambda calculus, for example; higher-order functions and the like. They're vital things to have in your mental toolkit even if you're programming in straight C or assembler or something.
posted by hattifattener at 6:36 PM on July 2, 2006


I went ahead and got the full BS in CS, and part of the degree program was that we had to minor in math. Guess how much of that math I've used since graduation? Almost none.

Ok, so Venn diagrams and basic set theory may help you with databases and such, but that's pretty basic stuff that you could probably learn from a decent website on the subject.

People talk about big-o and little-o as being important. Meh. If you have common sense, you can get by without this. Ok, so you have one loop that runs five times. Great. Ok, so you have another loop nested inside the first loop that also runs five times. It doesn't take a genius to see that any code inside the inner loop will run 25 times. Thus, your program will run 5 times slower if you have this nested loop. Moral of the story - don't use nested loops unless you have to. It's not rocket science.

Sorting algorithms? Whatever. If you google "sorting algorithms", you'll hear a loud chorus of "Use quicksort because it's fast." Or, alternately, you can get a minor in math, and learn all about big-O and nLogn and a whole bunch of other crap, and in the end, you'll still get the same answer - "Use quicksort because it's fast."

In fact, that same reasoning pretty much applies to anything even remotely math-intensive that you'll do as a programmer. Either there's a library out there that exists to do whatever you need doing, or there's a well-known answer that you can find out in 5 minutes worth of googling.

Oh yeah, and Calc? HAHAHAHAHAHAHAHAHAHAH. Yeah, the other day, I was spec'ing out a new app for our site, and my boss came up to me and said, "Umm, Afroblanco, I'm gonna need you to do me a favor. Could you please integrate Sec3 theta from -1 to infinity? Thanks. I'll be needing that by the end of the day." Please, don't waste your time with calc unless you *really* enjoy math.

Disclaimer - my advice only holds true for 95% of the computing work out there. There is a small number of jobs that actually use all of this math. However, if you wanted one of these jobs, it would be because you truly had a passion for math, in which case, you probably would never have asked this question.
posted by Afroblanco at 8:12 PM on July 2, 2006


Thus, your program will run 5 times slower if you have this nested loop. Moral of the story - don't use nested loops unless you have to. It's not rocket science.

Actually (excuse me if I'm a little rusty) if one loop is O(n) and the other one is five times slower that will also be O(n), Big O ignores constants and multiplication. I think my teacher spent less than half an hour covering it but it's one of those things you remember.
posted by bobo123 at 8:56 PM on July 2, 2006


bobo - re-read my comment. I'm talking about nested loops.

Here, DoSomething() is executed 25 times:

for (int i=0; i<5 ; i++) br> {
for (int j=0; j<5 ; j++) br> {
DoSomething();
}
}

Here, DoSomething() is executed 5 times:

for (int i=0; i<5 ; i++)br> {
DoSomething();
}

Thus, the nested implementation is 5 times slower then the non-nested implementation. Common sense. No minor in math required.

(please pardon my lack of formatting, AskMe doesn't want to cooperate)
posted by Afroblanco at 9:17 PM on July 2, 2006


damn, askme made a hash out of my comment. Well, you still get what I'm saying.

I think I know what you're getting at. If you want to get all technical on me, let's pretend that instead of i<5 and j5, we have iy and jy, and y just happens to be 5. same deal. nested loops=n2, which I argue is something that pretty much anyone could figure out on their own.
posted by Afroblanco at 9:19 PM on July 2, 2006


(Ok, askme fucked up my comment again. iy should appear as "i < y" and jy should appear as "j < y" without the extraneous spaces. Posting code to AskMe is no fun at all.)
posted by Afroblanco at 9:21 PM on July 2, 2006


A while back I ran across an essay on Math for Programmers. I don't agree with all of it, but he makes some good points.
posted by Galvatron at 11:35 PM on July 2, 2006


Whatever you do, do PROOFS. Proofs are something which most people are under-exposed to. There is a symmetry between rigorous proof and programming.

Also, do recurrence relations, deriving the 'formula' for the Fibonacci sequence. There's something pretty magical about finding closed form solutions for crappy situations that can make a math believer out of people.

Or maybe just explain how splines work.
posted by fleacircus at 7:52 AM on July 3, 2006


I'd say for a 4 week course, learn the math appropriate to the problems you are given to solve. You've only got four weeks.

If you go from the four week course on to something bigger, you can learn more math and more programming. If you are in your 20's, you've got another 60+ years to get better in both. Never stop.

I always confront my own ignorance in any programming project, and have found that you can't study it all at once. It just comes with the territory and should not be feared, just confronted.

Most of the advice above is a selection in personal bias. What will work for you will work for you.

That said, a lot of problems involve matrix manipulation and internalizing the notation for that is pretty useful. You'll see it a bunch in loops and algortithms.
posted by FauxScot at 11:05 AM on July 3, 2006


People talk about big-o and little-o as being important. Meh. If you have common sense, you can get by without this. Ok, so you have one loop that runs five times. Great. Ok, so you have another loop nested inside the first loop that also runs five times. It doesn't take a genius to see that any code inside the inner loop will run 25 times. Thus, your program will run 5 times slower if you have this nested loop. Moral of the story - don't use nested loops unless you have to. It's not rocket science.
Oh yeah, and Calc? HAHAHAHAHAHAHAHAHAHAH. Yeah, the other day, I was spec'ing out a new app for our site, and my boss came up to me and said, "Umm, Afroblanco, I'm gonna need you to do me a favor. Could you please integrate Sec3 theta from -1 to infinity? Thanks. I'll be needing that by the end of the day." Please, don't waste your time with calc unless you *really* enjoy math.

If your life aspiration is to write web applications, then, yes, by all means, put down that math book.

Otherwise...
posted by blenderfish at 9:10 PM on July 4, 2006


« Older How to get individual (permalinks) to work in...   |   What is this goofy song about everything the band... Newer »
This thread is closed to new comments.