A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem.

The previous best solution, which stood for more than 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established.

On the surface, the pancake problem seems to be of purely theoretical interest: Using the fewest flips, how do you re-order a stack of flapjacks, all of different sizes, so they are arranged from largest on the bottom to smallest on top?

But interest in the pancake problem is more than just theoretical (or a case of trying to top Bill Gates). One current proposal for bolstering computing power calls for configuring processors in a so-called pancake network, and the problem of computing the minimum number of steps to sort pancakes is equivalent to computing the shortest path between any two processors in this network.

“So our paper gives a way to compute a shorter route in such a network,” said Dr. Hal Sudborough, the Founders Professor for Engineering and Computer Science at the Erik Jonsson School of Engineering and Computer Science at UT Dallas.

“This was a labor of love,” he added, noting that the work took about two years. “Our research group devoted countless hours of personal effort to work on this project. We had group meetings every Wednesday to discuss progress and further strategies, and the whole group was heavily involved. Improving the upper bound for the pancake problem has challenged mathematicians and computer scientists for 30 years, and we succeeded through the dedicated efforts of our team, the willingness of all to devote many hours to analysis, verification and innovation, and our overriding belief that a better bound could be discovered.”

The paper describing this new result has been accepted for publication in the journal Theoretical Computer Science.

Media Contacts: The Office of Media Relations, UT Dallas, (972) 883-2155, newscenter@utdallas.edu

 

 


 

 

Computer science professor Hal Sudborough (center) and members of his pancake problem team (clockwise from upper left): Linda Morales, Charles Shields, Bill Fahle and Chalam Chitturi. Not pictured are Zhaobing Meng and Walter Voit.