My undergraduate algorithms class covered longest common subsequences last week, and I had time at the end of one of the lectures to survey some of the more advanced developments in this topic. I mentioned my thesis work on edit distance with gap costs, and UCI professor Dan Hirschberg's work on reducing the space complexity of the problem, but neglected to mention retired UCI professor George Lueker's work on analyzing the LCS of random strings. To atone for this omission, I've made a new Wikipedia article.

#LongestCommonSubsequence   #DynamicProgramming   #ProbabililtyTheory