FOR THE SAKE OF PANCAKE!

It was 12 in the afternoon and I was badly hungry. "One more hour for lunch break!”, I thought. One of the greatest teachers I strongly admire, started off with his lecture on some of the concepts of theoretical computer science. As expected we all were drowned in the world of his logics and were enjoying his lecture. It was as though my hypothalamus ceased to function and I forgot I was hungry. After a while he presented in front of us, a problem, that reminded me of my hunger once again!

It was about the yummiest south Indian food, dosa. The problem goes like this. A chef in some famous south Indian diner is preparing lots and lots of dosas, all of different sizes and is piling them up. But before delivering them, he wants to rearrange them such that the smallest one is on the top of the stack and the largest at the bottom. He has only one spatula, and he can place it somewhere in the stack, lifting the portion above the spatula, flipping it, and then placing it back on the stack. If there are $n$ dosas, what is the minimum number of flips performed by the chef to rearrange the stack? This, is the Indian version of the famous pancake problem.

Jacob Goodman, under the name Harry Dweighter, proposed the pancake problem in the year 1975. This scenario of a chef rearranging the pancakes was proposed by him, keeping in mind the minimum number of flips needed to obtain a correctly arranged stack of pancakes. One might wonder about the need to formulate such problem. It has many applications in the field of genetics, in sorting out the genome sequence.

The simplest solution to this problem requires $2n-2$ flips for $n$ pancakes. This can be explained with an example. The chef can place his spatula below the largest pancake, flip it, and place it back on the stack to obtain a newly arranged stack. He can then place his spatula below the second largest pancake and follow the same procedure for all the $n-1$ pancakes, because the last one left will be the smallest and it is evident that it will be on the top. Hence no flip is required for the smallest. From the above argument you can easily make out that each pancake is associated with two flips.

$2(n-1)+ 0= 2n-2$

The $0$ in the above equation indicates the number of flips for $n=1$.For remaining $n-1$ pancakes, the number of flips should be $2(n-1)$ flips, i.e $2n-2$ flips.

The above upper bound can be further reduced to $2n-3$. Consider you have only 2 pancakes with you. Now only one flip is required to re-arrange it. If there are $n$ pancakes, then apply the procedure mentioned above for $n-2$ pancakes and this will fetch you:

$2(n-2)+1=2n-3$ flips.

Here $+1$ is for the $n=2$ condition and the remaining $n-2$ pancakes, each being associated with 2 flips will amount to $2(n-2)$ flips, giving a total of $2n-3$ flips.

It occurred to some that the above algorithm can be improved and some attempts were made in the same.

In the year 1979, an algorithm was proposed by, the very famous Bill Gates of Microsoft fame ( perhaps the only technical paper that Gates came up with!) and Christos.H.Papadimitriou. The different sorting algorithm had lower and upper bounds to be $\frac{5n+5}{3}$ and $\frac{17n}{16}$ respectively.

Terminologies required to understand Gates’ and Papadimitriou’s algorithm:

$\sigma$: It is the permutation of numbers ranging from $1$ to $n$, you are provided with. The numbers in this permutation indeed signify the size of the pancakes. Larger the number greater is the size of the pancake.

For example, $\sigma$=( 5 1 4 2 3) denotes the arrangement of pancakes such that the largest i.e, number 5 is on the top of the stack with the third largest at the bottom and so on. The aim is to re-arrange it such that you get the identity permutation, which is $i$=( 1 2 3 4 5).

$S_n$ is the set of all permutations of numbers ranging from $1$ to $n$.

Adjacency: For a given stack of pancakes, an adjacency is an adjacent pair of pancakes in the stack such that there is no such pancake whose size is intermediate between the two.If the largest pancake is at the bottom this also counts as one extra adjacency.

For example if $\sigma$=( 2 5 3 7 6 1 4), (7,6) is an adjacency. Because they are adjacent to each other in the given $\sigma$ and as well as there are no pancakes of size in between 7 and 6.

Consecutive: If two pancakes are consecutive to each other in the identity permutation, then they are said to be consecutive.

For example: Given $\sigma$=( 3 5 1 2 4) : 1 is consecutive to 2, 2 is consecutive to 3, 3 is consecutive to 4, 4 is consecutive to 5, 5 is consecutive to 1.

