Note: I'm going to try to put a bunch of links (to mostly Wikipedia) pages into this post. Hopefully this will become the norm and those of me (haha) who don't know some of the terms/problems can look them up easier.

I've encountered yet another problem which boils down to being essentially the Traveling Salesman Problem . Someone really ought to find a nice, beautiful, algorithm for solving that thing in polynomial time ;)

Basically, I was reading about the Smith-Waterman algorithm when I noticed its similarity to Levenshtein distance . In fact, on the Wikipedia page for Levenshtein distance it mentions that it can be "further generalized by DNA sequence alignment algorithms such as the Smith–Waterman algorithm..." Awesome! So, I set off to implement the Smith-Waterman algorithm and play around with Levenshtein distance in D. I knew that D had a (correct) Levenshtein distance function from Andrei Alexandrescu's talk about D -- please excuse me if that link is incorrect, I will have to check it later, if I can remember ;) . The first thing I thought of was to simply output the outcome of both algorithms on each consecutive pair of arguments passed to the program, for something to do. This led me to think, "I wonder if there is a quick way to figure out the way to minimize the total Levenshtein distance between consecutive arguments." I quickly realized this could be expressed as an n-degree graph in which edge lengths are edit distances and we wish to find the minimum length Hamiltonian path. After a little more thought, I noticed the striking similarity to the TSP. If we could easily find the solution to the TSP, we could simply delete the longest edge to obtain the shortest Hamiltonian path (unproven...).

In other news, I am still working on reading the original paper for Eppstein's algortithm (no wiki link :(). I also still have the paper for the lazy version, and have obtained the reference paper for Frederickson's algorithm for finding the smallest k elements in a heap ordered tree. Ooh, I wish I had more time! :D