Lab 11 Solution

Purpose:




The purpose of this lab is to implement an experimental profiling on the Min-5 Heap, Max-5 Heap, and Binary Search Tree (BST) data structures.




General Requirements:




For this lab, you are required to implement an experimental profiling on Min-5 heap, Max-5 heap, and BST from Lab 8 and Lab 5. First, you need to make sure your implementations of both heaps and the BST are correct. You need to correct your code before you can compare the data structures’ performance. After you verify the correctness of your heaps and BST, you can move on to the performance comparison. In this lab, we will compare the runtime performance for build, deleteMin, and deleteMax operations for Min-5 heap, Max-5 heap, and BST. Then you will repeat the runs many times and take the average for each operation and for each data structure.




You are also required to submit a written report discussing the following (please submit your report in PDF format):




1- Organization of experimental profiling.

2- Input data generated using a random number generator.

3- CPU time recording in C++.

4- Data recording and analysis.

5- Performance comparison, observations, and summary. (Experimentally determine the complexity of functions for each hash table and compare them to their theoretical complexities. If they are different, you need to explain why.)




6- Conclusions.




Array size: 10,000,000 (for heaps only)

m = 1,000,000




Steps:

1- Build (using the bottom-up approach for heaps) Min-5 heap, Max-5 heap, and BST by inserting the same set of random numbers with size m (the range should be from 1 to 5m). Using CPU time, record the build time for each heap and BST.




2- Delete the min value 0.001m times from the heaps and BST, and then record the CPU time for deleteMin for each heap and for BST. Then delete the max value 0.001m times from the heaps and BST and record the CPU time for deleteMax for each heap and BST.

3- Repeat steps 1 and 2 five times using different seeds and take the average.

4- Repeat steps 1-3 with different random numbers of size 2m, 3m, 4m, and 5m.

Random Number Generator:

#include <stdlib.h

#include <time.h




int num;

/*initialize random seed*/

srand(time(NULL));




/*generate a random number between 1 and 10 inclusively*/ num = rand() % 10 + 1;




CPU Timing:

#include<time.h

clock_t t;

/*start the clock*/

t = clock();

/*insert code to be timed here*/




t = clock() – t;




Expected Results:




File for testing the correctness of your BST, Min-5 Heap, and Max-5 Heap:

Data.txt: 21 5 4 10 22 2 32 44 10 30




Note: For option 1, you should give the level order for BST, Min-5 Heap, and Max-5 Heap exactly like you did for your Lab 5 and your Lab 8.




------------------------------------------------------------

Please choose one of the following commands:

1- Test BST/Heaps

2- Performance Comparison

3- Exit

1




BST:

21522410322103044




Min-5 Heap:

2

54102221




32 44 10 30




Max-5 Heap:

44

32410222




2151030

Performance (BST):




1,000,000 2,000,000 3,000,000 4,000,000 5,000,000




Build(ms)

deleteMin(ms)

deleteMax(ms)




Performance (Min-5 Heap):




1,000,000 2,000,000 3,000,000 4,000,000 5,000,000




Build(ms)

deleteMin(ms)

deleteMax(ms)




Performance (Max-5 Heap):




1,000,000 2,000,000 3,000,000 4,000,000 5,000,000




Build(ms)

deleteMin(ms)

deleteMax(ms)










Submission:




Follow the conventions below to facilitate grading:




Source Code




Place all your source files (*.cpp, *.hpp) and input files in a single folder with no subfolders.




Name your folder using the convention Lastname_LabX (e.g., Smith_Lab11).



Include a functioning Makefile inside the folder. (The makefile should also include the clean command.)
Verify that your code runs on the lab Linux machines before submission.



Compressed File




Compress using .zip, .rar, or .tar.gz.



Name your file using the convention Lastname_LabX (e.g., Smith_Lab11.zip).



Email




Use the following subject for your email: Lastname_LabX (e.g., Smith_Lab11).



Send your code to l290w868@ku.edu if you are in one of Lei’s sections or to dhwanipandya1401@ku.edu if you are in one of Dhwani’s sections.



Anytime you have a question about the lab, put the word question in the subject of the email.