On average and highest number of flips in pancake sorting

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10100845" target="_blank" >RIV/00216208:11320/11:10100845 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.tcs.2010.11.028" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2010.11.028</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2010.11.028" target="_blank" >10.1016/j.tcs.2010.11.028</a>

Result language
angličtina
Original language name
On average and highest number of flips in pancake sorting
Original language description
We are given a stack of pancakes of different sizes and the only allowed operation is to take several pancakes from the top and flip them. The unburnt version requires the pancakes to be sorted by their sizes at the end, while in the burnt version they additionally need to be oriented burnt-side down. We study the largest value of the number of flips needed to sort a stack of n pancakes, both in the unburnt version (f(n)) and in the burnt version (g(n)). We present exact values of f(n) up to n=19 and ofg(n) up to n=17 and disprove a conjecture of Cohen and Blum by showing that the burnt stack -I(15) is not the hardest to sort for n = 15. We also show that sorting a random stack of n unburnt pancakes can be done with at most 17n/12 + O(1) flips on average. The average number of flips of the optimal algorithm for sorting stacks of n burnt pancakes is shown to be between n + Omega(n/log n) and 7n/4 + O(1). We slightly increase the lower bound on g(n) to (3n + 3)/2.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
<a href="/en/project/GD201%2F09%2FH057" target="_blank" >GD201/09/H057: Res Informatica</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)