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.