Thursday, April 22, 2010

Random Links for the Day

FemaleScienceProfessor tells an Evil Reviewer story.

The CRA blog tells us that DARPA is back, in terms of funding university research.  Ed Lazowska has related posts here and here at the CCC blog.

If you think deciding authorship is complicated normally, what about for Polymath projects?

For my last lecture in Algorithms and Data Structures, I try to show something that I, at least, think is amazing:  maximal palindromes can be found in linear time.   (pp. 197-198 of Gusfield's book Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology). 

But this year, I didn't miss enough lectures during the semester.  So I still have one more lecture -- a good excuse to finally add a brief discussion of Bubblesearch (randomized greedy) and maybe also Human-Guided Tabu Search into the class. 

3 comments:

Geoff Knauth said...

Looks like an interesting book, thanks for the tip. We had a colloquium speaker today on computational biology. This is very useful. Is this book the best general reference to date for the subject? I'm puzzled/amused so much work is still done in Perl, but I gather it's because searches are mostly ad hoc.

Anonymous said...

You could also take the opportunity to, you know, not talk about your own one-off papers but instead lecture on interesting/cool stuff done by other people. How about locally-sensitive hashing?

Michael Mitzenmacher said...

Anon #2: LSH is an interesting topic, but doesn't really fit naturally in the class -- particularly for a last 1/2-lecture or so.

Since I've often said in this blog (and, indeed, probably several other blogs) that I think "heuristic methods" are under-discussed in algorithms classes, it makes sense to spend the bit of time on them (especially as it's the subject of the programming assignment they're turning in that day). Since I've often said that BubbleSearch should be taught in every undergrad algorithms class, as it is a very simple and useful generalization for greedy algorithms, it makes sense I'd teach that. Finally, since I don't generally talk about "things I do" in class -- the closest is the lecture I spend on document similarity, following the approach of Andrei Broder, which does use min-wise independent permutations, but I gloss that over -- I think giving them context of "things their professor(s) do" is a reasonable thing.

There, that seems like a nice, professional response to your comment -- even though the tone of your first sentence makes you seem like something of a jerk.