$(20$ points$)$ Let $A$ be an array of strings of various lengths, and the total

number of characters over all the strings is $n.$ More technically, A stores

an array of pointers to string objects, whereas a string object $($e$.$g$.,$ string

in STL$)$ stores the length $l$ of the string and an array of $l$ characters. We

assume that each character can be viewed as an integer ranging from $0$

to $255.$ The goal of this problem is to sort the strings alphabetically. For

example, $\frac{\frac{?}{?}}{0}O(n)(n^2)ABa.$

$(a)(5$ points$)$ Consider the following algorithm: First pad $\text{'}\frac{\frac{?}{?}}{0}\text{'}(the$ char$-$

acter with ASCII code $0)to$ the right $of$ each string $so$ that all strings

have equal length, and then run radix sort $on$ all strings. What's the

worst$-$case running time $of$ this algorithm? Give $an$ input $on$ which

this running time $is$ attained.

$(b)(15$ points$)$ Design and analyze $an$ algorithm that sorts the strings

$inO(n)$ time.

Hint: Combine divide$-$and$-$conquer with counting sort. The running

time $of$ this divide$-$and$-$conquer algorithm can't $be$ analyzed $byare-$

currence. You can try $to$ count the total number $of$ operations over

all recursive calls; for example, the first recursive integer multiplica$-$

tion algorithm has running time $(n^2)$ because $it$ multiplies every

bit $of$ A with every bit $ofB.$