1. Ordered operations for tries. Implement the floor(), ceil(), rank(), and select() (from our standard ordered ST API from CHAPTER 3) for TrieST.
2. Construct a worst-case example for the Boyer-Moore implementation in ALGORITHM 5.7 (which demonstrates that it is not linear-time).
3. How would you modify the Rabin-Karp algorithm to search tor a given pattern with the additional proviso that the middle character is a "wildcard" (any text character at all can match it).
4. Draw the NFA corresponding to the pattern (((A l B)*| CD*| EFG)*)*.
5. Draw the digraph of ∈ - transitions for the NFA from EXERCISE 4.
6. Give the sets of states reachable by your NFA from EXERCISE 4 after each character match and susbsequent E-transitions for the input A B B A C E F G E F G C A A B.
7. Challenging REs. Construct an RE that describes each of the following sets of strings over the binary alphabet:
a. All strings except 11 or 111
b, Strings with 1 in every odd-number bit position
c. Strings with at least two Os and at most one 1
d. Strings with no two consecutive 1s