On average and highest number of flips in pancake sorting

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On average and highest number of flips in pancake sorting

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On average and highest number of flips in pancake sorting

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GD201%2F09%2FH057" target="_blank" >GD201/09/H057: Res Informatica</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2011

Kód důvěrnosti údajů

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

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

412

Číslo periodika v rámci svazku

8

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

13

Strana od-do

822-834

Kód UT WoS článku

000287295000018

EID výsledku v databázi Scopus

—