Tik-61.183 Special course on information technology III Randomized algorithms Spring 2000 Heikki Mannila

Exercises 3, due March 15, 2000

1. Complete last time’s exercise 2.4: show that the given algorithm does indeed select a permutation uniformly.

Set X ← (1, 2, …, n).

Repeat for i = 1, 2, …, n − 1:

Select a number r ∈ {i, i + 1, …, n} at random.

Exchange X[i] ↔ X[r].

Output X.