Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
UNF Graduate Theses and Dissertations
Academic -- UNF -- Computing; Block Sorting; Approximation Algorithms; Run Merging
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Sorting By Block Moves, Jici Huang
Sorting By Block Moves, Jici Huang
UNF Graduate Theses and Dissertations
The 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 …