Title page for etd-0827106-160715


[Back to Results | New Search]

URN etd-0827106-160715
Author Chiou-Ting Tseng
Author's Email Address M923040003@student.nsysu.edu.tw
Statistics This thesis had been viewed 5350 times. Download 1261 times.
Department Computer Science and Engineering
Year 2005
Semester 2
Degree Master
Type of Document
Language English
Title Finding the Longest Increasing Subsequence of Every Substring
Date of Defense 2006-07-06
Page Count 43
Keyword
  • longest increasing subsequence
  • row tower
  • substring
  • sliding window
  • Abstract Given a string S = {a1, a2, a3, ..., an}, the longest increasing subsequence (LIS) problem is to find a subsequence of the given string such that the subsequence
    is increasing and its length is maximal. In a previous result, to find the longest increasing subsequences of each sliding window with a fixed size w of a given string
    with length n can be solved in O(w log log n+OUTPUT) time, where O(w log log n+ w^2) time is taken for preprocessing and OUTPUT is the sum of all output lengths. In this thesis, we solve the problem for finding the longest increasing subsequence of every substring of S. With the straightforward implementation of the previous result, the time required for the preprocessing would be O(n^3). We modify the data structure used in the algorithm, hence the required preprocessing time is improved to O(n^2). The time required for the report stage is linear to the size of the output. In other words, our algorithm can find the LIS of every substring in O(n^2+OUTPUT) time. If the LIS's of all substrings are desired to be reported, since there are O(n^2) substrings totally in a given string with length n, our algorithm is optimal.
    Advisory Committee
  • Shi-Jinn Horng - chair
  • Yi-Hsing Chang - co-chair
  • Yue-li Wang - co-chair
  • Chia-Ping Chen - co-chair
  • Chang-Biau Yang - advisor
  • Files
  • etd-0827106-160715.pdf
  • indicate in-campus access immediately and off_campus access in a year
    Date of Submission 2006-08-27

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys