[Haskell-cafe] New slogan for haskell.org
lemming at henning-thielemann.de
Fri Dec 14 03:01:34 EST 2007
On Wed, 12 Dec 2007, Bill Wood wrote:
> On Wed, 2007-12-12 at 11:19 +0000, Andrew Coppin wrote:
> . . .
> > ...and normal programmers care about the Fibonacci numbers because...?
> > Seriously, there are many, many programmers who don't even know what
> > Fibonacci numbers *are*. And even I can't think of a useful purpose for
> > them. (Unless you count Fibonacci codes?)
> Knuth pp. 417-419 discusses Fibonacci trees and Fibonacci search.
> According to Knuth (and who am I to argue with him) Fibonacci search has
> better average case running time than binary search, although worst case
> can be slightly slower.
> Cormen et. al. devotes chapter 20 to Fibonacci heaps, which they say
> are of primarily theoretical interest.
>  Donald E. Knuth, The Art of Computer Programming, vol. 3, second
> edition, Addison Wesley Longman (1998).
>  Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and
> Clifford Stein, Introduction to Algorithms, second edition, The MIT
> Press (2001).
Worst case analysis of AVL trees also leads to Fibonacci numbers, as far
as I remember.
More information about the Haskell-Cafe