ICS 269, Fall 1999: Theory Seminar

29 October 1999:
The longest common subsequence of two strings A and B is the longest string which is a subsequence of both A and B. We discuss the expected length of the longest common subsequence when A and B are random binary strings of length n. It has long been known that for large n this is asymptotic to g n, where g is some constant. We discuss techniques for obtaining upper and lower bounds on the value of g.