Programming Assignment 5

Trees

Due before midnight on Tuesday Nov 14th

Objectives:

The objectives of this exercise are:

1. To become familiar with Binary Search Trees

· Being able to fully define a BST

· Being able to fully define an AVL tree including the rotations

Overview:

As we have been discussing various binary trees in class, this lab focuses on the use of binary search trees. You are going to implement a basic spell-checking program using binary search trees. Your program should prompt the use for a word to be checked, search for this word in your tree, and if it is found, tell the user that the word is correctly spelled. In order to understand the difference in efficiencies provided for by having a balanced binary search tree (i.e., an AVL tree), you will also run some experiments on searching for a given word in both an AVL and a regular BST.

Instructions:

 Make sure that you read over the lab assignment and get any clarification that you need. Then follow these steps:

1. Download the following files from the class website:

• btn (a binary tree node class)
• bst(a binary search tree class)
• avl (an AVL tree class)
• dictionary.txt (a list of words to be used as your dictionary to check proper spelling)

2. Implement all of the functions declared in BTN.h, BST.h, and AVL.h

3. Write a simple driver program name test.cpp to test all of the functions in the binary search tree and AVL tree classes

4. Write a program named spell.cpp which reads in the dictionary file, creates a binary search tree and an AVL tree from this program, and then accepts user input for a word to be checked for correct spelling. THIS program should then search the trees to determine if the word was in the dictionary. It should let the user know if the word was there. Also it should tell the user how long it took to search for the word on each of the trees (see below).

5. Since searching will be relatively quick and we want to be able to capture the time it takes to search on our different trees, in order to get comparable time you should run the search procedure 1000 times or more for each word being searched for. (you may have to try a few different values for your loop limit in order since it depends on your machine) For example:

#include <time.h>

clock_t stime = clock();

BST<T> Btree;

for (int i = 0; i < 100000; i++) { //search 100000 times

Btree.search(value);

}

clock_t etime = clock();

double elapse;

elapse =(double)(etime-stime)/CLOCKS_PER_SEC;

cout << "Search in BST tree took " << elapse << " seconds " << endl;

And then do the same timing for an AVL tree search

6. Make sure to report your timings in a chart comparing BST and AVL search times

Deliverables
For this you need to turn in the following before 5 pm on Tuesday Nov 14th (NOTE: It is essential that you turn in both hard and soft copies of your code and your report.):

• Email containing all of the following to dstrahma@mtholyoke.edu:
• Subject containing your name and which submission this is.
• Body containing a list of file attachments.
• Attached (soft copy) Source Code files associated with this assignment, and only this assignment.
• Attached (soft copy) Report in Word format.
• Instructions for compiling your code should be in the body of the email, as well.
• Note: the code you turn in must compile. If you have parts working and other parts not working, please comment out the parts that do not compile.
• Your (hard copy) printed Report (Word document), which includes:
• Analysis and Conclusions of what you learned from the exercise.
• A printout of your test driver output showing the output for the test cases.
• Your test plan, test log (which records what happened as testing) , and test cases.
• A Printout of your source code.

Grading:

Credit distributed in the percentages assignment is worth 100 points distributed as follows:

· BST class correctness 20%

· AVL class correctness 20%

· Test driver 10%

· Spell Check program 15%

· Test Plan and Test Log 10%

· Analysis questions 10%

· Report, including timings 15%

Analysis Questions

1. How does the ordering of the words in the dictionary file impact the architecture of the binary search tree?

2. How would your search timings change for the BST if you started reading the dictionary file from the middle of the file rather than the beginning? (To answer

this fully you need to reorder the dictionary file and test this.)

3. How do results this compare to theoretical runtime complexity?

Extra credit (may be handed in later)

Implement using tries and compare to BST and AVL additional credit 50%