We provide an introduction to the longest common subsequence (LCS) problem and the Chvátal-Sankoff constants, and obtain new results related to these areas. By improving upon a previous lower-bound algorithm, we obtain state-of-the-art lower bounds for all but one Chvátal-Sankoff constant, with particular attention paid to the Chvátal-Sankoff for two binary strings. Accompanying this, we also prove various properties describing the effect of modifying a pair of strings on their longest common subsequence. We additionally create a web application with interactive visualizations designed to allow users to learn and explore these properties and other facets of the LCS problem.

• This report represents the work of one or more WPI undergraduate students submitted to the faculty as evidence of completion of a degree requirement. WPI routinely publishes these reports on its website without editorial or peer review.

Creator

• Salls, Andrew
• Soiffer, Duncan
• Miller, Chase

Publisher

• Worcester Polytechnic Institute

Identifier

• E-project-042524-100314
• 121646

Keyword

• String Algorithms
• Statistics
• Chvátal-Sankoff Constants
• Dynamic Programming
• Longest Common Subsequence

Advisor

• Reichman, Daniel
• Sarkozy, Gabor N

Year

• 2024

Date created

• 2024-04-25

Resource type

• Major Qualifying Project

Major

• Computer Science

Source

• E-project-042524-100314

Rights statement

• In Copyright