Paper, Order, or Assignment Requirements

Points: 50

1. Which of the sorts that we’ve discussed in class are stable (or can easily be written to be stable)? Which are not?
2. How efficient is MSD Radix sort compared to Quicksort for sorting ints in Java if 8 bit bytes are used as the characters (that is, an int is comprised of four 8 bit bytes.) How does this work out in practice?
3. Show the search trie that results from inserting the strings (and data) “ant” (0), “anteater” (1), “antelope” (2), “aardvark” (3), “bat” (4), and “zebra” (5), into an initially empty trie. Do the same for a ternary search trie.
4. Give the DFA array for the Knuth-Morris-Pratt substring match algorithm for the pattern “ABCABCAB”.
5. Give an NFA for recognizing the regular expression “a* | ( a* b a* b a* )*”.