* Cris Moore <moore@santafe.edu> [Jul 12. 2016 19:41]:
To be fair, Karatsuba's algorithm is one of the most common examples we use when teaching divide and conquer in undergraduate CS classes. More broadly, it’s a nice example of where a problem is easier than we thought it was, since one’s first intuition is that the grade school method is optimal.
I do use Karatsuba's multiplication method as an example of divide and conquer myself. What bugs me is the statement that every single divide and conquer algorithm should be looked at as coming from Karatsuba's method (I am sure Karatsuba himself would laugh at the idea) ...and the fact that it is apparently enough just to be persistent and one can spread lies even in Wikipedia. On the bright side, the Smarandache name and nonsense seems to have disappeared from the English Wikipedia. Thanks for the answers and best regards, jj
Another good example of divide and conquer is mergesort (or quicksort).
Sorting is kind of boring,
Don't let Knuth hear this!
but in this case we can show that mergesort is almost optimal, in the sense that we need log n! ~ n log n comparisons to sort n things.
We often mention the FFT as well, but sadly a lot of CS undergrads don’t understand Fourier analysis well enough to really appreciate it...
I dare say that the FFT is not quite the most simple example for divide and conquer. But a beautiful (class of) algorithm(s) it is!
Cris
On Jul 12, 2016, at 8:08 AM, Joerg Arndt <arndt@jjj.de> wrote:
More (and worse) Wiki-weirdness:
The equivalent of https://en.wikipedia.org/wiki/Karatsuba_algorithm in German is https://de.wikipedia.org/wiki/Karazuba-Algorithmus
which states that "Die Methode von Karazuba wurde zum Vorbild für das Teile-und-herrsche-Prinzip in der Informatik."
which (roughly) translates as "Karatsuba's [multiplication] method became the prototype for the divide and conquer principle in computer science."
...and that is _exactly_ what his daughter wants the world to believe.
Can anybody refute that statement?
Thanks and best regards, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun