Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/23463
Title: | COMPUTATIONAL FRAMEWORK FOR THE GENERALIZED BERGE SORTING CONJECTURE |
Authors: | Sun, Zhuoyu |
Advisor: | Deza, Antoine |
Department: | Computing and Software |
Keywords: | Berge Sorting |
Publication Date: | Nov-2017 |
Abstract: | In 1966, Claude Berge proposed the following sorting problem. Given a string of n alternating white and black pegs, rearrange the pegs into a string consisting of all white pegs followed immediately by all black pegs (or vice versa) using only moves which take 2 adjacent pegs to 2 vacant adjacent holes. Berge's original question was generalized by considering the same sorting problem using only Berge k-moves, i.e., moves which take k adjacent pegs to k vacant adjacent holes. Let h(n,k) denote the minimum number of Berge k-moves to sort a string of n alternating white and black pegs.The generalized Berge sorting conjecture states that h(n,k) is equal to the ceiling of n/2 for any k and large enough n. We develop a computational framework to determine h(n,k) for small instances with a focus on the most computationally challenging instances; that is, the determination of (k+2,k). |
URI: | http://hdl.handle.net/11375/23463 |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
sun_zhuoyu_201708_master.pdf | 212.26 kB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.