What should be included in a freshman 'Mathematics for computer programmers' course?

Question

Many universities are changing up the way that they teach math service courses. 1-3 semesters of calculus and maybe a course in linear algebra are often included in majors (such as computer science) that will not use the majority of the material.

However, these courses are often justified by saying that they promote creative and mathematical thinking, and I agree that they are good precisely because of that. However, many fields of mathematics outside of calculus have the same effect.

I'd like to hear from a professional computer programmer's viewpoint what topics could be covered in a yearlong `Mathematics for Computer Programmers' course such that:

1. This course would be the only math course (besides remedial courses) that computer science students take.
2. The course needs to introduce them to the same level of mathematical rigor as a typical 2-semester calculus sequence.
3. The course covers the majority of mathematics that computer programmers tend to run into.

Additional requirements can be added if these are too vague.

Answer 1

TL;DR 2-semester course is not enough.

Disclaimer: I write this as a computer-scientist that uses math a lot in his work (I'm a research assistant at a university).

Introduction:

There are three (overlapping) aspects of math in computer science:

• Math that is actually useful.
• Math that you can run into, and is generally good to know.
• Math that lets you build more awesome math.

First is essential, because the students need to be able to do stuff. Second is important, because you cannot teach students everything, and at the same time trying to get into a new field all by yourself is quite hard (i.e. it's good to know the barest basics of everything). The third are these which aren't directly useful, but present meta-concepts that happen all the time (a bit like design patterns in programming); you can live without them, but intuition you gain there makes life much easier.

The list was sorted by (subjectively defined) importance.

Math that is actually useful.

• Logic. How to handle quantifiers and read formulas, tautologies, satisfiability; less important: free variables, substitutions and unifiers.
• Asymptotics. This is a must. The big-oh notation, etc., term manipulation, basic limits, sequences and series, both $\to \infty$ and $\to 0$.
• Graph theory. This is a must. Graphs are so prevalent and ubiquitous nowadays that it would be a major setback to not know the basics of graph theory (e.g. searching algorithms, connectedness and flows).
• Linear algebra. This is a must. What is a linear space, matrices, determinants, orthogonalization, linear programming, perhaps even eigenvalues.
• Probability. Strongly desirable. Discrete spaces, Bayes theorem, expected values, Markov's, Chebyshev and Chernoff inequalities, the law of large numbers.
• Data processing. Strongly desirable. It's important to know how to process a gathered set of data without destroying some of its vital properties. This includes a bit of statistics, some filters, means, clustering, basic approximation, modelling and regression.

Math that you can run into, and is generally good to know.

• Numerical analysis. Floating-point arithmetic and error-analysis are a must.
• Universal algebra. It's essential to make the students not afraid of abstract structures. No advanced stuff, no need for all the groups/rings/skew fields definitions. The barest essentials so that students won't run scared when they see algebraic data types in functional programming, monoids in automata theory or group theory in cryptography.
• Statistical and probabilistic modelling. This is strongly desirable. Markov chains and Monte-Carlo methods.
• Differential equations. Differential equations happen to explain a lot about world's interactions and are used frequently in multitude of practical applications. This is strongly desirable, because it's just hard to learn them with no help.
• Information theory and cryptography. This is a must for modern programmers. Symmetric and public-key cryptography, handshakes, entropy, notion of entropy extractor, Kolmogorov complexity, impossibility of perfect compression, lower bound on comparation-based sorting complexity.
• Signal processing. Fourier transform is strongly desirable. Kalman filters would be good, but there's not enough time. Just anything that would let them reduce the noise in a practical setting.

Math that lets you build more awesome math.

• Term rewriting. Notion of term rewriting is very powerful and underappreciated. A lot of processes can be explained in terms of term rewriting and it's good to know the relevant intuitions. It's useful for showing termination property of algorithms.
• Automata theory. The notion of finite automaton is a must.
• Complexity theory. Basic complexity classes and inter-dependencies (including randomized algorithms classes). Maybe other models of computations like $\lambda$-calculus or circuits.
• Number theory. The theory being beautiful and enriching is enough for me here.
• Game theory. You can find game theory in unexpected places, it's good to have this perspective. Nash equilibrium, prisoner dilemma, second-price auction.

Conclusion:

It's apparent that there's just too many things to cover during 2-semester course. If I had to pick, then I would choose the whole first group and nothing else (cryptography can be self-learned). However, I have no idea how to make there 2 semesters seem coherent. On the other hand, I think that it is possible to do in 4-semester course (e.g. one year, but double the load), and I would recommend it even at the cost of practical cs curriculum. With a stretch you could group it as follows: logic and asymptotics; graph theory, abstract algebra, automata, cryptography and information theory; numerical analysis, linear algebra, differential equations; probability, data processing, statistical and probabilistic modelling.

I hope this helps $\ddot\smile$

Answer 2

After reading the previous answers, I'd add logic and proofs. To reason about a program's (in)correctness is proofs, even if you don't go to the length of proving correctness formally.

Many students struggle with the idea of recursion, recursively defined functions/data structures, and the related proofs by induction.

More on the soft side, being able to express oneself clearly in English (or whatever the language used locally might be) seems to be correlated with being a good programmer. Besides, presenting an argument to non-specialists is often part of the job. So I'd insist on clearly written and reasoned homework (and not too sloppy exams).

And for the love of anything holy to you, do not overdo it. Yes, it would be extremely nice if they knew combinatorics, and probability, and linear algebra, and a bit of multivariable calculus, and enough number theory to understand RSA, a smattering of algebra for elliptic curve groups, and complexity theory, and... [sadly, our calculus curriculum came from collecting "wouldn't it be nice" comments from all engineering departments, with seemingly no criticall winnowing] concentrate on a few topics that are truly basic, mesh well with what they already know, and go smoothly over into courses taken in paralell/just afterwards. Offer a selction of optional courses for those who want to go into non-standard areas.

Answer 3

I'm not a professional programmer, but I worked in scientific programming for a couple years. Here are my picks.

1. Basic calculus

   I agree that calculus is overemphasized in many programs, but we can distill the useful parts. (And to study most higher level math, we need to.) Teach what limits, derivatives, and integrals are. The most important thing would be to emphasize their conceptual meaning and how they can be used. The student should come out with enough understanding to use calculus in real scenarios given access to computational algebra software like Mathematica.

   It should be sufficient to teach how to do these operations on polynomials and trig functions (since they are easy and common), some basic properties (such as linearity), and the Fundamental Theorem of Calculus. Leave out techniques like partial fractions and trigonometric substitution - these are not conceptually important, they can use Mathematica for that.

2. Numerical Analysis

   • Emphasize iterative methods and order of convergence

   • Include an in depth discussion of Monte Carlo integration and its generalization to other Monte Carlo algorithms. Teach them to solve problems by simulating data.

   • Cover asymptotics, Newton's method, truncation error (including Taylor's theorem here if it hasn't been covered already), analysis of algorithms

   • In a dream world, I'd also include discrete fourier transform on here, but this may not be feasible with only a pragmatic understanding of calculus. Perhaps best to leave for a later course for those who wish to learn it.

3. Logic (and other "proofs class" topics)

   • Logic itself is directly applicable to computer science.

   • Elementary set theory should be very intuitive to anyone who is used to working with arrays and lists all the time.

   • Direct, contrapositive, and contradiction proof methods will be needed for further topics. There should be a heavy emphasis on induction. (Recursion is basically induction.)

4. Combinatorics

   • Lexographic, colexicographic, and quasi-lexographic ordering, both in general and for monomials

   • Of course, some graph theory. Include depth/breadth first searches, Dijkstra's algorithm, Kruskal's algorithm.

5. Numerical Linear Algebra

   • The basics of linear algebra would, of course, need to be introduced before getting into the numerical part. Solving systems of linear equations is pervasive, and solving them quickly is definitely important.

   • For an example of applications, return to a graph theory for a moment to show them a linear algebraic graph drawing algorithm

   • Linear programming / convex analysis if there's time

6. Vector calculus

   This would be the last topic. This should be presented as a natural synthesis of everything learned so far. Anything in graphics programming requires a good understanding of vectors, as do many scientific programming applications. Learning how to take normals, how to compute projections, how to navigate vector fields, etc. all has direct practical value. Learning how to think about vectors in general does too. Due to time constraints, I wouldn't try to get any more in depth than that.

That's it. Those six topics should be enough for a very productive year long, five days a week class. I would caution against adding any more, as I think it's better to learn a few topics in depth than fly through a ton with only a shallow understanding.

I should also note that each of these subjects would be great for both short-term and ongoing programming projects. I would make these worth quite a lot of the grade, and save the rest for weekly quizzes and some written homework.

Answer 4

• I have been a professional programmer since I graduated in 2000.
• My degree is an MMath. I never studied CS.
• I will accept your premise of a single course, not give you a bucket list of everything potentially useful that adds up to at least a 1-year full-time syllabus.

I have used very close to none of the material from my degree in my professional work:

• The notion of mathematical rigour and what it means to prove something is close to essential. But whatever you study, if you aren't doing this then it really isn't university-level mathematics, so it doesn't help us choose a syllabus.
• A few specific concepts such as complexity are very important for communicating with other programmers. Complexity is also somewhat useful for noticing early that your code won't scale, but actually real computer programmers test that. You do not, strictly speaking, need to know what Omega(n^2) means in order to realise that looking at every pair of items will get slow eventually.
• At one point I was working in and around an entropy collector. I found it useful that I had taken a course on information theory, I actually knew what this "entropy" thing was that most of the programmers had no idea how to estimate rigorously. But that was just a fluke of course choice. I could just as well have read a book if I hadn't taken the course and if it had been all that important to my employer.
• One of my courses defined and proved the correctness of an algorithm for computation (the simplex method). If this kind of analysis would not be covered anyway by the CS syllabus, then it should be in the mathematics syllabus, and of course analysing that particular algorithm requires some abstract algebra. I've never used the simplex method professionally, but I have tried to work out whether my algorithm is correct.

The way I think and analyse problems, which was partly shaped by my degree, is fundamental to my work. Mathematics is certainly a respectable way to train for programming, but it's far from the only way, and I don't think there's any one thing on my university syllabus that I'd reject a CV just because it was missing. So I'd worry that this single course does half a job not because there isn't time to cover the necessary material, but because there isn't time to teach someone to think like a mathematician. If you crack the latter then the former is just picking up the right book when you need it. Or of learning geometry in the computer graphics course, mechanics in the physical modelling course, etc.

Now, I don't know whether your CS course does what I thought of as CS back in the day, or whether it's primarily concerned with producing employable software/hardware engineers ready to go. The mathematics requirements of each are rather different, but it might be that in the CS case, a lot of stuff that I consider to be mathematics will in fact be taught in the course, it just won't be called mathematics. So I don't know quite how to interpret "this is the only mathematics course they'll take". If they really do no other mathematics then to me it's not CS: call it software engineering. But I don't want to argue over what you call your courses, I'm just trying to understand what's called for.

So, this may be highly controversial, but my instinct is that:

• If the CS syllabus includes theoretical computer science, then the mathematics syllabus need only provide the necessary grounding for that. Consult the TCS syllabus to figure out what that is. There should also be content beyond that, but it doesn't actually matter what it is. Either elementary calculus or algebra provide plenty of opportunity for rigorous proof. Mechanics or probability/statistics might be more practically useful in life, but I think introductory courses don't really have time to avoid hand-waving important results so you risk sacrificing rigour. As long as the students have been taught what "doing mathematics" is, the specific content will appear in the courses it relates to, whether that's TCS or games programming.
• If the CS syllabus is all programming with very little TCS, then the "mathematics" syllabus should be TCS in disguise because that's the only way to present any theoretical material at all. Ditch the algebra (except that they'll need to know what vectors and matrices are) and calculus, do what you can from: computability (including classes of formal language and the machines that decide them), complexity, combinatorics, graph theory, information theory (entropy and codes), maybe some cryptology (which will bring in a bit of number theory). One course, two semesters, I guess you can introduce at least 4 fields in enough depth to matter? Teaching 'em mathematical physics so they can write games or the software for X-ray interferometers is someone else's problem.

I'm also guessing a bit what's considered "remedial". I'd expect an 18-year-old who wants to do a CS degree to already have mathematics education, and I would expect that education to include basic: geometry, trigonometry, dynamics, probability, calculus (know the fundamental theorem of calculus, a list of indefinite integrals, and the product rule. Maybe know l'Hôpital's rule. Probably not able to prove any of them but might be able to prove the derivatives of polynomials from first principles), proof by induction, maybe some abstract algebra, maybe some non-trivial statistics ("compute the mean" is trivial, by non-trivial I mean, "what's a two-tail test?" on upwards). But my expectations are based on a different education system, so might be out of line for your students. If any of that isn't remedial, it might be worth throwing it in just so that your degree provides a broad mathematical grounding in addition to the specialized CS. Unfortunately this turns back into that bucket list. I don't believe you can expect to take students who have never heard the word "integrate" except in the context of Brown v. Board of Education, and give them broad mathematics in the time available. So you might have to give up the aspirations of the mathematics department and cater to the CS department directly. I guess you're more or less at the mercy of how much time they give you?

Any or all applied mathematics could be useful to a programmer:

• you won't get far writing a physics engine if you don't know mechanics
• you can't be a quant without sophisticated statistical modelling and some economics / game theory
• without numerical analysis all your floating-point code blows up due to the "obvious" algorithm being numerically unstable

But you actually can't provide all of applied mathematics in the compulsory courses of a single undergraduate degree anyway, so why try. Ultimately it's domain knowledge for some programmers, it's not essential to the actual programming. You could just as well say that programmers might need to know tax law ;-)

For what it's worth, IIRC the "computation" (there was no "computer science") undergraduates at my university did something like half the first-year mathematics syllabus and then had to take a "foundations of mathematics" course including set theory and formal logic. How we laughed. But the intention of the course was to prepare them for academic computer science if anything: I don't think there was required to be any great advantage in preparing to be a programmer compared with the mathematics course. Or physics for that matter.

Answer 5

I think the general trend is that computer science initially was a subfield of mathematics, and has grown more and more apart from mathematics, to the point that there are universities that offer computer science programs without any math courses at all, my home university being one of them.

As a side note, I think this development is very bad, as programming an sich doesn't seem to be much of a science to me (programming websites and apps is very cool but I just wouldn't classify it as a science). I would argue that the university should not offer such programs. I think that computer science is more of a subfield of math than the other way around, which is why I might give you an overload of topics here ;)

The topics that you include should obviously depend on the rest of the curriculum. Of course, it's impossible to cover any of this topics comprehensively, but you should identify the elements that are important in the other courses that are offered and make the students comfortable with the ideas and math (with 'math', I mean the kind of deductions and/or calculations that are commonly done in this field).

This list probably differs from what professional programmers would say. A financial programmer would probably focus on probability, a game programmer on linear algebra (and maybe calculus), a cryptographer on number theory and information theory, and I can go on for a while.

I tried to order the list extremely loosely in order of $ \frac{\text{usefulness}}{\text{difficulty}} $

General skills
These are very important and not hard to learn. One of many possible uses is in algorithm analysis, where students are expected to do calculations with fractions, powers and logarithms. To my surprise, many of the computer science students had trouble with this (but of course, not everyone has the same background in math, so maybe you should do an extra section for the people that need extra practice with the basic math skills, just to not bother the students that have a sound knowledge with stuff that is way too easy for them). You can also fit things like proving something with induction in here and maybe more advanced skills such as finding a solution for a recurrent equation (just because they don't fit in anywhere else).

Asymptotics
Big O and it's friends are used in most courses about algorithmics, and limits provide a sound way to reason and provide rigor in calculus.

Graph theory
Graph theory is a very hot topic in computer science (and it will probably stay to be that way for a few decades). There is a large amount of algorithms important for computer science (this becomes very interesting if you combine it with probability: this way you can do stuff like facebooks friend suggestions), but in one course I would just focus on a few elementary algorithms (maybe something with node coloring or min/max cut, tree searches and a little bit on parallel algorithms).

Linear algebra
Extensively used in graphics and just a basic skill that comes in handy when doing anything geometric.

Combinatorics
Combinatorics pop up in a lot of places in algorithmics. For one course I would give some example of combinatoric proofs, and teach some basic stuff about binomial coefficients. Generating functions are very useful IMO, but probably way out of scope.

Probabililty
Probabilty is another topic that pops up all over the place. There is a lot you can cover as well. You can combine discrete probability with combinatorics and continuous probability with calculus.

Calculus
Students should be able to have a grasp of differential and integral calculus. In my country, this is mostly high school stuff, but high schools are of varying quality and there is some new stuff as well (partial integration, integration by substitution).

Number theory
Some basic number theory is used for encryption and sometimes comes in handy while analyzing algorithms. Basic topics are greatest common divisors, smallest common multiples, modular arithmetic...

Differential equations
Needed for simulation of real-world phenomenons. Programmers using this would be programmers working with graphics or simulations, and they would typically use finite-difference methods, as opposed to a mathematical approach.

Information theory
Used for encryption, compression and reliable transmission over noisy channels.

This maybe a little bit of a rant and it probably displays my view that for every mathematical field, you have a subfield in algorithmics (which in its turn is a part of computer science). I think that a student should have a good understanding of each of these topics to have a firm mathematical basis. In your situation it's probably a good idea to look at the courses and how many students take them, and maybe ask other professors on their opinion (for example, if there is a graphics course that has a low percentage of students that succeed, it may have to do with the amount of linear algebra, if there are no courses on cryptography or compression you can skip the number theory and information theory, etc...).

After this long list you can probably see why I think it's a bad idea to have just one (or even none) mathematics course in a computer science curriculum...

Answer 6

dtldarek's answer is excellent. The only thing I would add to it is a good foundation in proofs. While I don't run into proofs on the job, I've seen a tremendous number of proofs in my CS classes.

Experience with rigorous proofs also helps with logic and algorithms -- have you covered all the bases? Are there any places where this falls apart? Have you made any assumptions you shouldn't have? All good things to have in mind when writing programs.

[I have a BS in Math, did a career change to programming about 5 years ago, and am working on my MS in CS while holding a full time job as a software developer.]

Answer 7

"Computer programmers" is a bit broad, and I think the answer to this question depends on what exactly your university teaches in its own CS or Software Engineering department but doesn't technically label "math".

One thing to keep in mind is that Computer Science (and by extension anything in programming that's not engineering best practices, code organization, and such) is math, in that the theory of computation is in large part a formalization of how we do math.

I'd say that by far the most important thing that any programmer can be expected to know are under the discrete math banner. Graph theory (esp. trees and graph search), set theory, and formal logic (mostly propositional or first order) are backbones of programming. Going deeper, automata theory is important as well, but not as integral. However, it's likely that these topics are covered in the CS department already. If it's not, they're excellent candidates.

Another thing that's important is asympototic analysis, mostly in the form of Big O, Big Omega, and Big Theta. Again, this is usually introduced in a required CS course, but not necessarily. This is important enough to know that it tends to come up on interviews for software engineering positions. The ability to find the asymptotic behavior of recursive functions is also important, and less taught than the ability to do it for iterative processes (which are often trivially converted into polynomials). Obviously you only need to focus on more trivial recursive functions, proving a function's asymptotic behavior can be legitimately difficult and is very expansive, but single-variable recursion that can be solved with the "find the pattern" variety of problem solving is pretty good to teach. Finding the behavior of stuff like $M(1)=1;$ $M(n) = M(\lfloor\frac{1}{2}n\rfloor) + M(\lceil\frac{1}{2}n\rceil) + 2n + c;$ $n \in \mathbb{Z}^{1+};c\in \mathbb{Z}^{0+}$ can be immensely useful.

Then you start getting into the nitty gritty: statistics, regression, calculus, probability, and such are all very important, but only to certain subfields or people planning on going deeper into "CS" territory than "programming the front page of a comedy website". Being able to work with big data tends to require a lot of probability calculus (as does any machine learning). These skills are very in demand right now, but I'm not sure if you can cover enough to give the foundation in a single survey course. I mean, you're just plain not going to get to meaningfully explain gradients to anyone if you're going for reasonable breadth and replacing basic calculus.

Likewise linear algebra, which is important in computer graphics and computational geometry. You can find a good survey of the kind of math used in graphics by looking at any good Open GL tutorial, here's one for reference. It's mostly basic 2D and 3D matrix math and a tiny bit of quaternions, but even things like understanding what a basis is, whether a matrix is singular, or how to do an orthographic projection is very useful. Again, though, this may be covered in the university's computer graphics course. Granted if you put this in the course it could significantly lower the load on teaching this math in graphics and allow time for more advanced topics.

Combinatorics is also useful, if only because being able to count the number of unique password combinations of $n$ characters is useful. Cryptography is also traditionally a mathematical field, and is useful for all sorts of reasons, but may be a taaad advanced for a low level survey course.

Finally, as vonbrand pointed out, whichever combination of these you choose, formal instruction in proofs is very important. It can be done for any or all of these, and the merits of proving correctness is immense, even if they never "formally" do it again. Proofs also tend to introduce the ability to clearly express mathematical thoughts in words, even if those words are still surrounded by notation. That's a skill that isn't always valued highly enough.

Overall, there's a lot of useful math. The most useful is by far discrete, but the other math can be extremely useful to know depending on what the department already covers, what it wishes it didn't have to cover, and what sort of electives and specializations they offer.

Answer 8

Disclaimer: My answer is based on me being a computer science major, with an obscene interest in mathematics, to the point that I teach it, both on my own, and as a TA.

During regular programming, one thing I always come across, is the need to do some basic "regression". In quotation marks because really, it all comes down to, "I have n points, and need to find a [linear/exponential/whatever] function that crosses these n points". This is particularly something I find useful during development of software with graphical interfaces. Especially games, but really, anything with moving objects.

And of course, if you're doing anything in 3D, Linear Algebra is soooo useful! Learning how to view matrices as linear transformations (functions) with the stuff you normally learn about in algebra and calc. Like the fact that matrices can be injective, surjective, and have domains and ranges. And learning about eigenvalues and -vectors, and how they can be visualized.

Then, of course, discrete math is super important. Learning how to apply combinatorics and create and improve algorithms with decreased complexity has been a godsend.

Answer 9

One of the challenges here is that there is a big difference between software engineering and computer science. The latter has very rigorous mathematical underpinnings, whereas the former can often get away with very little math, depending on what area of industry you wind up working in. I'm assuming this is a program that is geared toward engineering.

What I've personally found the most useful in my work are linear algebra and signal analysis (Fourier transforms, convolution with filter kernels, etc.) Again, though, this is largely due to industry in which I work (industrial automation), where I deal with geometric transformations and interpretation of signals. If I was in process engineering, I might solve more differential equations. If I was in data mining or optimization, I might need to know more about linear programming and simplex methods.

One thing I will say is that I learned a lot more from my focused courses than I did from the 'survey' courses. My major included a required survey engineering course that covered a wide range of topics, but it covered each topic so briefly (no more than a week on a given area) that there was barely time to even get a taste of what the subject offered. I can understand the intention of the course (to help undergraduates discover what focus they might want to pursue), but I didn't learn anything significant from it that stuck with me. As such, it might be better to just teach Calculus, Linear Algebra or some other classic subject in full introductory depth, perhaps giving the student the option of which one to take. The student will retain more from the increased depth of the course and will likely develop better mathematical skills as a result of having to tackle more challenging problems than could be raised in a survey course.

Answer 10

None of the other answers have mentioned it thus far, so I'll add that lambda calculus would be a useful field to include.

In particular, several programming languages have introduced lambda functions to their syntax in the past several years. Java 8 was just released last month, introducing the concept to Java; C# added lambda functions in .Net 3.5(?) in 2007; C++ gained the functionality with C++11 in 2011.

Working as a TA as an undergraduate for a freshman-level course, this feature was definitely the most confusing piece of syntax the students encountered.

Answer 11

Something which I don't see mentioned here so far is mathematics in non-base 10. there are legitimate situations where bit shifting, binary algebra and hexadecimal are quite a benefit to coding. For example, if the device you're developing for has limited resources (embedded systems, legacy programs), using a bit shift can sometimes save precious memoryspace and processing cycles.

Answer 12

Actually there is NO REASON to include calculus level mathematics for a computer science degree. I repeat.. NO REASON. WHY is that, you might ask?? Because very few coders use heavy duty math (or even simple math) in their daily work. I've been coding for 16 years at both large and small corporations, and even when I worked at banks and mortgage companies, I hardly EVER needed anything more complex than multiplication. Put simply, coding is mostly logic and problem solving. As for those coders claiming that learning complex forms of math, teaches logic, I still have to disagree. If you want to learn coding logic, do some actual coding, or play a game of chess, or build a website in HTML and add some javascript functionality to it. There are far more interesting and practical ways to learn coding than bending your brain around rarely used formulas and procedures. So..other than earning colleges lots of money and denying tons of people, I am strongly against any kind of math for programmers. It just slows the real learning down.