CS 206: Data Structures
Assignment#7

Due on Thursday, April 15

Part#1: Repeat Assignment#5 but this time, prior to searching for towns, sort the data so that it is in acsending order of town names. You may use any sorting algorithm discussed in class for sorting the data. As in Assignment#5, output the number of comparisons performed during searches. Compute the average number of comparions needed to answer a query, the average number of comparisions needed to answer a successful query, the average number of comparisons needed to answer an unsuccessful query.

Part#2: Repeat Assignment#5 but this time, use a Binary Search Tree to store the data. Once you have constructed the tree, output the height of the final tree. As in Assignment#5, output the number of comparisons performed during searches. Compute the average number of comparions needed to answer a query, the average number of comparisions needed to answer a successful query, the average number of comparisons needed to answer an unsuccessful query.

Compare the averages obtained from Part#1 and Part#2 with those obtained from Assignment#5. Additionally, in Part#2 how do these relate to the height of the tree? Discuss the results obtained.

What to Hand-in:

1. A complete printout of the latest version of your program(s)
2. A prinout of your program showing the outputs from the queries above (as well as some failed queries)
3. The average comparisions data and how it compares to the previous assignment.
   

Back to CS206 Course Materials