Name: Random Shuffle & Fisher-Yates Algorithm
Uploaded: 2020-12-12T14:26:11+00:00
Duration: 26 min 36 s
Description: This lecture introduces the random permutation (aka random shuffling) problem. We can use Fisher-Yates algorithm for randomly shuffling a sequence. This lecture introduces the two versions of the Fish

3 years ago

Randomized Algorithms Random Shuffle Random Permutation Fisher-Yates Durstenfeld

This lecture introduces the random permutation (aka random shuffling) problem. We can use Fisher-Yates algorithm for randomly shuffling a sequence. This lecture introduces the two versions of the Fisher-Yates shuffle. The original version [Fisher-Yates 1938] has quadratic time complexity. The modern version [Durstenfeld 1964] has linear time complexity.

Slides: https://github.com/wangshusen/AdvancedAlgorithms

Reference:
1. Fisher, Ronald A.; Yates, Frank. Statistical tables for biological, agricultural and medical research, 1938.
2. Durstenfeld, R. Algorithm 235: Random permutation. Communications of the ACM, 7 (7): 420, 1964.

Loading comments...