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). / Thesis / Master of Applied Science (MASc)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/23463 |
| Date | 11 1900 |
| Creators | Sun, Zhuoyu |
| Contributors | Deza, Antoine, Computing and Software |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0016 seconds