What Math Courses Should We Teach CS Students?

Coryoth asks: "If you're taking computer science then getting as much mathematics as you can is probably a good idea. Ultimately, however, there are only so many math courses you an squeeze in. Given that, what areas of mathematics should we be teaching CS students for maximum benefit? Traditionally university math courses are structured around the needs of the physical sciences and engineering, which means calculus is what gets offered. While a decent calculus course can teach a certain amount of formality in reasoning, wouldn't CS students be better served with a course in mathematical logic and foundations with its greater degree of formal reasoning and obvious connections to fundamental concepts in computer science? Are courses in abstract algebra and graph theory going to be useful to CS students? Should courses in category theory (yes, it applies to computer science) be required of students going on in theoretical computer science? In short — what areas of mathematics are going to be the most useful and most applicable to computer science students? What courses were of the most value to you?"

Comments

Re:computational statistics

[Peter Mork]

I'm willing to assert something stronger. Instead of requiring undergrads to spend a year learning calculus, the requirement for all undergrads should be basic statistics. In the decade or so since I completed a math degree, I've used calculus only rarely (the intended implication being that even a mathematician might find little need for calculus). Statistics, on the other hand, are needed to correctly interpret newspaper articles.

Re:computational statistics

[arivanov]

In my biased opinion, that is a course that MUST NOT be taught to CS students unless they have the full one year worth of Probability Theory before that. In fact it is a course that MUST NOT be taught to any scientific student who has not taken a full probability theory course first. Unfortunately, many universities especially in the US tend to do that - teaching stats without teaching the probability theory which makes them possible.

As far probability theory itself is concerned its knowledge is essential for nearly any task in CS starting from an OS and all the way to transaction systems especially if the system is operating under a resource constraint. The time your request traverses the system, the completion rate, etc are all described by Markov chains and there is a appallingly low percentage of CS people who actually know them and can understand how their systems behave. There is no way in hell you can optimise or even understand a complex system without this knowledge. Unfortunately most Unis now prefer to use this time to teach marketing buzzword bollocks also known as Unified Process, Agile, etc instead.

The second most important math area for a CS student is possibly optimal control. This one is also nowdays omitted from some university curicullae which IMO is an absolute madness.

Maybe I just misunderstand CS

[A beautiful mind]

...but generally I received much more maths than I've seen mentioned in other posts in my five years of university while studying CS (not in the US).

The biggest chunk of it all was 6 semesters of Analysis and 4 of numerical analysis.

I was also told that only two other professions get slightly more maths: "applied mathematicians" and physicists.

Am I wrong to assume that CS education is much more maths based in the EU than in the USA?

Formal grammar, predicate calculus, statistics

[Twylite]

Start by making sure you understand the distinction between Computer Science and its related disciplines, and that this is a CS course. Read the overview report from the ACM Curricula Recommendations..

It is apparent from the ACM's recommendations (amongst others) that a lot of mathematics traditionally covered at universities(such as calculus) is not strongly related to Computer Science. That said, there are many applications of computing that require strong skills in these areas (scientific computing and cryptography for example) so they are not a bad option.

Important numerical and logical fundamentals that support the learning and use of undergraduate Computer Science include:

• Basic computing theory (formal grammars and finite automata). Understanding the qualities and use of state machines and formal grammars is essential in many fields of computer science including algorithm and protocol design, modeling robust systems, and creating parsers (e.g. for domain specific languages). It is also necessary to understand the halting problem and turing theory. Most of the theory requires the use of proof by induction or construction, which (in my experience) are the most common proof techniques in CS.
• First-order logic (predicate calculus). Also exceptionally valuable in the development of data structures and algorithms, and for communicating between domains.
• Graph theory. Understanding complexity, efficiency and optimisation in many aspects of CS (including compilers, algorithms, networks, data structures, etc) requires an understand of graph theory.
• Statistics. You will use it in most forms of analysis, at least to verify that a real-world realisation matches the predictions of a theory. Also valuable for performance analysis and optimisation to determine performance distribution and bounds.

Re:computational statistics

[nelsonal]

I think most everyone would be improved by more exposure to statistics. Business is one degree that most needs more calculus (most of what businessmen deal with is rates of change). For example the income statement contains the first derivative of most of the balance sheet, but I've never heard the term even broadly hinted at in any business classes.

