Description
Reminder: Thursday’s lab will be in 1010 Eaton. Even though 1010 Eaton is a Window’s lab you should be able to write the additional function below and make sure everything is working properly. CodeBlocks is an IDE for C++ that should be on the Windows machines.
This is a continuation of lab 4. This week you will implement one more function and collect run time statistics on the operations to see which structure is better for each operation. The data file for this project from which to build your database is data5M.txt, data5T.txt, or data5R.txt depending on whether the lab meets on Monday, Tuesday or Thursday.
The additional function to be implemented for each data structure is:
Given a point and a distance d, find and print out all cities within distance d of the point. You might want to use the database you used for testing last week in order to show that your distance function runs correctly. You must make sure it’s correct before continuing with the rest of this lab.
In case you’ve forgotten the formula, the distance between points (x1, y1) and (x2, y2) is given by SQRT( (x2 – x1)2 + (y2 – y1)2)
For each of the insert and delete operations you have programmed, experiment to see which data structure gives you better performance. Since actually timing them is impractical, one way to do this is to put a counter in each function that counts the number of item comparisons that are made in that function. If you have another idea on how you’d like to structure the testing, ask Mehrdad if what you’d like to do will work. You must run at least ten tests for each algorithm and report the results as part of what you hand in. Also, state any conclusions that you think can be drawn from those results.
To test the distance function, use the data in the file lab5_testM.txt, lab5_testT.txt or lab5_testR.txt. Each line in that file contains three integers—the x and y coordinates of a point and a distance d. First determine if the point is in the database and, if so, output the name of the associated city. Then, output the list of all cities in the database that lie within distance d of the point, even if the point is not in the database.
Turn in your code for the distance function and all results obtained by testing the algorithms. Also include a discussion of which structure is “better” for each operation. Be sure to justify your conclusions. Since the distance function must effectively examine every city in the database, is either structure better for this operation? Justify your answer.
Due dates: Sunday night for the Monday and Tuesday labs and Monday night for the Thursday lab. Note: labs may be in use for Expo from Wednesday night to Saturday afternoon.
Remember the first test is on Wednesday March 9.