Utilities - Data Structures and Problem Solving Using Java - page 504

all misspelled words and the line numbers on which they occur (note
that keeping track of the misspelled words and their line numbers is
identical to generating a cross-reference). Also, for each misspelled
word, list any words in the dictionary that are obtainable by applying
any of the following rules.
a. Add one character.

b. Remove one character.

c. Exchange adjacent characters.

Two words are anagrams if they contain the same set of letters (with
same frequencies). For instance, least and steal are anagrams. Use a
map to implement a program that finds large groups of words (five
words or more) in which each word in the group is an anagram of
every other word in the group. For instance, least , steal , tales , stale ,
and slate are anagrams of each other and form a large group of ana-
grams. Assume that there is a large list of words in a file. For each
word, compute its representative . The representative is the characters
of the word in sorted order. For instance, the representative for the
word enraged is adeegnr . Observe that words that are anagrams will
have the same representative. Thus the representative for grenade is
also adeegnr . You will use a Map in which the key is a String that is a
representative, and the value is a List of all words that have the key as
their representative. After constructing the Map , you simply need to
find all values whose List s have size five or higher and print those
List s. Ignore any case distinctions.

12.21

Implement a sorting algorithm using a TreeMap . Because a TreeMap
does not allow duplicates, each value in the TreeMap is a list containing
duplicates.

12.22

Assume that you have a Map in which the keys are names of students
( String ), and for each student, the value is a List of courses (each
course name is a String ). Write a routine that computes the inverse
map, in which the keys are the names of the courses and the values
are lists of enrolled students.

12.23

Static method computeCounts takes as input an array of strings and
returns a map that stores the strings as keys and the number of occur-
rences of each string as values.
a.

12.24

Implement computeCounts and provide the running time of your
implementation.

b. Write a routine, mostCommonStrings , that takes the map generated

in part (a) and returns a list of the strings that occur most often
(i.e., if there are k strings that are tied as the most common, the