COMP582 Module 10 Problems solution

Description

1. [16 pts] Consider an input of size N consisting of exclusively numbers.
Suppose you know the input values are not bounded. You do know, however,
that the number of distinct input values is “small” Specifically, let M be the
number of distinct input values. Then, you are guaranteed that M log M =
O(N). Give an algorithm that has expected time O(N) to sort the items.
Hint: What techniques do you know that make good use of expected-time
behavior?
2. [12 pts] Give a trace for the LSDsort applied to the following strings:
no is th ti fo al go pe to co to th ai of th pa
3. [12 pts] What modification to LSDsort would you make to cover variable
length strings?
4. [12 pts] Draw the 26-way trie that results from inserting the following
strings into the empty trie
no is th ti fo al go pe to co to th ai of th pa
5. [12 pts] Draw the TST that results from insering the following strings into
the empty trie
no is th ti fo al go pe to co to th ai of th pa
6. [12 pts] Draw the 26-way trie that results from inserting the following
strings into an initially empty trie
now is the time for all good people to come to the aid of
7. [12 pts] Draw the TST that results from inserting the following strings into
an initially empty trie
now is the time for all good people to come to the aid of
8. [12 pts] Show the state transitions for DFA below
DFA
0 1 2 3 4 5
A 1 1 3 1 5 1
B 0 2 0 4 0 4
C 0 0 0 0 0 6
for the following input strings:
8.1 [6 pts] ABCAAABABABACAABB
8.2 [6 pts] ABCAAABAABACAABBA