## 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?