Sorting is kind of boring,
Don't let Knuth hear this!
Heh :-) of course I admire his work on comparison networks — but one has to appreciate sub-leading terms in the asymptotics to get excited about this.
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!
Absolutely. And by parallelizing the (Gauss)-Cooley-Tukey algorithm, you’re close to understanding Coppersmith's quantum Fourier transform, which is the engine behind Shor’s factoring algorithm. - cris
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun