MATH 595: Longest Common Subsequences

This is a graduate research seminar, so there will not be any official homeworks nor assessments. This page will simply be used for posting relevant materials.

---

Relevant papers

• Longest common subsequences of two random sequences by Chvátal and Sankoff
• The rate of convergence of the mean length of the longest common subsequence by Alexander
• Expected length of the longest common subsequence for large alphabets by Kiwi, Loebl and Matoušek
• Improved bounds on the average length of the longest common subsequences by Lueker
• Periodic words, common subsequences and frogs by Bukh and Cox
  • code

Background reading

• Markov Chains by Norris
• Reversible Markov chains and random walks on graphs by Aldous and Fill
• The probabilistic method by Alon and Spencer
• Probability theory: The coupling method by Hollander