University of North Florida. School of Computing
Sorting by Strip Moves and Strip Swaps
Abstract
dc:description.abstractGenome 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- Thesis; University of North Florida; UNF; Dissertations
- Academic -- UNF -- Master of Science in Computer and Information Sciences; Dissertations
- Academic -- UNF -- Computing; sorting; strip moves; strip swaps; greedy; closest consecutive pair; block sorting
- Other Computer Engineering
- Sorting (Electronic computers) -- Testing; Approximation algorithms -- Testing; Combinatorial optimization -- Testing; Arbitrary constants -- Testing; Permutations -- Testing; Electronic data processing -- Testing
Rights
dc:rightsIdentifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.unf.edu/etd/982