11.14 Exercises 269 implementation (of 1000 IP addresses using a set of random hash functions), and compare the amount of memory needed with an implementation based on semiperfect hashing. 16. Removing Redundancies in Lookup Tables: Besides the use of compressed structures, another technique to reduce the size of IP lookup tables (especially when the tables are stored in on-chip SRAM) is to remove redundancy. One simple example of redundancy is when a prefix P is longer than a prefix P and they both have the same next hop. Which prefix can be removed from the table? Can you think of other examples of removing redundancy? How would you implement such compression? Draves et al. [DKVZ99] describe a dynamic programming algorithm for compression, but even simpler alternatives can be effective. 17. Implementing Tries for Best Matching Prefix: (Due to V. Srinivasan.) The problem is to use tries to implement a file name completion routine in C or C++, similar to ones found in many shells. Given a unique prefix, the query should return the entire string. For example, with the words angle, epsilon, and eagle: Search(a) should return angle, Search(e) should return "No unique completion," Search(ea), Search(eag), etc. should return eagle; and Search(b) should return "No matching entries found." Assume all lowercase alphabets. To obtain an index into a trie array use: index= charVariable - 'a'. The following definition of a trie node may be helpful. #defineALPHA26 structTRIENODE { intcompletionStatus;