Re:Core Math for Comp Sci.

[Enselic]

I agree with Linera Algebra, if you know linear algebra, you can pick up on 3D rendering APIs easily, and making 3D games is great fun, and you learn a lot about programming in general, like the need to structure your code (source code of 3D games without good structure is hell to modify).

Also, a lot of geometrical problems can be solved using Linear Algebra, things that can be useful in GUI code for instance (like, which of these arbitrary line segments are closest to the cursor, what angle does these lines form, etc etc).

Re:Why do CS?

[microTodd]

Operating System developer.

Compiler developer.

Artificial Intelligence researcher.

Search engine algorithm developer.

I have a Master's in CS. Yes, I agree that at the higher end CS is basically a specialized math degree. But there is that touch of applied math thrown in that separates it from a mathematician or statistician.

Even better, if you pair up a CS degree with something applied (physics, mech engineering, chemistry) you suddenly become someone very valuable to any organization trying to build advanced software. Yes, a biologist could hack out some code to study protein folding, but if you're also a CS guru then you can make a very efficient protein folding algorithm and save zillions of computing hours.

According to Ron Graham and Donald Knuth

[robkill]

Ron Graham was head of Math Research at AT&T Bell Labs back in the '80's. Knuth should need no introduction.

Concrete Mathematics

Re:Some Math greater than Other Math

[tritonman]

I think they need to separate CS into two branches, one that's "computer software engineering" and another that's "computer science". The first focuses more on software engineering and different languages. The second focuses on one language (probably c++) and has more intense math and physics as this is more related to science. The reasoning would be that there tend to be two types of programmers. Those who work with scientists and really need an understanding of calculus and of physics forulas and those who work on DB front-end type stuff, these require a knowledge of some things like set theory and discrete math, but they don't need to have a deep understanding of calculus or have an understanding of physics.

Re:Some Math greater than Other Math

[JBHarris]

I go to a smaller college in Columbus, GA....Columbus State University...in fact early registration for Spring Semester was today. Here at CSU, they have split the CS degrees into two separate camps....The CS-Systems Track & the CS-Applied Track. They are nearly exactly what you have outlined. I am more of a systems (theory) guy, and I hope to lead a team of Applied guys (coders). This isn't about salary or power, it is about what you do best. I cannot sit behind a desk and write code for 8 hours a day, plus I am a visual thinker. I can layout advanced problems and envision solutions, but my expertise falls apart when I start coding them...I get lost in the forest. However, some people cannot see the big picture but they have incredible focus on the smaller, more intricate problems. To each his own path.

This after nearly 6 years designing/programming full-time. I just recently decided to go back & get my degree to increase my potential value, plus after being promoted to Product Design Lead, I realized I needed to get on the ball with my degree or someone hot-shot kid straight out of college would take my job.

Yes, yes, yes, Linear Algebra.

[Malkin]

SQLGuru is absolutely right. If you want to do graphics, or want to be a game programmer in general, you should absolutely study linear algebra.

I would also like to emphasize that as much as university programs tend to be focused on theory, it would be beneficial for the students to have some inkling of what the applications of these various branches of math are. I studied linear algebra in college, but I was forced to do an aggressive review of it, later in my career, because I had retained very little of it. Had I understood how important linear algebra was to 3D graphics, back when I was studying it, I'd have been much more excited about the topic, and would have retained the information better. Unfortunately, our program provided no context, whatsoever, for what we were learning, so we never really knew why we were studying it in the first place.

Re:Yes, yes, yes, Linear Algebra.

[elwinc]

I second the suggestion of linear algebra. Here's how I would do it:

1 semester of graphics. While teaching graphics, make sure to emphasize the matrices. Students will get concrete visual examples of what matrix multiplication can do: rotation, scaling, general affine transforms. Graphics is useful in itself, and becomes a stepping stone to linear algebra.

Then 1 semester of linear algebra, with lots of practical examples. Linear algebra is the stepping stone to data mining. it also leads other important statistical techniques used in pattern recognition and machine learning.

Delving into those statistical techniques is graduate level work, but by knowing linear algebra, a CS student has the tools to learn the basics from a book.

Lemme put it like this: If your student wants to work for Google or similar cutting edge companies, she should be familiar with linear algebra. If she wants to spend her career translating sales records from one database format to another, she can probably skip the linear algebra.