Assignment 1: Anagrams

Due: 5:00pm, Thursday, February 4. Value: 40 pts. Submit your solution (consisting of dict.c only) using the Sauron Submission System. [instructions]

The starting code for this assignment is spread over five files. The program reads in a dictionary of words and then permits the user to query the dictionary to check whether words are in the dictionary.

hash.c	provides a hash table data structure where strings are the keys.
hash.h	declares the data structure and function prototypes for hash.c.
dict.c	provides three functions for managing a dictionary and processing queries. This is the file you will modify for this assignment.
dict.h	declares the data structure and function prototypes for hash.c.
main.c	defines the main function, which reads the dictionary file and prompts the user repeatedly for query words.

Before starting the assignment, you should first download these five files and ensure that you can get the program working as distributed. If you're working on your own computer, you may need a dictionary file; you can work with the Scrabble dictionary.

Compiling C programs
Debugging C programs

Your assignment is to modify the dict.c file of the provided program so that the program displays all anagrams of each query string within the dictionary (rather than display simply a string indicating whether the query word is within the dictionary). Below is a sample illustrating the proper output of your program.

Query? quite
2 anagrams found
quiet
quite
Query? quit
1 anagram found
quit
Query? qui
no anagrams found
Query? control-C to exit

Important restrictions:

• Your program's output must match the above example precisely, including displaying the words in alphabetical order. (Note that the dictionary will come to you in alphabetical order.)
• You must not modify any files except dict.c.
• You must use the functions of hash.c to perform lookups.
• You must use the algorithm described below, where there is precisely one hash table lookup for each query word.
• Beware of memory leaks — that is, memory that is allocated without ever being deallocated. A program with memory leaks is hard to detect, since it works normally and only slowly degrades as it allocates more memory. But you can detect such leaks using a profiler such as valgrind.

Algorithm

Perhaps the obvious way to perform this assignment is to store each dictionary word in the hash table, and then with each query to generate all rearrangements of the query word and look up that rearrangement in the dictionary. This is the slow technique, and you should not use it.

Instead, with each dictionary word, you should sort the letters of that word and use that as the key for your hash table. Thus, given the word quiet, the program would compute the key eiqtu and then associate quiet with that. Given quite, the program would also compute the key eiqtu and associate quite with that key as well.

Then, given a query of quite, your program would perform one hash table lookup on the the sorted letters (eiqtu), and it would discover that both quiet and quite are associated with eiqtu. It would display both words.

The following code for insertion sort is a useful starting point for sorting the characters. It sorts an array of ints, where n stores the array's length. You should be able to adapt it to sorting the characters of a string easily.

for(i = 1; i < n; i++) {
    t = array[i];
    for(j = i - 1; j >= 0 && array[j] > t; j--) {
        array[j + 1] = array[j];
    }
    array[j + 1] = t;
}