Abstract
dc:description.abstractThe research in this thesis is focused on the problem of Block Sorting, which has applications in Computational Biology and in Optical Character Recognition (OCR). A block in a permutation is a maximal sequence of consecutive elements that are also consecutive in the identity permutation. BLOCK SORTING is the process of transforming an arbitrary permutation to the identity permutation through a sequence of block moves. Given an arbitrary permutation π and an integer m, the Block Sorting Problem, or the problem of deciding whether the transformation can be accomplished in at most m block moves has been shown to be NP-hard. After being known to be 3-approximable for over a decade, block sorting has been researched extensively and now there are several 2-approximation algorithms for its solution. This work introduces new structures on a permutation, which are called runs and ordered pairs, and are used to develop two new approximation algorithms. Both the new algorithms are 2-approximation algorithms, yielding the approximation ratio equal to the current best. This work also includes an analysis of both the new algorithms showing they are 2-approximation algorithms.
Degree
thesis:*- Name thesis:degree_name
- Master of Science in Computer and Information Sciences (MS)
- Discipline thesis:degree_discipline
- Computing
- Grantor
- University of North Florida. School of Computing
- Date dc:date.issued
- Summer
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Huang, Jici
- Huang, Jici, 1989-
- Advisors dc:contributor.advisor
-
- Roy, Swapnoneel
- Chuan, Ching-Hua
- Klostermeyer, William F.
- Contributors dc:contributor
-
- Dr. Swapnoneel Roy
- Dr. Ching-Hua Chuan
- Dr. William F. Klostermeyer
Subjects
dc:subject × 5- Thesis; University of North Florida; UNF; Dissertations
- Academic -- UNF -- Master of Science in Computer and Information Sciences; Dissertations
- Academic -- UNF -- Computing; Block Sorting; Approximation Algorithms; Run Merging
- Theory and Algorithms
- Blocks (Group theory) -- Testing; Approximation algorithms; Permutations
Rights
dc:rightsIdentifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.unf.edu/etd/576