Wednesday, July 04, 2007

What's an advanced algorithm ?

And he's back !!!

After a rather refreshing (if overly hot) vacation in India, I'm back in town, forced to face reality, an impending move, and the beginning of semester. Yep, the summer is drawing to a close, and I haven't even stuffed my face with hot dogs yet, let alone 59.5 of them (is there something slightly deranged about ESPN covering "competitive eating" as a sport?).

Anyhow, I digress. The burning question of the day is this:
What is an advanced algorithm ?
It might not be your burning question of the day, but it certainly is mine, because I am the proud teacher of the graduate algorithms class this fall.

Some explanation is in order. At most schools, undergrads in CS take some kind of algorithms class, which for the sake of convenience we'll call the CLRS class (which is not to say that it can't be a KT class, or a DPV class, or a GT class, or....). At any rate, this is the first substantial algorithms class that the students take, and often it's the last one.

Now when you get into grad school, you often have to complete some kind of algorithms breadth requirement. In some schools, you can do this via an exam, and in others, you have to take a class. Namely, a graduate algorithms class. Note also that some students taking this class might not have taken an undergrad algorithms class (for example if they were math/physics majors)

What does one teach in such a class ? There are a number of conflicting goals here:
  • Advertising: attract new students to work with you via the class. Obviously, you'd like to test them out first a little (this is not the only way of doing this)
  • Pedagogy: there's lots of things that someone might need even if they don't do algorithms research: topics like approximations and randomization are not usually well covered in an intro algorithms class
  • Retaining mindshare: you don't want to teach graduate algorithms as a CLRS class because you'll bore all the people who took such a class. On the other hand, you zoom too far ahead, and you lose the people who come to CS from different backgrounds. And the Lord knows we're desperate nowadays for people to come to CS from different backgrounds (more on this in a later post).
This is obviously not a new problem, and there are numerous models for how to teach a graduate algorithms course, all with their own pros and cons. Some of the extreme points that define the spectrum of solutions are:
  • Teach to the top: dive straight into advanced topics; anyone who needs to catch up does so on their own time. This is probably the most appealing solution from a lecturer perspective, because it covers more interesting topics. It's also most likely to excite the few students who care. Be prepared for bumpy student evals, especially from disgruntled folks who just need a grade so that they can forget all about algorithms for the rest of their Ph.D
  • Teach to the bottom: Do a CLRS-redux, with maybe a few advanced topics thrown in at the end (NP-hardness might count as advanced). You'll bore the good ones, but you'll bring the entire class along.
A 'split-the-difference' solution of covering basic material quickly, and then jumping ahead into advanced topics, is also a possibility. Like most solutions of this kind though, it runs the risk of satisfying nobody while trying to satisfy everyone.

All of this elides the most important point though: what constitutes advanced material ? I've seen graduate students struggle with NP-hardness, but this is covered in almost any undergraduate algorithms class (or should). What about general technique classes like approximation algorithms and randomization, both of which merit classes in their own right and can only be superficially covered in any algorithms class (the same is true for geometry) ? Advanced data structures can span an entire course, and some of them are quite entertaining. Topics like FFTs, number-theoretic algorithms, (string) pattern matching, and flows also seem to fit into the purview of advanced topics, though they don't cohere as well with each other.

It seems like an advanced algorithms class (or the advanced portion of a graduate algorithms class) is a strange and ill-defined beast, defined at the mercy of the instructor (i.e ME !). This problem occurs in computational geometry as well; to use graph-theoretic parlance, the tree of topics fans out very quickly after a short path from the root, rather than having a long and well-defined trunk.

