Random Shuffle & Fisher-Yates Algorithm

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.