23
$\begingroup$

I have a reasonable undergrad math education but have never been 100% comfortable with abstract algebra (the mathematics of groups, rings, fields etc. ). I think this was partly as I needed to see applications and any that I could find were in physics, not CS. As my interest is really CS, are there any materials available now (online drafts, lecture notes, videos, books) that cover abstract algebra from the point of view of applications in CS and in particularly algorithms/theory? I am happy for these applications to be entirely theoretical but they shouldn't assume any pre-existing abstract algebra knowledge.

I am pretty sure that were these resources to exist, they would be appreciated by a large number of CS researchers.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ stackexchange gives plenty of "Related" questions to yours on the right hand side bar. Please read them first, in particular Algebraic structures in Computer Science. $\endgroup$
    – Uday Reddy
    Commented Feb 24, 2013 at 10:57
  • 1
    $\begingroup$ @UdayReddy Thanks. I am reading those and some of the links have good stuff in them. However, ideally I am looking for a lecture course entitled "An introduction to abstract algebra for theoretical computer scientists" (as a random fictional example) rather than a list of CS results where abstract algebra have been crucial. My interest is really on algorithms/theory and far from category theory, for example. $\endgroup$
    – Majid
    Commented Feb 24, 2013 at 11:11

4 Answers 4

Reset to default
19
$\begingroup$

You could try the notes from Madhu Sudan's course: Algebra and Computation

Improve this answer
$\endgroup$
1
  • $\begingroup$ This answers the question very nicely. It's a shame that "Mathematics for Computer Science" courses such as MIT's 6.042 don't seem to cover any abstract algebra. At least not the ones I have seen. $\endgroup$
    – Majid
    Commented Feb 25, 2013 at 12:51
14
$\begingroup$

One possibily path into abstract algebra could be to look at it from point of view of cryptography, which is about algorithms on finite field. Fields are rings, and fields are also two groups coupled by simple laws. Field theory uses vector spaces in prominent position (Galois theory), so this angle should cover a lot of abstract algebra. The book

A Computational Introduction to Number Theory and Algebra by V. Shoup

could therefore be of interest.

My personal recommendation would be to ignore applications, and study a basic undergraduate maths text on abstract algebra. There is no shortage of those. Just trust that all this stuff is useful, and that the use will reveal itself more easily once you have a basic grasp of the material.

Most basic algebra is constructive and you can easily implement basic concepts to gain a better understanding, e.g. algorithms that check if a multiplication table is a group, an equation solver in a group, a program that checks if two algebraic structures are isomorphic etc. Most of these problems have brute-force solutions which are easy to implement, but slow. The more you learn about algebra, the more algorithmic shortcuts you can make, to speed up your programs. E.g. the famous Miller-Rabin and AKS primality tests.

Improve this answer
$\endgroup$
3
$\begingroup$

Check out this book by Rudolf Lidl and Harald Niederreiter: Introduction to Finite Fields and its Applications (2nd edition, 1994) http://www.amazon.com/Introduction-Finite-Fields-their-Applications/dp/0521460948

Quoting the book description in Amazon: "The theory of finite fields is a branch of modern algebra that has come to the fore in recent years because of its diverse applications in such areas as combinatorics, coding theory, cryptology and the mathematical study of switching circuits."

Improve this answer
$\endgroup$
0
0
$\begingroup$

Besides cryptography, a very nice practical application of algebra in computer science is perhaps the implementaion of fractions, where numerator and denominator are of an integral or "big integer" type and encoding length is kepts small by reducing fractions (i.e. factoring out the greatest common divisor of numerator and denominator).

Concerning "big integer" data types, an interesting result is the so-called "Chinese remainder theorem" which permits the parallelization of integer operations once a representation as prime factors of the arguments are known.

Furthermore, most of the stuff found in algebra can be aesthetically pleasing (just a personal point of view).

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ I don't see how this addresses the question? $\endgroup$
    – András Salamon
    Commented Feb 25, 2013 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.