Title page for etd-0108115-142017


[Back to Results | New Search]

URN etd-0108115-142017
Author Cing-Yao Chen
Author's Email Address No Public.
Statistics This thesis had been viewed 5350 times. Download 324 times.
Department Computer Science and Engineering
Year 2014
Semester 1
Degree Master
Type of Document
Language English
Title Efficient Algorithms for the Common Multiset Interval Problem
Date of Defense 2015-01-26
Page Count 47
Keyword
  • Assembly Code
  • CI
  • LCS
  • CPE
  • BKS
  • CMI
  • Abstract For two sequences A = a1a2a3 … am and B = b1b2b3 … cn, a multiset interval ∆(A, i, j) = [ax | i ≤ x ≤ j], and a common multisets interval (CMI) is ∆(A, iA, jA) = ∆(B, iB, jB) for some $iA, jA, iB, jB. 1 ≤ iA ≤ jA ≤ m and 1 ≤ iB ≤ jB ≤ n, which is a multiset that appears in both sequences.
      Previously, researchers have proposed algorithms for finding the common set interval of permutations and sequences. In this thesis, we propose two algorithms to find common multiset intervals of two sequences. The first is the occurrence counting algorithm, which counts the occurrences of the characters in all intervals of the two input sequences and calculate the difference of character occurrences. Its time complexity is O(n3) time, where n denotes the length of the input sequences. The second is the hash key algorithm, which use the product of prime numbers and the modulo operation to build a hash table for quick search. The time complexity of the second algorithm is O(n2 + Gn + qn) or O(n2|Σ| + G|Σ|+ q|Σ|), where G denotes the number of answers and q denotes the number of error collisions. In our experiments, we use C/C++ source codes in CPE (Collegiate Programming Examination of Taiwan) as the data set for classification. The experimental results show that the BKS (behavior knowledge space) method with the combination of the LCS (longest common subsequence) and CMI classifiers can obtain better accuracy than the two methods alone.
    Advisory Committee
  • Chungnan Lee - chair
  • Hsing-Yen Ann - co-chair
  • Yung-Hsing Peng - co-chair
  • Chang-Biau Yang - advisor
  • Files
  • etd-0108115-142017.pdf
  • Indicate in-campus at 0 year and off-campus access at 1 year.
    Date of Submission 2015-02-08

    [Back to Results | New Search]


    Browse | Search All Available ETDs

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