Problem: Shuffle
n children are sitting in a row on n chairs. You can ask any two children at any time to swap places. If you do anything else with the kids it will end in chaos which you want to avoid at all cost. You want to reorder the children on their seats so that they sit in a uniform random order. Find an algorithm to do this with at most n swaps if you have access to a random number generator rand(k) that takes as input an integer k and returns a random integer in the range [1, k]. Describe your algorithm and prove that it results in a uniform random order.