Pearls of Functional Algorithm Design, Chapter 2, The Surpasser Problem

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Pearls of Functional Algorithm Design, Chapter 2, The Surpasser Problem

Costello, Roger L.
Hi Folks,

I created Powerpoint slides to describe the algorithm for the "surpasser problem".

Here is a motivation for the surpasser problem:

Stock Market:

Each day I record the closing value of the DOW. Occasionally, I pick a date and ask, "How many days after this date has the stock market closed at a higher value?"

A more challenging question is, "Which day has the most number of following days where the stock market closed at a higher value?"

People's Height:

Line up a bunch of people. Pick one person and ask, "How many of the following people are taller than this person?"

A more challenging question is, "Which person has the most number of following people that are taller?"

Word Analysis:

Take a letter in a word and ask, "How many of the following letters are bigger (occurs later in the alphabet) than this letter?"

A more challenging question is, "Which letter has the most number of following letters that are bigger?"

Thus we see a recurring problem: find the number of surpassers; or, find the maximum surpasser count. Recurring problems are good subjects for elegant algorithms.

More ...

http://www.xfront.com/Pearls-of-Functional-Algorithm-Design/Chapter2/surpasser-problem.pptx

/Roger