I was curious if you had any discussions on what kind of math background new graduate students need to have? For instance, if the undergraduate institution did not have a good math program to support the CS curriculum, what specific topics should students self-study before going to graduate school?Most importantly you should have some familiarity with mathematical proofs. Mathematical maturity is more important than specific knowledge in any single topic.
Theoretical computer science is mostly discrete mathematics and other areas of discrete math play an important role: Discrete probability, combinatorics, algebra especially group theory, logic and number theory.
Depending on your interests analysis, measure theory, topology and algebraic geometry might be important. Almost every branch of mathematics has played some role in theoretical computer science.
I don't mean to scare you. As I said best to take any real math course (one with proofs, not just Plug-and-Chug Engineering math) and you can later pick up more specific math knowledge when you need it.
shouldn't your response be don't worry about it, you won't be getting into grad school for comp sci anyway?
ReplyDeleteWhat funny is that in the past I've seen mathematical types complain about "having to program" and programmer types complain about "having to write a proof." For me, I'd get chills proving that 0*a = 0 (in group theory) or showing that something was undecidable.
ReplyDeleteTo me these activities are far too similar. At least at the junior and senior undergraduate level. There's even a degree of type systems in there: if you need to prove some scalar satisfies P(x), you better not end up with a set or a vector.
In both cases, you also need to get over the tactical problems. For any 100 line program or single page proof, there are probably a dozen stupid little "tricks" that you just need to learn from reading other proofs/programs or through experience. Getting hung up on the syntactic/semantic rules and the early tactical tricks just clouds the strategic activity, where designing an algorithm is similar to designing a proof.
And if you don't believe me, take it up with Curry and Howard.
Algebra algebra algebra. And some more algebra. Its not just useful, its also pretty.
ReplyDelete(The lists people have been describing mostly relate to CS theory but for graphics and vision, in addition to linear algebra, topics like differential geometry are also valuable/essential.)
ReplyDeleteI was an undergraduate math major and can't think of a math course that I took that hasn't been useful in understanding some CS theory paper or other. On the other hand, self-study is also important. For example, Lance mentioned discrete probability as an important area. The most useful aspect in lots of CS theory work has been the "probabilistic method" but you would be hard-pressed to find an undergraduate course on the subject. It is extremely accessible, perfect for self-study, and there are some great texts like Alon and Spencer's
text on the subject.
I think if you intend on applying for graduate schools in theoretical computer science, you're shooting yourself in the foot by not having any mathematical coursework in your background. I get the impression that it's something that admissions committees look favorably upon (at least for theory).
ReplyDeleteIf I could go back now and change the math courses which I took when I was an undergraduate, I would get rid of algebraic geometry (which I was not mature enough to appreciate) and of differential geometry, and I would add probability, statistics, and advanced linear algebra. Mostly I agree with Scott.
ReplyDeleteAs people suggest, the most important math skill to get as an undergrad is math agility--the ability to feel comfortable picking up and learning new topics. In the best case, CS theory hopefulls would do a double major.
ReplyDeleteOn the other hand, I don't think it's that important (at the undergrad stage) to pick up specifically useful mathematics. The reason is that until you have some experience (at least 4-5 high level math courses), it's very difficult to approach new math from the right stand point--you don't yet have a philosophy, or a way of partitioning the world so the new concepts and problems look like the old ones, just in different clothing.
So, as Scott seems to advocate, you should just take things that seem "cool" to you. Topology, complex analysis, galois theory, number theory, etc. The unfortunate thing about differential geometry is that, while it's a beautiful subject, it is often taught at an incessantly boring level of generality, so you need a lot of stamina just to get to anything interesting.
Whatever you learn, it won't be enough.
ReplyDeleteYou'll have to learn new things and (more importantly) appreciate them at a deeper level to succesfully do research.
Scott mentioned this in his long-ago guest-blogging gig, you can only REALLY appreciate something when you actually use it in your OWN work.
In fact, I might even advice this undergrad to forget about taking courses and just try to find a good theory problem and work hard on it.
You will probably learn plenty of math along the way and a STOC/FOCS paper is probably more impressive than any number of graduate math courses!
But yeah, if you're going to take math courses, just mastering the notion of proof is more key than the specific content, so any number of courses could serve the goal pretty well.
A couple of anonymouses above have suggested that you won't get into CS grad school unless you have a lot of math courses.
ReplyDeleteMy observation leads me to think that this is NOT a huge factor in the admissions decision.
They want to know if you'll be a good RESEARCHER not if you are a good course taker or if you are "someone who knows a lot of math."
To this end the biggest factors are:
(1) Recommendations from other succesful researchers (e.g. your professors).
(2) The research that you've actually participated in.
Of course, having a lot of math courses on your transcript certainly won't hurt you, but its probably not going to influence the admissions decision that much(compared to the other factors involved).
Theoreticians need a sound mathematical education, and that's acquired usually through analysis and algebra. Some probability theory and discrete mathematics won't hurt. Other than that, my advice is to take math courses that you like. You'll do a better job absorbing the course material if you are motivated by interest rather than perceived usefulness.
ReplyDeleteI have the following situation, related to this discussion. I have a PhD student early in his Phd career that thinks that he wants to do theory. But
ReplyDeletehis mathemtical background/skills are too weak at this point to be able to obtain results publishable in the theory literature. I am try to decide whether it would be better to advise him:
* Take 1-2 years of mathematics courses to build up his skills, and not worry too much about publishing, or
* Try to build his skills by trying to get publishable results, even though initially there is little chance for success
The students hinks he really wants to do theory.
Grad school is so cushy--there's time to sleep in, party, do research, and learn. If you feel like it, you can take a week or a month off and no one notices.
ReplyDeleteSo why shouldn't you be expected to work hard? Why can't he both take math courses, and do research?
Generic advice I give to students who've asked me that question is:
ReplyDeleteThe math you learn is the math you'll use, and the math you use is the math you'll learn. I think that the more mathematical expertise the community has, the more chances we have of finding the right area of mathematics to solve any particular problem. Each researcher gets an ``edge'' in solving the problems susceptible to the branches of mathematics and techniques that that researcher knows BETTER than the other researchers. So we shouldn't all study the same math.
On the other hand, as other people have also pointed out, I don't really feel that I've understood a mathematical topic until I can apply it to solve some problem that I didn't know previously. Often, I don't ``apply'' a technique I previously learned as much as solve a problem and then RECOGNIZE the technique I used as being one I read about previously. Then I understand the technique.
Russell Impagliazzo
I studies CS for the Bachelor degree. I regret my decision now. If I had the choice again, I would study MATH and PHYSICS, then you can do a masters in CS easily. From my view, it is a crime to a have Bachelor program in CS. Because you will later find yourself having much difficulty in advanced topics. You need tons of math from every direction in Masters of CS.
ReplyDelete