12 ms·
I know Knuth for his The Art of Computer Programming and TeX, and he's clearly amazingly smart - I'm curious about what algorithms he has invented, for what app
by 10ren 17y ago
I know Knuth for his The Art of Computer Programming and TeX, and he's clearly amazingly smart - I'm curious about what algorithms he has invented, for what applications. e.g. Is there a "Knuth's Algorithm" (like Dijkstra's)?
- jcl 17y agoWikipedia gives a few... http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pr... http://en.wikipedia.org/wiki/Knuth-Bendix_completion_algorithm http://en.wikipedia.org/wiki/Knuth-Bendix_completion_algorit... There are probably others as well. KMP is well-known and, I believe, commonly implemented for text search. Algorithm X is implemented in his "dancing links" method, and can be used (among other things) to solve Sudoku puzzles.
- 10ren 17y agoThanks, how silly of me: the text search algorithms are some of my favourites. :-(
- paulgb 17y agoI learned of the Fisher-Yates shuffle as the Knuth shuffle, but apparently both names are used for it. http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- Aron 17y agoI have used an alternate shuffling approach in the past of my own naive creation, which is to go from 1-N items, each pass selecting a random number to swap the current position with. This would not require counting over missing items (those copied to result) on each loop. What is the flaw in this approach I wonder?
- paulgb 17y agoI've used that method too. The flaw is that it is biased; some permutations will be more likely than others. Each shuffle will consume N random numbers between 1 and N (inclusive). This gives a total of N^N equally probable N-tuples of random numbers, all corresponding to exactly one output permutation. But there are only N! possible permutations, so some of the N^N N-tuples must share the same output permutation. Since N! does not usually divide N^N evenly, some permutations must be more probable than others.
- Aron 17y agoAh....clever. thx.
- gchpaco 17y agoThe only one with his name on it that comes to mind is KMP, the Knuth-Morris-Pratt algorithm for text searching, which is actually a fairly big deal in that community. But most of the typesetting algorithms in TeX were totally novel at the time; ditto Metafont. Wikipedia lists several others, including his popularization of the "Dancing Links" exact cover algorithm and his cunning test of recursion in Algol 60 compilers (which was very new at the time).