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