10 comments:

  1. You certainly can't teach everything, so teach what you are most well-versed in and most interested in. Thus your enthusiasm for the material will reflect in your teaching.

    On the other hand, you could use this to brush up on a topic less familiar to you that you would like to learn more about.

    As long as you find the material interesting it is a good choice.

    ReplyDelete
  2. jeez. some people read things as soon as I post them.

    as for teaching with enthusiasm, I think that although students appreciate it, it doesn't necessarily reflect in teaching evals. An interesting conundrum.

    ReplyDelete
  3. ...i'm not an algorithms person, but it seems that this is a conundrum that may be shared by many grad level instructors. (note that i really haven't thought this through, so it may actually make no sense.)

    i think a part of the reason might be something like: we *know* that sorting is important; we *know* that the concept of NP is important; we *know* that hashing (i mean the simple versions) is important; etc...

    but when it comes to more advanced topics, there will inevitably some that go on to conquer the world and some that fade into obscurity.

    it seems like maybe what you really want to teach them is to teach them how to think about problems in an algorithmic way (i.e., care about things like efficiency, care about things like bounds and gaps, care about thinking about a problem before they start coding). maybe the right way to structure an advanced algorithms course is that it's not necessarily the *algorithms* that are advanced, but the thinking that they have to do. i'm not sure how much more you can make people think about sorting, but i remember that even when i learned the nlogn lower bound on sorting, i thought this was incredible! it seems like if you can pull this off, it actually satisfies all of your requirements. (well, some students might get annoyed at having to think so much and this may reflect poorly on evals.)

    incidentally, did you see this post? what do you think?

    ReplyDelete
  4. I'm a graduate student at UNICAMP, Brazil. Every PhD student must take a course in one of algorithms, graph theory or formal languages and automata. The algorithms course is CLRS-like, NP-completeness included, and somewhat fast paced. People with a non strong CS/math background tend to struggle with these courses. For example, students with a degree in Information Systems (instead of Computer Science) might not have had good discrete math and algorithms courses.

    Some of the students that are more theory oriented tend to take these three courses and also algorithms II (string processing, number theoretic algorithms, network flows, approximation and randomized algorithms). There are also separate courses on randomized algorithms, approximation algorithms, and computational geometry.

    I think that a graduate CLRS-like course is useful for students without a good CS background. For those who have had a good undergraduate algorithms course, there are other interesting algorithms courses to take.

    ReplyDelete
  5. crypto: i think the implicit question that suresh didn't ask is "why should students who don't have background in algorithms not be required to take undergrad algorithms as catch-up?"

    ReplyDelete
  6. Two more comments:

    * Hal, I read Michael's post, and haven't yet figured out what I think of it. I'm lazy, and the idea of introducing programming exercises into a course terrifies me. I'm also a bit of a purist, and feel that students get enough opportunities to do programming (this may or may not be the case at Harvard) and don't need yet another one. However, I do see the need to connect these two "pillars" somehow.

    * I have yet to hear an academic reason why incoming grads who need an undergrad class can't take it. All the reasons so far are logistical, bureaucratic, and often come down to money issues.

    ReplyDelete
  7. Suresh! Thank goodness you're back!

    Can't help but start by commenting on comments:

    I'm lazy, and the idea of introducing programming exercises into a course terrifies me.

    Well, you're certainly honest. I suspect laziness is at least as big a reason as anything didactic for why many theorists avoid assigning programming problems...

    I'm also a bit of a purist, and feel that students get enough opportunities to do programming (this may or may not be the case at Harvard) and don't need yet another one.

    Of course students have plenty of chances to program (here and everywhere); what they probably haven't learned is why they should think algorithmically BEFORE they sit down in front of the machine and start to program. They probably haven't learned that a good algorithm can dramatically more important than running on a faster machine. And lots of other important things. And I think it's our responsibility to make that point.

    ReplyDelete
  8. I think linear programming should
    be introduced and some thing should
    be said about the big area of
    mathematical programming and optimization. CS people tend to
    ignore this whole area even though
    in practice many things are handled
    by "algorithms" from this area.

    Of course there are too many things
    to cover and I agree with some of
    the comments that the bottom line
    is to teach the process of putting
    on the algorithmic hat what ever
    material one eventually settles
    on.

    ReplyDelete
  9. Michael Mitzenmacher says:

    Suresh,

    I don't envy you the teaching problem. It is a remarkably poor setup when the "basic" graduate algorithms class is meant to cover for people who haven't learned the subject properly as an undergraduate (for whatever reason), and I do think the correct answer is that entering students who haven't had an appropriate theory background should simply be required to go back and take the undergraduate course. Or they should be expected to pick it up on their own and move on -- graduate students are supposed to be able to learn things independently, right? Alternatively, it's also fine to have a remedial graduate course that's essentially a fast moving undergraduate course, as long as everyone understands that that's what the course is, so no actual theory students show up for it.

    If you can assume that the basic undergraduate background is covered, then your department could offer slightly more specialized courses, and students could take the one that most appealed to them. Advanced algorithms seems like just too broad a category to even think about coherently. If I had to pick topics for such a course, randomization and probabilistic analysis would obviously top the list, along with other approximation algorithms, linear programming, and whatever I was doing research on that month.

    ReplyDelete
  10. in response to Michael:

    Given my druthers, I'd have entering grads take the undergrad algorithms class as the required class (or better yet, take some kind of exam). That would leave me free to teach whatever in my graduate algorithms class.

    The reasons why this can't happen are messy, and have nothing to do with pedagogy per se. Not something I can change in my current position. Given that, the next best alternative is something like what Hal and Chandra also suggest: a course that emphasizes algorithmic thinking (researcher style), since almost any CS researcher will find the tools of formalization, abstraction, and algorithm design useful.

    ReplyDelete

Disqus for The Geomblog