University of North Florida. School of Computing
Implementation of algorithms for sorting by strip swaps using alternating cycle graphs
Abstract
dc:description.abstractChallenges 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- Thesis
- University of North Florida
- UNF
- Dissertations, Academic -- UNF -- Master of Science in Computer and Information Sciences
- Dissertations, Academic -- UNF -- Computing
- strip swaps
- Alternating cycle graph
- Computer Engineering
- Approximation algorithms -- Testing; Sorting (Electronic computers) -- 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/1286