Computers and Algebra

I just finished attending a 3 day workshop on Computers and Algebra held in my University. Here is the website.

When a professor asked me a few months ago if I would be interested in attending, I told him yes. My motivation back then was curiosity. We hear a lot about how a mathematics background is important for a computer science student and it seemed like a good platform to learn something.

Some nitpicking first. It didn’t seem like a workshop to me. At least, when I hear the word “workshop”, I expect to be doing something. What actually happened was a series of lectures with Q&A sessions sprinkled in-between. But in spite of that, it was an interesting experience.

The word “Algebra” makes me think of polynomials and related matter – high school stuff. I went into the workshop expecting to be able to follow the technical jargon. To my utter dismay (and horror), I could not properly follow ANY of the mathematics lectures! The speakers all assured me that it was basic stuff which they spoke about; which means that my math isn’t good right now.

One of the speakers talked about prime numbers. That got me thinking about making a program to check for a prime number. It isn’t a difficult task; something most computer science students are taught as a textbook exercise after they learn about loops. What specifically caught my attention was how to optimize the answer.

A simple way to check if a random number “N” is prime is to divide all the numbers between 1 and N with N. If none of them are perfectly divisible, then we caught a prime! Its a very wasteful tactic and the first level of optimization students are taught is to limit the check to all numbers between 1 and N/2. This range can be further reduced to all numbers between 1 and square-root(N).

I began to wonder if something more could be done. My search led me to this paper titled Primes is in P. Its a PDF link to a 9-page paper. What surprised me was that one of the conference speakers mentioned this very paper. … And I couldn’t understand a word of it! 😦

In the end, I came away from the conference humbled and inspired. I’m going to add “algebra” on my TO-DO list.