<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-250

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

Vlado Dancik and M.S. Paterson, Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences. (October 1, 1993).

Abstract

Let f(n) be the expected length of a longest common subsequence of two random binary sequences of length n. It is known that the limit c=lim{n->oo}f(n)/n exists. Improved upper bounds for c are given using a new method.

<%@ include file="cited.html" %>

Vlado Dancik and M.S. Paterson, "Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences", Random Structures and Algorithms 4(6) pp. 449-458 (1995)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>