What theory should every non-theory Ph.D. student know?

I’ve survived my first week of teaching graduate algorithms and data structures. “Survived” really isn’t the right word. I’ve had a lot of fun and the students in the class are bright and interactive, which makes a 50 minute lecture go by in a flash.

Since the time is going by so quickly, I realize the need to consider more systematically what should be taught in this course. As you might know, I am the only algorithms/TCS person in the department (who isn’t emeritus) and so I will likely be able to quite easily affect the graduate curriculum.  I’m impressed by the amount of theory that the CS Ph.D. students are required to take here (at least in comparison to Brown, a theory-heavy school).  Each student must take the (10-week long) courses called “Algorithms and Data Structures” and “Theory of Computation and Formal Languages”.  Beyond that, there are several other optional algorithms and complexity courses offered every second year.

There has been some discussion on My Biased Coin on what every theory Ph.D. student should know. My question is: given 20 weeks of class time (three 50 minute lectures a week), what topics in TCS should every CS Ph.D. student know?

Print Friendly, PDF & Email

6 thoughts on “What theory should every non-theory Ph.D. student know?

  1. D. Eppstein

    Our basic algorithms-for-non-theorists graduate class mostly covers graph algorithms, dynamic programming, linear programming, approximation, and NP-completeness. I think the specific problems we cover are not as important as the emphasis on reduction: taking the problem you are given (from e.g. some more applied area of CS) and massaging it into a form that can be solved using one of the standard algorithms from CS theory. The same idea of reduction leads naturally to the theory of NP-completeness.

    We also have a graduate data structures course that’s taken instead of the one above by a lot of non-theorists in more technical areas.

    1. Glencora Post author

      To what detail do you teach linear programming? Do you actually teach methods for solving an LP or focus on the modelling part and just make them aware of simplex and ellipsoid?

  2. Paul Beame

    It’s a bit tough to answer. The kind of course that David describes certainly makes sense but not all non-theory students have the same needs. Every AI PhD student ought to know about PSPACE-completeness. Every Systems PhD student should know about randomized algorithms for load balancing. It isn’t clear that either needs to know about the other’s topic.

  3. Jeremy LeJyBy

    The undergrad theory courses I taught in 3 different universities had roughly the same structure:
    – First year, a single course:
    * basic data structures and algorithms in comparison
    model [Dictionary,priority queues,sorting];
    – Second year, two courses:
    * advanced data structures, algorithms and models [Randomized/Online/Approximation/Parallel algorithms, hierarchical memory, pagination]
    * Calculability [from Automata to Turing Machines, going through NP-hardness and the polynomial hierarchy]

    The structure is not necessarily ideal, they are similar because hacked from the same book or from each other.

    A personal addition which I think important for theory courses to students who will not necessarily do theory, is to insist that worst-case comparison model is one simplification valid for many applications, but that there are many other “simplifications” available, some of which are more valuable for some applications (online, memory hierarchy, space, but also energy consumption and others).

  4. JeffE

    The graduate-algorithms-for-everyone course at UIUC is pretty close to what David describes, plus some randomized algorithms. I always teach the simplex method (in its geometric “drop the marble” formulation. No tableaux!) And we do NP-completeness *first* to (try to) drive the reduction point home early.

  5. hpux735

    Paul Beame brings up a good point. As someone who is more concerned with applied computer science, I found formal languages painful and useless. I’m currently taking Error Correcting Codes (and sat in a couple lectures from Information Theory). I’m excited about the idea of quantifying the information content in a system, and the capacity of a channel to transmit that information. I think that is as fundamental as any other theory course, but it is roundly ignored.

Comments are closed.