# Math for computer science?

Math for computer science? I'm a computer science major and just completed linear algebra. Many courses are available to take now. Of particular interest: number theory and abstract algebra (Modern Algebra). Which one do you recommend? Is there any overlap between the two courses? Which one is more applicable to computer science?

Thanks.

-
Talk to a real-life adviser. – anon Jun 9 '12 at 1:14
How about graph theory/combinatorics? – John Engbers Jun 9 '12 at 2:31
You know, I agree with anon's comment, but I really can't see closing this question. What's wrong with it? – Gerry Myerson Jun 9 '12 at 12:44
Four votes to close, and not a single comment to say why. WTF? – Gerry Myerson Jun 10 '12 at 12:53
@Gerry Myerson My first action as a 10K user was to cast the last required re-open vote. Hopefully the OP comes back to edit the question suitably, but they haven't been seen for 2 days. Fair enough, if my first question was closed for apparently no reason right after I joined the site I might not have returned either. – Ragib Zaman Jun 11 '12 at 14:49

Abstract algebra, IMHO -- by a wide margin.

There are a wealth of applications of algebra to theoretical and even practical computer science. It's also beginning to go the other way -- theoretical computer science influencing research in abstract algebra.

Some example of the former (applications of algebra to CS) include the theory of groups, semigroups and monoids to automata and formal languages, particularly finite-state automata and languages. In fact, semigroup/monoid theory provides a very powerful and elegant way to look at finite automata -- for example a "recognizable" (finite state) set is $h^{-1}(P)$ where $P \subseteq M, M$ a finite monoid, $h:\Sigma^* \rightarrow M$ a monoid morphism, and a large, rich theory takes off from there.

In the other direction, a group is said to be "automatic" if it is finitely generated (it is all the products of a finite set of generator elements), group multiplication can be represented by a finite-state automaton, as can the property that a particular product of generators multiplies out to the groups unit. That leads to interesting application to groups in Euclidean space and on 3-manifolds and others.

Number theory is a wonderful branch of mathematics, perhaps the "purest" branch. It finds occasional application within theoretical CS, but not nearly to the same extent as algebra.

I wish I had taken more algebra courses as a CS grad student -- I'd have a lot less to catch up on now. More generally, the kind of thinking in abstract algebra -- axiomatization, morphism, composition, decomposition, quotient, etc etc will stand you in good stead throughout CS.

-

If you thumb through Knuth's Art of Computer Programming (better: if you read it, cover to cover), I think you'll find a lot more Number Theory there than Abstract Algebra. Disclaimer: I'm a Number Theorist, and I probably claim more of Math as Number Theory than other people would.

-
That's a good point. It's probably due to the question of what kind of CS is the OP interested in -- theoretical or practical. When you get down to actually writing and analyzing programs, number theory is often useful. So is algebra, but it may not be as obvious. – David Lewis Jun 9 '12 at 15:51

As usual the answer is, it depends. If you go into a field like algorithms and end up wishing to do algorithmic number theory then surely, as the name implies, you need to know algorithms. If you go into cryptography, you'll also need number theory, as RSA and elliptic curve cryptography use a lot of it.

However if you go into want to go into something like signal processing or coding theory and information theory, you'll be better off with abstract algebra. A lot of graph theory also has some algebraic components.

On a final note, most number theory beyond the elementary level requires an understanding of groups, rings, and fields. Even one's understanding of elementary number theory can be enriched with a knowledge of group theory.

For a similar discussion see this, this, and this.

-

Abstract algebra is more applicable - for example, in the Darcs "Theory of Patches," which is an algebra where patches can be composed and most patches can be commuted, so you can take an older version of your code and apply specific patches out of sequence without catching up to the latest version. See, for example, http://en.wikibooks.org/wiki/Understanding_Darcs/Patch_theory. That's all applied abstract algebra.

-