Thursday, January 31, 2008

Algorithms for Newbies: Static or Dynamic?

A talk I just went too (by Lynn Stein) raised the following question for me.

While I have some strange ideas about how an algorithms class should be taught (like students should do some programming in an algorithms class), in most ways my algorithms class is quite traditional. Roughly, my class looks quite similar in the path it takes to Algorithm Design by Kleinberg/Tardos (or the corresponding subsections of the standard Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein). And specifically, I teach primarily what we'd call "static" algorithms; there's an input, a desired output, and the algorithm is the recipe.

These days, many of us do research in and arguably most commercial products use "dynamic" algorithms; that is, they're processes that are always on, reacting to the environment around them. (Your cell phone, for example, might be considered a dynamic algorithm device; so would a robot vehicle. If you like, you can think of "dynamic algorithms" as roughly being closely tied to "distributed systems".) My course is not geared to teach or have student explore dynamic algorithms, although they get brief mention. Lynn seemed to be suggesting that dynamic algorithms and programs should be taught before static algorithms and programs. It is, after all, the paradigm students are most familiar with, and arguably more interesting to them.

This doesn't sit right with me. In my mind, it's partly a "walk before you can run" issue -- you could teach a lot of calculus without teaching trig, but it doesn't seem the right way to go. Although that's not really quite the right analogy; I can see that the issues in dynamic algorithms/distributed systems -- like communication, and responding to asynchronous incoming signals -- are often quite different than for static algorithms, so much so that in many case you don't have to know your standard static algorithms to write a dynamic one. I think it's more that I think that to do anything that I would consider technically interesting you need to know static algorithms first. That is, sure you can probably teach people to write an interactive Internet chat program pretty easily, and they'd learn a lot by doing it, but that's like the task 20 years ago of writing a checkbook program, just harder because of issues raised by the interactivity. To do really interesting things with dynamic algorithms, my bias is you need good static algorithms behind it. Like Google mail's search features, or Amazon's recommendation feature, or other stuff. (Or at least, in many cases, you should understand the static version of an algorithm before trying to understand the dynamic version of it.)

So now I'm wondering if I'm just old-fashioned. What do you all think?

9 comments:

Anonymous said...

(1) I agree that implementation of an algorithm is very important. There are often many details to work through during implementation that make the students really "learn" and appreciate the algorithm.

Often times, there's a disconnect between those who do "theory" and those that implement. I've heard this from a NASA engineer: "Just because some clown told you Turbo codes are good, doesn't mean you should use it." He was very bitter because in th past, he had to deal with many "clowns" who couldn't see the difficulties during implementation.

(2) I would imagine that if people thought hard enough (say, put in the same effort they do to a STOC/FOCS problem), they could think of some very innovative ways to teach both static and dynamic algorithms.... but I digress...

Anonymous said...

"Dynamic" algorithms could perhaps also include on-line algorithms, and issues like competitive ratio; they don't have to be distributed.

When we move to distributed algorithms, the business of proving desirable properties becomes less dominated by identification of bounds on their runtime. In the context of teaching, maybe this is a good thing (arguably the proofs are more diverse and interesting.)

Anonymous said...

My guess is that the teaching of only
static algorithms in algorithms courses will look old fashioned at some point in the not too distant future. At the very least, it seems that standard texts such as CLRS should at least have one chapter devoted dynamic/online/streaming/etc algorithms.

Mikhail said...

To me, distributed algorithms are very different from "classic" ones. Designing a DA is much like solving a puzzle about three wise men. In fact, you design a FSA that, being deployed on network nodes, will strive towards some "common aim".

So, static and dynamic algorithms can be studied in any order.

Anonymous said...

A sequence of insertions, deletions and lookups in a binary search tree are a dynamic algorithm, aren't they? So are on-line algorithms such as paging.

Michael Mitzenmacher said...

Anon 5 : I think we hint at "dynamic" algorithms when we consider data structures responding to a sequence of operations [though usually that can be thought of as an offline finite sequence of operations -- or an input], and hint more strongly when we consider online algorithms. Though somehow the "always on" aspect isn't quite captured. (Also, while I do some approximation algorithms in my undergrad class, I don't really cover on-line algorithms in any detail. Not enough time, and some unwillingness on my part to try to justify why the competitive ratio would be the "right" thing to aim for algorithmically...)

Your Correspondent said...

The "Static" algorithms are too important to be skipped over. But the students need to understand what dynamic algorithms actually are.

Ideally, you would find 2 simple dynamic algorithms to teach. It wouldn't take much time and 2 is the beginning of seeing a pattern.

I don't actually know if 2 such algorithms exist that are worth teaching, though.

Jelani Nelson said...

Perhaps we've reached a level of specialization where any course entitled "Introduction to Algorithms" is too broadly titled. For example, how often do you see a course called "Introduction to Math"? Now we have separate intro courses for algebra, analysis, etc. Maybe the same should be true for algorithms. Commonly used concepts, e.g. "big-Oh" notation and recurrences, could be taught beforehand in a separate "Math for algorithmists" course (maybe not the best name), and then there could be separate intro courses for different algorithm subfields.

Anonymous said...

Commonly used concepts, e.g. "big-Oh" notation and recurrences, could be taught beforehand...

This sort of material is very often taught in a "Discrete Math" course that is a prerequisite of algorithms.

Some schools may also have a course on Data Structures before a course on algorithms, or a two-semester algorithms sequence.