First moment problem in longest common subsequences
Loading...
Date
2018.
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2018.
Abstract
In this thesis, we investigate the properties of the longest common subsequences in random words, examine upper and lower bounds for the expected value of the longest common subsequences in this setting, and discuss the behavior of the asymptotic order of the longest common subsequences's variance. Besides this, we also study the relationship between longest common subsequences and longest increasing subsequences in random permutations and discuss some properties of the matrix L (n) that is generated by the length of the longest common subsequences of permutations. Our aim is to understand the details of the theory of the longest common subsequences whose study begun in 1970's, draw attention to the progress about the longest common subsequences in the recent studies, and state some open problems about the subject