1. What is the use of the bin data structure?
a) to have efficient insertion
b) to have efficient deletion
c) to have efficient region query
d) to have efficient traversal
Answer: c
Explanation:
Bin data structure allows us to have efficient region queries. A frequency of bin is increased by one each time a data point falls into a bin.
2. Bin is an example of a range query data structure.
a) true
b) false
Answer: a
Explanation:
Bin is an example of a range query data structure. It is because it efficiently answers any number of queries on any subset of the input.
3. What is the worst case time complexity of query operation(n is the no. of candidates)?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Answer: b
Explanation:
The worst case in a bin query occurs when all the candidates are concentrated in one bin. So in this case the time complexity is O(n).
4. What is the worst case time complexity of delete operation(n is the no. of candidates)?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Answer: b
Explanation:
The worst case in a bin delete operation occurs when all the candidates are concentrated in one bin. So in this case the time complexity is O(n).
5. What is the worst case time complexity of insertion operation(n =no. of candidates)?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Answer: a
Explanation:
The worst case in a bin insert operation occurs when all the candidates are concentrated in one bin. So in this case the time complexity is O(1).
6. What is computational geometry?
a) study of geometry using a computer
b) study of geometry
c) study of algorithms
d) study of algorithms related to geometry
Answer: d
Explanation:
Computational geometry deals with the study of algorithms which can be expressed in terms of geometry. Bin data structure is an example of it.
7. What will be the time complexity of query operation if all the candidates are evenly spaced so that each bin has constant no. of candidates? (k = number of bins query rectangle intersects)
a) O(1)
b) O(k)
c) O(k2)
d) O(log k)
Answer: b
Explanation:
The process of query becomes faster in a case when the number of candidates are equally distributed among the bins. In such a case the query operation becomes O(k).
8. What will be the time complexity of delete operation if all the candidates are evenly spaced so that each bin has constant no. of candidates? (m = number of bins intersecting candidate intersects)
a) O(1)
b) O(m)
c) O(m2)
d) O(log m)
Answer: b
Explanation:
The process of deletion becomes faster in a case when the number of candidates are equally distributed among the bins. In such a case the query operation becomes O(m). It is practically slower than insertion in this case.
9. What will be the time complexity of insertion operation if all the candidates are evenly spaced so that each bin has constant no. of candidates? (m = number of bins intersecting candidate intersects)
a) O(1)
b) O(m)
c) O(m2)
d) O(log m)
Answer: b
Explanation:
The process of insertion becomes faster in the case when the number of candidates are equally distributed among the bins. In such a case the query operation becomes O(m). It is practically faster than deletion in this case.
10. Efficiency of bin depends upon ___________
a) size of query and candidates
b) location of query and candidates
c) location and size of query and candidates
d) depends on the input
Answer: c
Explanation:
Efficiency of bin depends upon the location and size of query and candidates. It is similar to that of a hash table.
11. Bigger the query rectangle the better is the query efficiency.
a) true
b) false
Answer: b
Explanation:
Efficiency of bin depends upon the location and size of query and candidates. Also, the smaller is the query rectangle the better is the query efficiency.
12. In the Union/Find algorithm, the ranks of the nodes on a path will increase monotonically from?
a) leaf to root
b) root to node
c) root to leaf
d) left subtree to right subtree
Answer: a
Explanation:
One of the lemmas state that, in the Union/Find algorithm, the ranks of the nodes on a path will increase monotonically from leaf to root.
13. How many strategies are followed to solve a dynamic equivalence problem?
a) 1
b) 2
c) 3
d) 4
Answer: b
Explanation:
There are two strategies involved to solve a dynamic equivalence problem- executing find instruction in worst-case time and executing union instruction in worst-case time.
14. What is the total time spent for N-1 merges in a dynamic equivalence problem?
a) O(N)
b) O(log N)
c) O(N log N)
d) O(M log N)
Answer: c
Explanation:
The total time spent for N-1 merges in a dynamic equivalence problem is mathematically found to be O(N log N).
15. What is the condition for an equivalence relation if two cities are related within a country?
a) the two cities should have a one-way connection
b) the two cities should have a two-way connection
c) the two cities should be in different countries
d) no equivalence relation will exist between two cities
Answer: b
Explanation:
If the two towns are in the same country and have a two-way road connection between them, it satisfies equivalence property.
16. Reversal algorithm and juggling algorithm for array rotation have the same time complexity.
a) True
b) False
Answer: a
Explanation:
Time complexity of juggling algorithm is O(n) which like that of reversal algorithm. They also have the same space complexity
