Description
1. [15 pts] Run quickselect on the sequence below to find the 7th smallest
element.
Assume the pivot for any subsequence is always the 1st element in
the sequence.
Please show intermediate steps of the algorithm.
3, 17, -5, 4, 13, 8, 7, 6, 9 find 7th smallest
element
2. [15 pts] Run quickselect on the sequence below to find the median of the
sequence.
Assume the pivot for any subsequence is always the 1st element in
the subsequence.
Please show all intermediate steps of the algorithm.
9, 8, 6, 4, -100 find the median
3. [20 pts] You have just run quickselect on integers from 1 – 9. The array
below shows the output of the
partition
3 1 2 4 5 8 7 6 9
What are the possible pivot elements ?
4. [20 pts] Given a set of 5 numbers:
1, 2, 3, 4, 5
The output of the KFY shuffle is:
1, 4, 2, 5, 3
Give a sequence from the random number generator that produced this
output.
5. [30 pts] Suppose you change the shuffling algorithm to select a random
number between 0 and N-1 at each stage. For this problem, let N = 3. (Sorting
3 items).
5.1 [10 pts] What is the total number of exchange sequences generated
by “always between 0 and N-1” (bshuffle)?
5.2 [10 pts] What is the total number of exchange sequences generated
by KFY shuffling algorithm?
5.3 [10 pts] How does this show a bias for the faulty algorithm?
