As discussed in class, a dynamic dictionary is an abstract data type which supports the following public interface:

~dictionary();

bool isEmpty() const;

bool isFull() const;

void insert(keyType k, dataType x);//insert if not already present; else update

void remove(keyType k); //remove if present

bool find(keyType k, dataType &x); //return true if present, and place data in x

void printSorted() const; //print ordered pairs (key, data), sorted by key

Implementing a dynamic dictionary. You are to provide a complete binary search tree (BST) based implementation of the dynamic dictionary ADT. Use an array for internal representation of the BST, based upon the cursor implementation method discussed in class.

Counting word frequencies. Using your dynamic dictionary, write a utility that reads in a text file specified as a command-line argument, and prints out (on standard output) a lexicographically-sorted list of all the words that occur in this file alongwith the frequency with which each word occurs. (This requires you to familiarize yourself with (i) command line arguments, and (ii) the string-manipulation package <string>.)

Rules for submitting this (and future) programs:

• You are not permitted to work in groups – all your work must be your own, and you must attest to this in a signed pledge– failure to do so results in your program not being graded.

• Include a complete listing of all your code, input files, and output files
• Your code must be appropriately commented --- if we don’t understand your code with reasonable effort, you get no credit for it.
• Include a test plan detailing how you tested your program, and why you believe it is correct. (Note that the word-counting utility does not test your deletion routines – these must be tested separately!!)

• Include a (neatly typed – not handwritten) design plan and some general comments on the structure and layout of your assignment.

All of the above should be placed in an envelope with your name on the outside, and submitted at the beginning of class on the due date. Submissions will not be accepted after 10 minutes have elapsed from the start of class – no late submissions will be accepted without documented reasons.