Question $4$: Lower Bounds and Linear time Sorting

$($a$)10$ points Let $\backslash ($ A$[]\backslash )$ be an array of $\backslash ($ n $\backslash )$ real $($decimal$)$ numbers, uniformly distributed from $1$ to $100.$ A student would like to print out the smallest $\backslash (\backslash$mathrm$\{$t$\}\backslash$sqrt$\{$n$\}\backslash )$ numbers in increasing order. Consider the three approaches below:

OPTION $1$

$1.\backslash ($ k$=\backslash$sqrt$\{$n$\}\backslash ).$

$2.\backslash ($ p$=\backslash$operatorname$\{$Select$\}($A$,1,$ n$,$ k$)\backslash ).$

$3.$ Loop through $\backslash ($ A$[]\backslash )$ and store all items that are less than or equal to $\backslash ($ p $\backslash ),$ in a list $\backslash ($ L $\backslash )$

$4.$ Sort list $\backslash ($ L $\backslash )$ in increasing order, using QuickSort.

$5.$ Print $\backslash ($ L $\backslash )$

OPTION $2$

$1.$ Set$-$up Bucket sort using $10$ equally$-$sized buckets in the range $1$ to $100.$ Bucket $1$ covers the range $1$ to $10$ inclusively.

$2.$ Distribute the points into buckets.

$3.$ Run insertion sort on the elements of bucket $1$

$4.$ Print out the sorted elements from bucket $1.$

OPTION $3$

$1.$ Loop through input $\backslash ($ A$[\backslash )$ and set $\backslash ($ m $\backslash )$ to be the maximum element found

$2.$ Use Counting sort with maximum$-$sized element $\backslash ($ m $\backslash )$

$3.$ Print out the first $\backslash (\backslash$sqrt$\{$n$\}\backslash )$ 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$)4$ points Draw the decision tree for the in$-$place partition algorithm on four elements.

$($c$)4$ points 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 $\backslash ($ B $1$ C $3$ X $4\backslash ).$ Explain how to sort a set of $\backslash ($ n $\backslash )$ licenses using Radix sort, and justify the runtime.

I need the answer in written format $($on paper$).$