Project 1: RMQProject 1: RMQMax excellence credits: 1.0• Your code must be of good quality, well commented, and pass all test cases to earn excellencecredits.Tasks:1. Implement spare table...

pHi, I need help with this Algorithm project using Java.











Project 1: RMQ Project 1: RMQ Max excellence credits: 1.0 • Your code must be of good quality, well commented, and pass all test cases to earn excellence credits. Tasks: 1. Implement spare table RMQ structure. 2. Implement hybrid approach one efficiently (in the lecture notes). The performance of your implementation will be compared with other teams’ implementation. 3. Implement Fischer-Heun algorithm. 4. Compare the performances of the hybrid 1 and Fischer-Heun approaches. Generate input arrays of various sizes (n=10M, 100M, 200M, and 400M) and measure preprocessing time for each n. Measure the query processing time over various ranges (0.01n, 0.1n, 0.2n, 0.4n, 0.8n) for each n. Run several trials and take the average for each measurement. Write a good report (with graphs) about your observations. Starter code and driver code are provided. RMQ.ink RMQ Problem Input: An array A and two integers i and j Output: Find the smallest element among A[i]…A[j] CS 6301 IDSA 2 24 32 58 6 94 86 16 2 RMQ Problem Input: An array A and two integers i and j Output: Find the smallest element among A[i]…A[j] CS 6301 IDSA 3 24 32 58 6 94 86 16 2 i j RMQ Problem Input: An array A and two integers i and j Output: Find the smallest element among A[i]…A[j] CS 6301 IDSA 4 24 32 58 6 94 86 16 2 i j RMQ Problem Input: An array A and two integers i and j Output: Find the smallest element among A[i]…A[j] CS 6301 IDSA 5 24 32 58 6 94 86 16 2 i mi n j RMQ Problem Input: An array A and two integers i and j Output: Find the smallest element among A[i]…A[j] CS 6301 IDSA 6 24 32 58 6 94 86 16 2 i j RMQ Problem Input: An array A and two integers i and j Output: Find the smallest element among A[i]…A[j] CS 6301 IDSA 7 24 32 58 6 94 86 16 2 i j RMQ Problem Input: An array A and two integers i and j Output: Find the smallest element among A[i]…A[j] CS 6301 IDSA 8 24 32 58 6 94 86 16 2 i jmi n Straight forward solution • Iterate from A[i] through A[j] and find the minimum • Suppose A is fixed, and there will be many different queries • Can we do better than the above O(n) solution? CS 6301 IDSA 9 How many distinct queries? • i: 0 to n-1 and j: 0 to n-1 • Maximum number of distinct queries = n2 • Preprocess these queries and store it in a table CS 6301 IDSA 10 Preprocess the all distinct queries 11 24 32 58 6 0 1 2 3 0 1 6 2 3 i j Preprocess the all possible queries CS 6301 IDSA 12 24 32 58 6 0 1 2 3 0 24 24 24 6 1 32 32 6 2 58 6 3 6 • How to build the table? • For each entry in the table, find the minimum over the range • RT? • O(n3) • Is there a better way to build? Is there a better way to build the table? 13 24 32 58 6 0 1 2 3 0 1 2 3 • Yes • In O(n2) using Dynamic Programming • Start with the diagonal and then fill the adjacent entries of already filled entries Is there a better way to build the table? 14 24 32 58 6 0 1 2 3 0 24 ? 1 32 2 58 3 6 • Yes. • In O(n2) using Dynamic Programming • Start with the diagonal and then fill the adjacent entries of already filled entries Is there a better way to build the table? 15 24 32 58 6 0 1 2 3 0 24 ? 1 32 2 58 3 6 • Yes. • In O(n2) using Dynamic Programming • Start with the diagonal and then fill the adjacent entries of already filled entries Is there a better way to build the table? 16 24 32 58 6 0 1 2 3 0 24 24 1 32 2 58 3 6 • Yes. • In O(n2) using Dynamic Programming • Start with the diagonal and then fill the adjacent entries of already filled entries Is there a better way to build the table? 17 24 32 58 6 0 1 2 3 0 24 24 1 32 ? 2 58 3 6 • Yes. • In O(n2) using Dynamic Programming • Start with the diagonal and then fill the adjacent entries of already filled entries Is there a better way to build the table? 18 24 32 58 6 0 1 2 3 0 24 24 1 32 ? 2 58 3 6 • Yes. • In O(n2) using Dynamic Programming • Start with the diagonal and then fill the adjacent entries of already filled entries Is there a better way to build the table? 19 24 32 58 6 0 1 2 3 0 24 24 1 32 32 2 58 3 6 • Yes. • In O(n2) using Dynamic Programming • Start with the diagonal and then fill the adjacent entries of already filled entries Is there a better way to build the table? 20 24 32 58 6 0 1 2 3 0 24 24 ? 1 32 32 2 58 6 3 6 • Yes. • In O(n2) using Dynamic Programming • Start with the diagonal and then fill the adjacent entries of already filled entries Is there a better way to build the table? 21 24 32 58 6 0 1 2 3 0 24 24 ? 1 32 32 2 58 6 3 6 • Yes. • In O(n2) using Dynamic Programming • Start with the diagonal and then fill the adjacent entries of already filled entries Is there a better way to build the table? 22 24 32 58 6 0 1 2 3 0 24 24 24 1 32 32 2 58 6 3 6 • Yes. • In O(n2) using Dynamic Programming • Start with the diagonal and then fill the adjacent entries of already filled entries Is there a better way to build the table? 23 24 32 58 6 0 1 2 3 0 24 24 24 6 1 32 32 6 2 58 6 3 6 • Yes. • In O(n2) using Dynamic Programming • Start with the diagonal and then fill the adjacent entries of already filled entries So far we have… 24 • Two approaches • Denote the complexity of an RMQ data structure by • p(n) is pre-processing time • q(n) is query time • Our menu of structures for RMQ: • with no preprocessing • with preprocessing • These are two ends of the spectrum • Is there a trade-off or a better solution? Look at the problem again… CS 6301 IDSA 25 24 32 58 6 94 86 16 2 99 28 39 40 64 13 70 47 i j Look at the problem again… CS 6301 IDSA 26 24 32 58 6 94 86 16 2 99 28 39 40 64 13 70 47 i j Look at the problem again… CS 6301 IDSA 27 24 32 58 6 94 86 16 2 99 28 39 40 64 13 70 47 i jmi n Need another approach We don’t want to search all the elements… CS 6301 IDSA 28 24 32 58 6 94 86 16 2 99 28 39 40 64 13 70 47 i jmi n Block partition approach Partition the array into blocks of b elements CS 6301 IDSA 29 24 32 58 6 94 86 16 2 99 28 39 40 64 13 70 47 b = 4 Block partition approach Partition the array into blocks of b elements Find the min of each block and store in another array (size = n/b) CS 6301 IDSA 30 6 2 28 13 6 32 58 24 94 86 16 2 99 28 39 40 64 47 70 13 b = 4 Block partition approach Partition the array into blocks of b elements Find the min of each block and store it an another array (size = n/b) RMQ(i,j) = ? CS 6301 IDSA 31 6 2 28 13 6 32 58 24 94 86 16 2 99 28 39 40 64 47 70 13 b = 4 i j Block partition approach Partition the array into blocks of b elements Find the min of each block and store it an another array (size = n/b) RMQ(i,j) = ? CS 6301 IDSA 32 6 2 28 13 6 32 58 24 94 86 16 2 99 28 39 40 64 47 70 13 b = 4 i j Block partition approach Partition the array into blocks of b elements Find the min of each block and store it in another array (size = n/b) RMQ(i,j) = ? CS 6301 IDSA 33 6 2 28 13 6 32 58 24 94 86 16 2 99 28 39 40 64 47 70 13 b = 4 i j Block partition approach Partition the array into blocks of b elements Find the min of each block and store it an another array (size = n/b) RMQ(i,j) = ? CS 6301 IDSA 34 6 2 28 13 6 32 58 24 94 86 16 2 99 28 39 40 64 47 70 13 b = 4 i j Block partition approach Partition the array into blocks of b elements Find the min of each block and store it an another array (size = n/b) RMQ(i,j) = ? CS 6301 IDSA 35 6 2 28 13 6 32 58 24 94 86 16 2 99 28 39 40 64 47 70 13 b = 4 i j Block partition approach Partition the array into blocks of b elements Find the min of each block and store it an another array (size = n/b) RMQ(i,j) = ? CS 6301 IDSA 36 6 2 28 13 6 32 58 24 94 86 16 2 99 28 39 40 64 47 70 13 b = 4 i j Block partition approach Partition the array into blocks of b elements Find the min of each block and store it an another array (size = n/b) RMQ(i,j) = ? CS 6301 IDSA 37 6 2 28 13 6 32 58 24 94 86 16 2 99 28 39 40 64 47 70 13 b = 4 i j Analysis of block partition approach Preprocessing time p(n): • O(b) to find minimum on each of (n/b) blocks • p(n) = O(n) Query time q(n) • O(1) to find blocks of i and j • O(b) to scan inside blocks of i and j • O(n/b) to scan minima of each block between blocks of i and j • q(n) = O(b + n/b) CS 6301 IDSA 38 6 2 28 13 6 32 58 24 94 86 16 2 99 28 39 40 64 47 70 13 b = 4 i j Analyze query time O(b + n/b) • If b = 1 or b = n, then no preprocessing requires • Choose b to minimize b + n/b • Optimal value of b = √n • q(n) = O(√n + √n) = O(√n) CS 6301 IDSA 39 Our Menu • No preprocessing: • Block partition: • Full preprocessing: • Can we add something better? CS 6301 IDSA 40 Revisit preprocessing full table approach • Is it necessary to preprocess all the ranges of the given array? • Goal: preprocess less number of ranges yet query in O(1) time CS 6301 IDSA 41 Revisit preprocessing full table • Is it necessary to preprocess all the ranges of the given array? 42 24 32 58 6 94 86 16 20 0 1 2 3 4 5 6 7 0 24 24 24 6 6 6 6 6 1 32 32 6 6 6 6 6 2 58 6 6 6 6 6 3 6 6 6 6 6 4 94 86 16 16 5 86 16 16 6 16 16 7 20 Revisit preprocessing full table • Is it necessary to preprocess all the ranges of the given array? 43 24 32 58 6 94 86 16 20 0 1 2 3 4 5 6 7 0 24 24 24 6 6 6 6 6 1 32 32 6 6 6 6 ? 2 58 6 6 6 6 6 3 6 6 6 6 6 4 94 86 16 16 5 86 16 16 6 16 16 7 20 Revisit preprocessing full table • Is it necessary to preprocess all the ranges of the given array? 44 24 32 58 6 94 86 16 20 0 1 2 3 4 5 6 7 0 24 24 24 6 6 1 32 32 6 6 ? 2 58 6 6 6 3 6 6 6 6 4 94 86 16 16 5 86 16 16 6 16 16 7 20 Revisit preprocessing full table • Is it necessary to preprocess all the ranges of the given array? 45 24 32 58 6 94 86 16 20 0 1 2 3 4 5 6 7 0 24 24 24 6 6 1 32 32 6 6 ? 2 58 6 6 6 3 6 6 6 6 4 94 86 16 16 5 86 16 16 6 16 16 7 20 Revisit preprocessing full table • Is it necessary to preprocess all the ranges of the given array? • Which ranges to skip? • Need to skip enough numbers to get an asymptotically lower bound than O(n2) 46 24 32 58 6 94 86 16 20 0 1 2 3 4 5 6 7 0 24 24 24 6 6 6 6 6 1 32 32 6 6 6 6 6 2 58 6 6 6 6 6 3 6 6 6 6 6 4 94 86 16 16 5 86 16 16 6 16 16 7 20 4 2 3 1 5 6 7 8 Revisit preprocessing full table • Is it necessary to preprocess all the ranges of the given array? • Which ranges to skip? • Need to skip enough numbers to get an asymptotically lower bound than O(n2) 47 24 32 58 6 94 86 16 20 0 1 2 3 4 5 6 7 0 24 24