Student Work

Exploring Longest Common Subsequences and the Chvátal-Sankoff Constants

Pubblico Deposited

Contenuto scaricabile

open in viewer

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
Publisher
Identifier
  • E-project-042524-100314
  • 121646
Parola chiave
Advisor
Year
  • 2024
Date created
  • 2024-04-25
Resource type
Major
Source
  • E-project-042524-100314
Rights statement

Relazioni

In Collection:

Articoli

Elementi

Permanent link to this page: https://digital.wpi.edu/show/wh246x39h