Back to results

University of North Florida. School of Computing

Implementation of algorithms for sorting by strip swaps using alternating cycle graphs

Abstract

dc:description.abstract

Challenges in computational biology, such as genome rearrangement, and applications in optical character recognition, like zoning techniques, often require solving optimization problems. These involve reordering scrambled sequences of numbers into a sequential arrangement known as the identity permutation. Rearranging any given permutation into the identity permutation with the minimum number of specific operations related to strips gives rise to various combinatorial optimization scenarios. Operations such as strip moves, transpositions, reversals, and block interchanges have been extensively researched. This thesis builds on the foundational work of Roy et al., targeting the refinement of their cycle graph algorithm for sorting by strip swaps. The main contribution of this thesis is the development of a solution that successfully handles the various scenarios of sorting by strip swaps on which the cycle graph algorithm of Roy et al. did not succeed. In order to evaluate our suggested approaches, a brute-force algorithm has been developed to determine the optimal solution and to verify that the cycle graph algorithm is indeed a 2-approximation algorithm. Our experimentation has been confined to small-sized permutations only due to limitations on the resources.

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
  • Bhakharia, Harsh S.
  • Bhakharia, Harsh, 2000-
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 × 9

Rights

dc:rights

Identifiers

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

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

Bhakharia, Harsh S.; Bhakharia, Harsh, 2000-. Implementation of algorithms for sorting by strip swaps using alternating cycle graphs. University of North Florida. School of Computing, https://digitalcommons.unf.edu/etd/1286