Back to search

University of North Florida. School of Computing

Sorting by Block Moves

Abstract

dc:description.abstract

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 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

Rights

dc:rights

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.unf.edu/etd/576

Chain of custody

source
Harvested from
University of North Florida
Base URL
digitalcommons.unf.edu/do/oai/
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Huang, Jici; Huang, Jici, 1989-. Sorting by Block Moves. University of North Florida. School of Computing, https://digitalcommons.unf.edu/etd/576