6
$\begingroup$

Possible Duplicate:
What kind of mathematical background is needed for complexity theory?

I'm a final year undergrad and I'm looking to pursue a PhD in theoretical computer science in the long term. I've been admitted to some great schools to do theory, I'm looking to defer all my admits to study math for a year in the university.

I'd very much appreciate your thoughts on the following couple of questions.

  1. So, given that I'm not really sure what sort of theory I want to be doing at grad school (as of now, algorithms and combinatorics) what sort of things should I be looking to study there?

  2. As someone who has studied computer science and not pure mathematics for the last few years, I want to take the next few months to prepare myself for the course. Can anyone recommend areas (and/or books) to bone up on before going there? (Since for instance, I never formally studied abstract algebra or complex analysis)

Thanks.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ General advice that I have heard from various people is that you can always learn the required math when you need them, so probably there is no need to spend another year learning math. There is no sufficient amount of math, you will always need to learn new things, the sooner you have a problem to work on the better it is. We have had a number of question on required math for TCS, you may want to check them first. $\endgroup$
    – Kaveh
    Commented Mar 24, 2011 at 0:33
  • $\begingroup$ Hi, Thanks for the advice. The thing is, while I have heard the same, I'm really looking to take a year off before starting grad school and want to make the best use of my time at Cambridge. $\endgroup$
    – user4363
    Commented Mar 24, 2011 at 0:38
  • 3
    $\begingroup$ see these: 1, 2, 3, 4, $\endgroup$
    – Kaveh
    Commented Mar 24, 2011 at 0:44
  • 1
    $\begingroup$ 5, 6. If they don't answer your question and you have a more specific question about books in a particular area of TCS then it might be better to edit your post and focus it to a specific area, e.g. "what mathematical background is needed for combinatorics?" $\endgroup$
    – Kaveh
    Commented Mar 24, 2011 at 0:44
  • 1
    $\begingroup$ Crosspost on mathoverflow $\endgroup$
    – Marc Bury
    Commented Mar 24, 2011 at 0:47

3 Answers 3

Reset to default
4
$\begingroup$

do the tripos! its an incredibly awesome opportunity and many of its alums are fantastic computer scientists.

ultimately though its your life though and you should do stuff because you'll enjoy it.

Improve this answer
$\endgroup$
2
$\begingroup$

I am in a similar position as you and I have asked this before (see link 1). Studying only mathematics for a year is not necessary, but it's up to you to determine how comfortable you are wuth math. Many TCS papers contain a lot of math, which can be daunting, especially if they are not from your area of expertise. I am learning as I go for more than half a year now and I have accumulated more knowledge than I had in the past two years studying. TCS.SE has been a very good stimuli, since I am exposed to problems that I normally wouldn't, unless I attended a dozen of conferences or so.

However, studying only mathematics for a year can be dangerous, too. First of all, you could be intimidated if you allow yourself to go too deep in a subject. Although some undestanding is required, some areas of mathematics are supposed to be only a tool by computer scientists. A certain level of knowledge is needed to effectively use the tool, but you don't have to know how exactly it works or how it would be improved. To reflect this, reverse your situation and assume you are a mathematician needing some programming skills. The amount of knowledge from TCS would be minimal, yet going too deep in TCS could lead to abandon your goal altogether.

The previous was a "DFS" kind of problem, i.e. going too deep. The other problem is expanding too much , i.e. BFS. There are many areas of mathematics with complex relations between them, sometimes even being incompatible. Fields are becoming more or less relevant as the knowledge of mathematics progresses and new breakthroughs arise. Simply put, you could be caught on the crazy new trend in mathematics, which can overstate or understate the importance of certain areas. That can be good if you are a mathematician, however it can serve as a distraction if you are a computer scientist. Some areas of mathematics may be irrelevant to your cause altogether. For a more hands-on example, consider a mechanical engineer. His machines follow the rules of quantum physics, but he doesn't care about that level of abstraction, he can work using classical mechanics and ignore the quantum level. Yet, it is possible that if he studies physics in detail quantum mechanics will stray him afar from his initial goals.

All that said, although "getting lost" in mathematical knowledge is dangerous, going a bit further than needed is beneficial. This extra knowledge can help you see patterns and solutions that you wouldn't otherwise , expanding your "arsenal" with new thinking approaches. As you can see, at least in my opinion, knowing how far is far enough in terms of mathematical knowledge is not an easy problem (how ironic). That is why the "learn as you go" method is preferred, since you will have experienced computer scientists at your disposal to guide you. Your advisor and tutors can help you determine what you really need to know and when your mathematical studies get in the way of the computer science ones.

Improve this answer
$\endgroup$
2
$\begingroup$

Although a full answer may require knowing more about your situation and what you plan to research, you can't go too far wrong with some of the standard resources. Fundamentally you need to be comfortable with discrete maths which is commonly said to include logic, discrete probability, combinatorics and so on. I would start by making sure you know the material in http://courses.csail.mit.edu/6.042/fall10/mcs-ftl.pdf . Once you have mastered that you are in a position to specialise a little and there is a world of online lecture notes you can use to either learn from directly or to inform your choice of course at Cambridge. Do you already know the material from http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/ and have you looked at advanced course such as http://courses.csail.mit.edu/6.854/current/ or http://courses.csail.mit.edu/6.851/spring10/lec.html? You could of course study computational complexity http://www.cs.princeton.edu/theory/complexity/ if you haven't already or coding theory http://people.csail.mit.edu/madhu/FT02/ or learn some algorithmic game theory http://people.csail.mit.edu/costis/6896sp10/. The options are endless.

If, on a more mundane note, you just want to take straight maths courses I would recommend anything in linear algebra, discrete probability, combinatorics, graph theory and group theory/fields and rings. Oh and please complain that they don't have a decent computational complexity course in part III yet :)

Improve this answer
$\endgroup$