1.05.md

Chapter 5. Probabilistic Analysis and Randomized Algorithms

This chapter introduces probabilistic analysis and randomized algorithms.

It discusses how probabilistic analysis can be used to analyse the inputs of algorithms, and how that can help us randomize input to ensure a better distribution (in cases where, for example, we know the input received to be generally the cause of poor performance).

Permute by sorting

Input: A sequence of n numbers <a₁, a₂, ..., a_n>.

Output: A new sequence, containing a random permutation of the same values.

Pseudocode:

Permute-By-Sorting(A)
     n = A.length
     let P[1..n] be a new array
     for i = 1 to n
         P[i] = Random(1, n³)
     sort A, using P as sort keys

In Kotlin: Implementation and Tests.

Randomize in-place

Input: A sequence of n numbers <a₁, a₂, ..., a_n>.

Output: The same sequence, modified to contain a random permutation of its values.

Pseudocode:

Randomize-In-Place(A)
     n = A.length
     for i = 1 to n
         swap A[i] with A[Random(i, n)]

In Kotlin: Implementation and Tests.