A block: Sticking with the definition in the paper a block is a maximum length sublist $x=\sigma_i \sigma_{i+1}{.......}\sigma_{j-1} \sigma_j=y$ such that there is an adjacency between $\sigma_p$ and $\sigma_{p+1}$ for all $i\leq p \leq j$.

End points: The initial and final elements of the block are called end points.

Singleton: An element that does not belong to any block is called as a singleton.

For example consider $\sigma$=( 3 4 5 1 6 7 2):

In the above permutation:

1. (3 4 5) is a block since the consecutive elements form an adjacency and so are ( 6 7). They form an adjacency as well as a block since its evident that every adjacency is also a block.


2. 1 and 2 are singletons since they do not belong to any block.

A table has been given in the paper whose link is given below:
You can refer the paper for many cases which are used below
http://etd.ohiolink.edu/send-pdf.cgi/Armstrong%20Alyssa.pdf?wuhonors1242223287

In the following example $B$ denotes the initial element of the permutation, i.e., the leftmost element.The separation between the blocks and singletons is marked by the symbol $\__$.If B begins with any block then we denote it as $B\simC$. We do the same thing for the right most element of the initial block and denote the element consecutive to it as $D$. Remaining all elements between blocks and singletons are denoted by $\__$.

Example: let $\sigma=(3 4 1 5 2)$:

• B=3


• ( 3 4) is a block denoted by B$\sim$C.


• A=2, since the element consecutive to 3 ( other than 4 which is already in the block) is 2.


• D=5, since 4 is the rightmost element of the block and 5 is consecutive to 4 which is also a singleton.


• So we denote this permutation as B$\sim$C$\__$D$\__$A.

Having these definitions in mind, we can proceed with the following example:

Let $\sigma \in S_8$, i.e., $\sigma=(2 3 4 7 6 1 5)$ and the identity permutation $i_8=( 1 2 3 4 5 6 7 8)$:

According to Gates' algorithm:

• Begins with block ( 2 3 4) and 2 is consecutive to 1 and is also a singleton.Hence, by case 4,we have
  B=2, A=1
  So, we reverse at 6 to get ( 6 7 4 3 2 1 5).


• Now, the permutation begins with the block ( 6 7 ). 6 is consecutive to 5 which is a singleton. So, by case 4,:
  B=6, A=5:
  We reverse at 1 to get ( 1 2 3 4 7 6 5).


• Now, the initial block is ( 1 2 3 4) and 1 is consecutive to 7 of the block ( 7 6 5). By case 5 of the table,
  B=1, A=7
  So, we reverse at 4 to get ( 4 3 2 1 7 6 5).


• Now, we got a single block, in such cases we go for the trivial algorithm,
  The largest is 7, so reverse at 7 to get ( 7 1 2 3 4 6 5) and further reverse at 5 to get ( 5 6 4 3 2 1 7).


• Again we have got a single block, apply the trivial algorithm,
  Reverse at 6 to get ( 6 5 4 3 2 1 7) and at 1 to get (1 2 3 4 5 6 7).

Thus, we got the identity permutation after 7 reversals.

Using this algorithm Gates and Papdimitriou showed that the lower bound for the algorithm is 1.667. In 1997, Mohammad H. Heydari and I. Hal Sudborough improved the lower bound to $\frac{15n}{14}$ and computed the pancake numbers up to 13.

The above image shows the team of UT Dallas computer science students and their faculty adviser who improved upon a longstanding solution to the pancake problem.

An interesting variant of the problem, proposed by Gates and Papadimitriou, concerns pancakes that are burnt on one side. Here the pancakes must be sorted with the burnt side down.

Applications:

1. The pancake problem is relevant to the construction of networks of parallel processors, in which pancake sorting can provide an effective routing algorithm between the processors.


2. 
   

   Analysis of Genomes: In evolutionary processes, changes in DNA sequences can cause a new species to get separated from an existing one, resulting in diversified life-forms. If you want to reconstruct such changes, you can look into genome sequences of related species. An event where a certain sequence is deleted and is replaced with its reverse sequence can be looked for. Thus analyzing the transformation from one species to the other is analogous to the problem of finding the shortest series of reversals.