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 hy
id 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 hy
id 1 and Fischer-Heun approaches.
Generate input a
ays 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 a
ay A and two integers i and j
Output: Find the smallest element among A[i]…A[j]
CS 6301 IDSA 2
XXXXXXXXXX2
RMQ Problem
Input: An a
ay A and two integers i and j
Output: Find the smallest element among A[i]…A[j]
CS 6301 IDSA 3
XXXXXXXXXX2
i j
RMQ Problem
Input: An a
ay A and two integers i and j
Output: Find the smallest element among A[i]…A[j]
CS 6301 IDSA 4
XXXXXXXXXX2
i j
RMQ Problem
Input: An a
ay A and two integers i and j
Output: Find the smallest element among A[i]…A[j]
CS 6301 IDSA 5
XXXXXXXXXX2
i mi
n
j
RMQ Problem
Input: An a
ay A and two integers i and j
Output: Find the smallest element among A[i]…A[j]
CS 6301 IDSA 6
XXXXXXXXXX2
i j
RMQ Problem
Input: An a
ay A and two integers i and j
Output: Find the smallest element among A[i]…A[j]
CS 6301 IDSA 7
XXXXXXXXXX2
i j
RMQ Problem
Input: An a
ay A and two integers i and j
Output: Find the smallest element among A[i]…A[j]
CS 6301 IDSA 8
XXXXXXXXXX2
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
XXXXXXXXXX
0 1 2 3
0
1 6
2
3
i j
Preprocess the all possible queries
CS 6301 IDSA 12
XXXXXXXXXX
0 1 2 3
XXXXXXXXXX
XXXXXXXXXX
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
XXXXXXXXXX
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
XXXXXXXXXX
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
XXXXXXXXXX
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
XXXXXXXXXX
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
XXXXXXXXXX
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
XXXXXXXXXX
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
XXXXXXXXXX
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
XXXXXXXXXX
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
XXXXXXXXXX
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
XXXXXXXXXX
0 1 2 3
XXXXXXXXXX
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
XXXXXXXXXX
0 1 2 3
XXXXXXXXXX
XXXXXXXXXX
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
XXXXXXXXXX XXXXXXXXXX70 47
i j
Look at the problem again…
CS 6301 IDSA 26
XXXXXXXXXX XXXXXXXXXX70 47
i j
Look at the problem again…
CS 6301 IDSA 27
XXXXXXXXXX XXXXXXXXXX70 47
i jmi
n
Need another approach
We don’t want to search all the elements…
CS 6301 IDSA 28
XXXXXXXXXX XXXXXXXXXX70 47
i jmi
n
Block partition approach
Partition the a
ay into blocks of b elements
CS 6301 IDSA 29
XXXXXXXXXX XXXXXXXXXX70 47
= 4
Block partition approach
Partition the a
ay into blocks of b elements
Find the min of each block and store in another a
ay (size = n
)
CS 6301 IDSA 30
XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX70 13
= 4
Block partition approach
Partition the a
ay into blocks of b elements
Find the min of each block and store it an another a
ay (size = n
)
RMQ(i,j) = ?
CS 6301 IDSA 31
XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX70 13
= 4
i j
Block partition approach
Partition the a
ay into blocks of b elements
Find the min of each block and store it an another a
ay (size = n
)
RMQ(i,j) = ?
CS 6301 IDSA 32
XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX70 13
= 4
i j
Block partition approach
Partition the a
ay into blocks of b elements
Find the min of each block and store it in another a
ay (size = n
)
RMQ(i,j) = ?
CS 6301 IDSA 33
XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX70 13
= 4
i j
Block partition approach
Partition the a
ay into blocks of b elements
Find the min of each block and store it an another a
ay (size = n
)
RMQ(i,j) = ?
CS 6301 IDSA 34
XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX70 13
= 4
i j
Block partition approach
Partition the a
ay into blocks of b elements
Find the min of each block and store it an another a
ay (size = n
)
RMQ(i,j) = ?
CS 6301 IDSA 35
XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX70 13
= 4
i j
Block partition approach
Partition the a
ay into blocks of b elements
Find the min of each block and store it an another a
ay (size = n
)
RMQ(i,j) = ?
CS 6301 IDSA 36
XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX70 13
= 4
i j
Block partition approach
Partition the a
ay into blocks of b elements
Find the min of each block and store it an another a
ay (size = n
)
RMQ(i,j) = ?
CS 6301 IDSA 37
XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX70 13
= 4
i j
Analysis of block partition approach
Preprocessing time p(n):
• O(b) to find minimum on each of (n
) 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
) to scan minima of each block between blocks of i and j
• q(n) = O(b + n
)
CS 6301 IDSA 38
XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX70 13
= 4
i j
Analyze query time O(b + n
)
• If b = 1 or b = n, then no preprocessing requires
• Choose b to minimize b + n
• 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 a
ay?
• 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 a
ay?
42
XXXXXXXXXX20
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
6 16 16
7 20
Revisit preprocessing full table
• Is it necessary to preprocess all the ranges of the given a
ay?
43
XXXXXXXXXX20
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX ?
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
6 16 16
7 20
Revisit preprocessing full table
• Is it necessary to preprocess all the ranges of the given a
ay?
44
XXXXXXXXXX20
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX ?
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
6 16 16
7 20
Revisit preprocessing full table
• Is it necessary to preprocess all the ranges of the given a
ay?
45
XXXXXXXXXX20
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX ?
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
6 16 16
7 20
Revisit preprocessing full table
• Is it necessary to preprocess all the ranges of the given a
ay?
• Which ranges to skip?
• Need to skip enough numbers to get an asymptotically lower bound than O(n2)
46
XXXXXXXXXX20
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
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 a
ay?
• Which ranges to skip?
• Need to skip enough numbers to get an asymptotically lower bound than O(n2)
47
XXXXXXXXXX20
XXXXXXXXXX
0 24 24