Question $4$: Lower Bounds and Linear time Sorting

$($a$)$ Let $A$ be an array of $n$ real $($decimal$)$ numbers, uniformly distributed from $1$ to $100.$

A student would like to print out the smallest $t\sqrt[\phantom{2}]{n}$ numbers in increasing order. Consider the three

approaches below:

OPTION $1$

$k=\sqrt[\phantom{2}]{n}.$

$p=$Select$(A,1,n,k).$

Loop through A and store

all items that are less than

or equal to $p,$ in a list $L$

Sort list $L$ in increasing or$-$

der, using QuickSort.

Print $L$

OPTION $2$

Set$-$up Bucket sort using $10$

equally$-$sized buckets in the

range $1$ to $100.$ Bucket $1$ covers

the range $1$ to $10$ inclusively.

Distribute the points into buck$-$

ets.

Run insertion sort on the ele$-$

ments of bucket $1$

Print out the sorted elements

from bucket $1.$

OPTION $3$

Loop through input and set

$m$ to be the maximum element

found

Use Counting sort with

maximum$-$sized element $m$

Print out the first $\sqrt[\phantom{2}]{n}$ elements

from the resulting sorted array

Your Job:

For each option, determine if the procedure correctly solves the problem.

Determine the Expected runtime of each approach, and justify your answer.

Which option is expected to be asymptotically faster? Or are they expected to be asymptotically

equivalent?

$($b$)$ Draw the decision tree for the in$-$place partition algorithm on four elements.

$($c$)$ A car license consists of $6$ characters, where the characters alternate between alphabetic

characters $($A to Z$)$ and numerical characters $(1$ to $9).$ An example of a valid license is