*** if you only choose to answer one part, please answer part b. and c.

Problem 2. Lecture 7 presented radix sort as performed on integers; this problem explores radix sort performed on strings. a) Consider the following list of four-letter words (not that kind, don't worry): PATH PAST FAST CHIP HOME List the words in the order they would appear after two passes of radix sort done top-to-bottom using lexicographic (i.e. alphabetical) ordering. Order the list least-to-greatest from top to bottom: (lexicographically least) (lexicographically greatest) b) Give a list of five 4-character strings (they do not have to be real words) on which radix sort would return an incorrect answer if done in most-significant- to least-significant-position order Assume the radix sort scans the list from top to bottom on each pass. c) If radix sort as presented in Lecture 7 were implemented on same-length strings of English and Chinese characters, which implementation would be faster on a small input set of 100 strings in the worst case? Consider relevant constant factors. Why