COMP15 Spring 20XX
Due: Thursday, April 21, 11:00PM
The goal of this project is to implement, test and assess a dictionary abstract data type (ADT.) A dictionary stores key-value pairs. A key is used to identify and refer to a particular pair. A key is used to select a pair in order to retrieve the associated value, remove the pair from the dictionary, etc. Dictionaries are used in a large number of applications. Compilers use a form of dictionary called a "symbol table" to store information about programmer-defined classes, types, variables and functions. The PostScript language uses dictionaries to store variables, functions and even fonts.
In this project, we will use a binary search tree (BST) representation to implement a simple dictionary ADT. In Project #8, we will use hash tables to implement the same simple dictionary ADT. In both projects, we will measure the execution speed of insertion and lookup operations. These measurements will allow us to compare the efficiency of the two implementation methods.
The objectives for this project are:
Several files are provided:
You will need to implement the dictionary ADT using the files dictionary.h and dictionary.cpp. The implementation must use a binary search tree (BST) to maintain the contents of the dictionary. Dictionary items are represented using BSTNode objects which must be allocated and deallocated dynamically. To simplify, a BSTNode elides the value part of a key-value pair and only stores the symbolic key in the form of a C-style string. The key symbol must be dynamically allocated and deallocated, too.
It is not necessary to implement a copy constructor or overloaded assignment operator for the Dictionary class.
You will need to implement a test and measurement driver, bst_search.cpp. The driver has three phases of operation:
Number of words in dictionary: 354984 Measurements for reading dictionary word list Elapsed time: 0.344894 seconds User time: 0.330000 seconds System time: 0.020000 seconds Measurements for inserting words into dictionary Elapsed time: 1.595779 seconds User time: 1.870000 seconds System time: 0.050000 seconds Number of words to lookup: 30065 Measurements for reading list of words to be found Elapsed time: 0.024342 seconds User time: 1.890000 seconds System time: 0.060000 seconds Starting lookups Lookups finished Measurements for finding words in dictionary Elapsed time: 0.077263 seconds User time: 1.960000 seconds System time: 0.060000 seconds Statistics for comparisons per find operation Samples: 30065 Minimum: 4.000000 Maximum: 45.000000 Mean: 25.181074 Variance: 668.901876 Std dev: 25.863137 Coeff of var: 1.027086
The test and measurement driver takes two command line arguments: the name of the file containing words to be place into the dictionary and the name of the file containing words to be looked-up. The usage synopsis for the driver is:
Usage: bst_search wordfile lookupfileThe test and measurement driver must check for the correct number of command line arguments.
Two test data files are provided:
Here are some additional requirements to be satisfied:
Use the provide system to submit your finished program:
/local/bin/provide comp15 p7 makefile bst_node.h ...The files to be submitted are:
bst_node.h Declaration/definition of a BST node dictionary.h Declaration of the dictionary ADT interface dictionary.cpp Definition of the dictionary ADT bst_search.cpp Test and measurement driver stats.h Declaration of the statistics interface stats.cpp Definition of the statistics module timer.h Declaration of the timing interface timer.cpp Definition of the timer module makefile makefile to build everythingDo not submit the test files moby.scrambled and lookup.
Be sure you are completely satisfied with your work before submitting! Build and test your program on comp15.cs.tufts.edu before submitting your work. This system is the target build and test platform for all course projects. Projects which do not build correctly receive a score of zero.
Project #8 will use this same informal interface specification for the dictionary ADT. Since the dictionary interface will not change, you should be able to reuse your test and measurement driver for Project #8.
Function: Dictionary() Purpose: Constructor for the Dictionary class. Initializes the dictionary to its empty state. Parameters: None Returns: Nothing Error conditions: None Function: ~Dictionary() Purpose: Deallocates (deletes) any items in the dictionary Parameters: None Returns: Nothing Error conditions: None Function: insert(char *new_symbol) Purpose: Inserts a new entry into the dictionary with the key specified by new_symbol Parameters: new_symbol: The key (a C-style string) Returns: Nothing Error conditions: Memory space exhausted Function: find(char *target) Purpose: Performs a look-up to find an item in the dictionary with the specified key Parameters: target: The key (a C-style string) Returns: True if the item was found, otherwise false Error conditions: None Function: remove(char *target) Purpose: Finds and removes the item with the specified key from the dictionary Parameters: target: The key (a C-style string) Returns: Nothing Error conditions: None Function: print Purpose: Prints (dumps) the contents of the dictionary. Only useful for debugging with *small* dictionaries! Parameters: None Returns: Nothing Error conditions: None Function: clear_number_of_comparisons Purpose: Resets the running count of symbol (string) comparisons to zero Parameters: None Returns: Nothing Error conditions: None Function: inc_number_of_comparisons Purpose: Increments the running count of symbol (string) comparisons Parameters: None Returns: Nothing Error conditions: None Function: get_number_of_comparisons Purpose: Retrieves the running count of symbol (string) comparisons Parameters: None Returns: Current running count of symbol comparisons Error conditions: NoneCopyright © 2004-2013 Paul J. Drongowski