Saturday, September 12, 2009

Exactly what math background is required for theory material?

I am about dive into theory. I have taken the undergraduate intro to theory class and now I am going to take the graduate level classes. First stop is the Theory of Automata which begins Monday night. We will cover finite state automata/regular languages and pushdown automata/context-free languages. We are using Elaine Rich's text.

As a beginning theory student one thing that I find difficult is knowing exactly what math background I need in order to be strong in my theory classes. Elaine Rich has an appendix that provides a review of math material.

Some of that topics in the appendix:
Logic
Sets
Relations
Functions
Closures
Proof Techniques
Mathematical Induction
Pigeonhole Principle
Complexity of Algos

What classes was I supposed to take to learn the necessary mathematics needed for mastery of theory of computer science, I wonder? Do a lot of theory folks have a few undergrad mathematics classes on their transcript? It seems like logic, discrete math, set theory, combinatorics, and classes that demand proof writing are needed. This isn't a huge deal, but to take 4 undergrad math classes, including the calculus I,II,and III in addition to the other required undergrad computer science classes for your undergrad seems like a lot. Is this what most theory people have done before hitting the theory material at the masters level? What other math classes are required to master theory? Which are more important?

This is a question that keeps me up at night as I scramble to get the math background and level of sophistication required to figure out theory and be a strong student of the topic.

2 comments:

Anonymous said...

Do a lot of theory folks have a few undergrad mathematics classes on their transcript? It seems like logic, discrete math, set theory, combinatorics, and classes that demand proof writing are needed.

Most people don't take full courses in logic or set theory. Almost everyone takes a discrete math course. Beyond that, it's valuable to study abstract algebra, combinatorics, number theory, or probability. Few computer scientists study all four, but it's relatively common to take a course on at least one.

Alex McFerron said...

Thanks! I appreciate the info. I am working on abstract algebra now.