Section 3.3 Analysis of Algorithms
211
Special iNtereSt page
Of Trees % and Pancakes
Of Trees %
Mapping the evolutionary “tree of life” has been
the subject of research since Charles Darwin. Until
recently, this research sought to find similarities between species based on structural properties such
as skeletons, but today scientists search for similarities in DNA and other genetic evidence. This field of
research, called phylogenetics, can involve aligning
the molecular sequences of many thousands of species,
and the work becomes an enormous computational
problem. Researchers at the University of Texas have
developed a software package called SATé (and a new
and improved SATé-II)—Simultaneous Alignment
and Tree Estimation—that uses a divide-and-conquer
algorithm. Huge data sets are divided into small data
sets, alignments are found for the small sets, and then
the results are combined to determine an overall alignment (and a likely tree) for the full data set. The resulting full alignment isn’t foolproof, and the software
repeats this process many times, creating new alignments and trees. A statistical “maximum likelihood”
method selects the best result by comparison with
known answers. This approach has been proven to
produce results comparable to other, slower methods,
or to produce more accurate results in the same amount
of time.
Sequence alignment and evolutionary t ree-building
tools have applications to areas other than tracing the
path of historical evolution. For example, the Centers
for Disease Control use them to detect how a newly
emerging virus differs from previous viruses in order
to plan the best counterattack.
http://www.tacc.utexas.edu/news/feature-stories/2012/
tree-of-life
http://www.ncbi.nlm.nih.gov/pubmed/22139466
% and Pancakes
A problem posed in the American Mathematical
Monthly in 1975 by Jacob Goodman concerned a
waiter in a café where the cook produced a stack of
pancakes of varying sizes. The waiter, on the way to
delivering the stack to the customer, attempted to arrange the pancakes in order by size, with the largest
on the bottom. The only action available was to stick
a spatula into the stack at some point and flip the entire stack above that point. The question is: What is the
maximum number of flips ever needed for any stack
of n pancakes? This number, P n , is known as the nth
pancake number.
Here’s a fairly simple algorithm to arrange the pancakes. Put the spatula under the largest pancake, and flip.
This puts the largest pancake on top. Put the spatula at
the bottom of the unordered section (in this case at the
bottom) and flip. This puts the largest pancake on the
bottom, where it belongs. Repeat with the rest of the pancakes. Each pancake therefore requires two flips, which
would give a total of 2n flips required. But the last two
pancakes require at most one flip; if they are already
in order, no flips are needed, and if they are out of order, only one flip is needed. So this algorithm requires
at most 2(n − 2) + 1 = 2n − 3 flips in the worst case,
which means that P n ≤ 2n − 3. Are there other algorithms that require fewer flips in the worst case?
A faculty member at Harvard University posed
this question to his class; several days later, a sophomore from the class came to his office with a better
algorithm. This algorithm, which requires at most
(5n + 5)/3 flips, was published in the journal Discrete
Mathematics in 1979. The authors were William Gates
(the student) and Christos Papadimitriou.
Yes, THAT William Gates.
From SCHNEIDER/GERSTING. Invitation to Computer
Science, 6/E. © 2013 South-Western, a part of Cengage
Learning, Inc. Reproduced by permission.
www.cengage.com/permissions
C h a p t e r
3 3
211
Special iNtereSt page
Of Trees % and Pancakes
Of Trees %
Mapping the evolutionary “tree of life” has been
the subject of research since Charles Darwin. Until
recently, this research sought to find similarities between species based on structural properties such
as skeletons, but today scientists search for similarities in DNA and other genetic evidence. This field of
research, called phylogenetics, can involve aligning
the molecular sequences of many thousands of species,
and the work becomes an enormous computational
problem. Researchers at the University of Texas have
developed a software package called SATé (and a new
and improved SATé-II)—Simultaneous Alignment
and Tree Estimation—that uses a divide-and-conquer
algorithm. Huge data sets are divided into small data
sets, alignments are found for the small sets, and then
the results are combined to determine an overall alignment (and a likely tree) for the full data set. The resulting full alignment isn’t foolproof, and the software
repeats this process many times, creating new alignments and trees. A statistical “maximum likelihood”
method selects the best result by comparison with
known answers. This approach has been proven to
produce results comparable to other, slower methods,
or to produce more accurate results in the same amount
of time.
Sequence alignment and evolutionary t ree-building
tools have applications to areas other than tracing the
path of historical evolution. For example, the Centers
for Disease Control use them to detect how a newly
emerging virus differs from previous viruses in order
to plan the best counterattack.
http://www.tacc.utexas.edu/news/feature-stories/2012/
tree-of-life
http://www.ncbi.nlm.nih.gov/pubmed/22139466
% and Pancakes
A problem posed in the American Mathematical
Monthly in 1975 by Jacob Goodman concerned a
waiter in a café where the cook produced a stack of
pancakes of varying sizes. The waiter, on the way to
delivering the stack to the customer, attempted to arrange the pancakes in order by size, with the largest
on the bottom. The only action available was to stick
a spatula into the stack at some point and flip the entire stack above that point. The question is: What is the
maximum number of flips ever needed for any stack
of n pancakes? This number, P n , is known as the nth
pancake number.
Here’s a fairly simple algorithm to arrange the pancakes. Put the spatula under the largest pancake, and flip.
This puts the largest pancake on top. Put the spatula at
the bottom of the unordered section (in this case at the
bottom) and flip. This puts the largest pancake on the
bottom, where it belongs. Repeat with the rest of the pancakes. Each pancake therefore requires two flips, which
would give a total of 2n flips required. But the last two
pancakes require at most one flip; if they are already
in order, no flips are needed, and if they are out of order, only one flip is needed. So this algorithm requires
at most 2(n − 2) + 1 = 2n − 3 flips in the worst case,
which means that P n ≤ 2n − 3. Are there other algorithms that require fewer flips in the worst case?
A faculty member at Harvard University posed
this question to his class; several days later, a sophomore from the class came to his office with a better
algorithm. This algorithm, which requires at most
(5n + 5)/3 flips, was published in the journal Discrete
Mathematics in 1979. The authors were William Gates
(the student) and Christos Papadimitriou.
Yes, THAT William Gates.
From SCHNEIDER/GERSTING. Invitation to Computer
Science, 6/E. © 2013 South-Western, a part of Cengage
Learning, Inc. Reproduced by permission.
www.cengage.com/permissions
C h a p t e r
3 3