$\backslash$problem$[$Selecting a nut$-$bolt pair in space$]\{2+3+10\}$

You are an astronaut in space given the enviable task of doing a space

walk to fix a loose shield in your spaceship. The shield is loose

since it is missing a single nut$-$bolt pair. You have your toolbox

with $N$ different nuts and $N$ different bolts. When these were

originally packed, they were in matching pairs and sorted, but the

violent lift$-$off undid all of that, and you are left with $N$ nuts of

different widths and $N$ bolts of different widths scattered all over,

only with the comfort of knowing that there exists a $1-1$ match between

the nuts and bolts.

The spaceship manual says that you need the particular nut$-$bolt pair

of rank $k$ in the sorted order of nuts and bolts. That is$,$ if you

were to sort both nuts and bolts in increasing order of widths, then

the $k$th nut and $k$th bolt in this order $($which will match one

another$)$ is the desired pair. But here is the catch: the difference

between the sizes of two nuts or the sizes of two bolts is so tiny

that $\backslash$emph$\{$it is impossible for you to manually compare two different

nuts or two different bolts$\}.$ You can, however, try a nut $x$ and

bolt $y$ together, using the procedure $$\backslash$textsc$\{$match$\}($x$,$y$)$$ which

returns one of these three outputs $($i$)\backslash$textsc$\{$Nut$-$Too$-$Large$\},($ii$)$

$\backslash$textsc$\{$Nut$-$Too$-$Small$\},$ or $($iii$)\backslash$textsc$\{$Exact$-$Match$\}.$ But note that

there is no way to compare two nuts together, or two bolts together.

In this problem, we will develop algorithms for determining the $k$th

nut$-$bolt pair in the sorted order of matched nut$-$bolt pairs.

$\backslash$begin$\{$enumerate$\}$

$\backslash$item Describe precisely what your algorithm is given as input and what it

needs to output.

$\backslash$item Design an $O$($n$^2)$$ time deterministic algorithm for the problem.

Assume that any call to $$\backslash$textsc$\{$match$\}$$ takes unit time. Describe

your algorithm in pseudocode, and analyze its running time.

$\backslash$item We now consider a randomized expected $O$($n$)$$ time algorithm for the

same problem!

$\backslash$begin$\{$enumerate$\}[$label$=(\backslash$roman$*)]$

$\backslash$item Suppose you select a random nut, match all the $n$ bolts with this

nut, and partition the bolts based on the three responses: one set

of bolts that are too small, one matching nut$-$bolt pair, one set

of bolts that are too large. What is the probability that the

sets of bolts that are too small and too large are each of size at

least $n$/4$$$?$

$\backslash$item If each of the two sets $--$ too small and too large $--$ is of size

at least $n$/4$$$,$ let us call it a $\backslash$emph$\{$success$\}.$ Suppose you

repeat the step given in $($i$)$ until success. What is the expected

number of times you have to repeat the above step to achieve

success?

$\backslash$item Design a randomized algorithm that uses the idea from $($i$),$ then

partitions the $\backslash$emph$\{$nuts and bolts$\}$ into three parts$---$a matching

nut$-$bolt pair, and two groups of appropriately selected nuts and

bolts with the number of nuts in each group equal to the number of

bolts in the group$---$ and does a suitable recursion $($like

Randomized Selection$)$ to solve the given problem. Describe your

algorithm in pseudocode.

$\backslash$item Using $($ii$),$ analyze the expected running time of the problem.