Programming_Assignment_2 _ BSTMarch 2, 2023 Programming Assignment 2 Prof. Rahul Shah Due: March 23, 2023 (Thursday 11:59 PM) Problem Statement: Binary Search Tree with Range...

Programming_Assignment_2 _ BST March 2, 2023 Programming Assignment 2 Prof. Rahul Shah Due: March 23, 2023 (Thursday 11:59 PM) Problem Statement: Binary Search Tree with Range Minimum Queries (RMQs) For this assignment, we are to create insert-only (will make your lives easy) Binary Search Tree (not AVL – again making your lives easy). Each node will contain: class Node { int key; int data; int mindata; Node *left, *right, *parent; }; The goal is to compare two methods for computing RMQs. And compare their times for different data sizes of 3000, 10000, and 30000. What is an RMQ ? We did this as homework 2 question 4. RMQ (*root, k1, k2) returns the smallest data value among all the keys which fall within k1 and k2 (both k1 and k2) inclusive. Method 1: will be naïve one, which will use the range-report solution of question 3 in homework 2. That is, visit each key which falls within k1 and k2. And look at the data value of each qualifying node – and keeps track of the minimum thus seen. This can be done by slightly modifying the pseudocode provided in homework 2 solutions for question 3. Method 2: will use the mindata field and keep track of that field during the insertion. p->mindata basically maintains the minimum data value in the entire subtree of the node p (p included). You have to maintain this during insertion. Based on this, use the pseudocode in the solution provided for homework 2 question 4. Submission: There are going to be two modes of submission here. On gradescope, you will submit so that correct answer is verified. This will be for small example. On moodle, you will submit the report of your findings with timing analysis. Submission 1: (Gradescope) Input file will be of the form pair, as follows. IN stands for insert RMQ stands for the range minimum query 10 //number of lines IN 6 207 IN 12 545 IN 7 32 IN 4 191 IN 2 100 IN 17 344 IN 8 37 IN 1 20 IN 15 787 RMQ 4 9 // answer should be 32 Submission 1: The submission on gradescope must follow Method 2. It cannot be inefficient (like Method 1). Submission 2: (Moodle) Here you will only submit report of your timing experiment. You will use random numbers for keys, data as well as ranges for the queries. USING RANDOMLY generated DATA: First generate keys uniformly between [0, MAXSIZE]. Generate data for each key as from uniform generation between [0,MAXSIZE]. MAXSIZE will be set to 32767. (This is also default for random number generator in C). Firstly, note down the time to build the tree. After the tree is built, the timing experiment for queries will start. Generate 1000 RMQ queries with Random ranges. i.e., generate 2000 random numbers (making up 1000 pairs of the type ). Execute these queries and note down the time for both method 1 and method 2. CAREFUL !! : You will have to be careful here for the duplicate entries. If a key which is being inserted is already present in the tree, then if the data of newly inserted key is smaller, then we change existing keys data to that one. And then, discard the new insertion. If we find that newly inserted node has data which is more than existing node with the same key, then we simply discard the insertion. What will report contain: It will have timing charts, which will show insertion time per item (divide the total time by # of items (3000,10000,30000) . And then it will show average query time for RMQ with method 1 and method 2. This could be 3x3 bar chart or 3 lines (on scaled axis). Finally, you need to explain your findings along with complexity analysis. You will have to write a program in C++ or Java to implement a Binary Search Tree with Range Minimum Queries. Your file name should be BST.java or BST.cpp. The input file name is inputFile.txt. According to the gradescope auto-grader, for the input given above, the output should be 32 with a newline character appended to it.