Back to search

University of North Florida. School of Computing

Sorting by Strip Moves and Strip Swaps

Abstract

dc:description.abstract

Genome rearrangement problems in computational biology [19, 29, 27] and zoning algorithms in optical character recognition [14, 4] have been modeled as combinatorial optimization problems related to the familiar problem of sorting, namely transforming arbitrary permutations to the identity permutation. The term permutation is used for an arbitrary arrangement of the integers 1, 2,···, n, and the term identity permutation for the arrangement of 1, 2,···, n in increasing order. When a permutation is viewed as the string of integers from 1 through n, any substring in it that is also a substring in the identity permutation will be called a strip. The objective in the combinatorial optimization problems arising from the applications is to obtain the identity permutation from an arbitrary permutation in the least number of a particular chosen strip operation. Among the strip operations which have been investigated thus far in the literature are strip moves, transpositions, reversals, and block interchanges [16, 2, 25, 11, 34]. However, it is important to note that most of the existing research on sorting by strip operations has been focused on obtaining hardness results or designing approximation algorithms, with little work carried out thus far on the implementation of the proposed approximation algorithms. This research starts with implementing two existing algorithms [5, 34] and as the main contributions, provides two new algorithms for sorting by strip swaps: 1) A greedy algorithm in which each strip swap reduces the number of strips the most, and puts maximum strips in their correct positions; 2) Another algorithm that uses the strategy of bringing closest consecutive pairs together called the closest consecutive pair (CCP) algorithm. The approximation ratios for the implemented algorithms are also experimentally estimated.

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
Fall

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Rao, Chandrika Pandurang
  • Rao, Chandrika, 1985-
Advisors dc:contributor.advisor
  • Asaithambi, Asai
  • Roy, Swapnoneel
  • Liu, Xudong
Contributors dc:contributor
  • Dr. Asai Asaithambi
  • Dr. Swapnoneel Roy
  • Dr. Xudong Liu

Subjects

dc:subject × 5

Rights

dc:rights

Identifiers

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

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

Rao, Chandrika Pandurang; Rao, Chandrika, 1985-. Sorting by Strip Moves and Strip Swaps. University of North Florida. School of Computing, https://digitalcommons.unf.edu/etd/982