Design And Analysis Of Algorithms Set 6
On This Page
This set of Design and Analysis of Algorithms Multiple Choice Questions & Answers (MCQs) focuses on Design And Analysis Of Algorithms Set 6
Q1 | What will be the cross product of the vectors 2i + 3j + k and 3i + 2j + k?
- i + 2j + k
- 2i + 3j + k
- i + j – 5k
- 2i – j – 5k
Q2 | Which of the following operation will give a vector that is perpendicular to both vectors a and b?
- a x b
- a.b
- b x a
- both a x b and b x a
Q3 | is a method of constructing a smallest polygon out of n given points.
- closest pair problem
- quick hull problem
- path compression
- union-by-rank
Q4 | What is the other name for quick hull problem?
- convex hull
- concave hull
- closest pair
- path compression
Q5 | How many approaches can be applied to solve quick hull problem?
- 1
- 2
- 3
- 4
Q6 | What is the average case complexity of a quick hull algorithm?
- o(n)
- o(n log n)
- o(n2)
- o(log n)
Q7 | What is the worst case complexity of quick hull?
- o(n)
- o(n log n)
- o(n2)
- o(log n)
Q8 | What does the following diagram depict?
- closest pair
- convex hull
- concave hull
- path compression
Q9 | Which of the following statement is not related to quickhull algorithm?
- finding points with minimum and maximum coordinates
- dividing the subset of points by a line
- eliminating points within a formed triangle
- finding the shortest distance between two points
Q10 | The quick hull algorithm runs faster if the input uses non- extreme points.
- true
- false
Q11 | To which type of problems does quick hull belong to?
- numerical problems
- computational geometry
- graph problems
- string problems
Q12 | Which of the following algorithms is similar to a quickhull algorithm?
- merge sort
- shell sort
- selection sort
- quick sort
Q13 | Who formulated quick hull algorithm?
- eddy
- andrew
- chan
- graham
Q14 | The time is taken to find the ‘n’ points that lie in a convex quadrilateral is?
- o(n)
- o(n log n)
- o(n2)
- o(log n)
Q15 | Chan’s algorithm is used for computing
- closest distance between two points
- convex hull
- area of a polygon
- shortest path between two points
Q16 | What is the running time of Chan’s algorithm?
- o(log n)
- o(n log n)
- o(n log h)
- o(log h)
Q17 | Who formulated Chan’s algorithm?
- timothy
- kirkpatrick
- frank nielsen
- seidel
Q18 | The running time of Chan’s algorithm is obtained from combining two algorithms.
- true
- false
Q19 | Which of the following is called the “ultimate planar convex hull algorithm”?
- chan’s algorithm
- kirkpatrick-seidel algorithm
- gift wrapping algorithm
- jarvis algorithm
Q20 | Which of the following algorithms is the simplest?
- chan’s algorithm
- kirkpatrick-seidel algorithm
- gift wrapping algorithm
- jarvis algorithm
Q21 | What is the running time of Hershberger algorithm?
- o(log n)
- o(n log n)
- o(n log h)
- o(log h)
Q22 | Which of the following statements is not a part of Chan’s algorithm?
- eliminate points not in the hull
- recompute convex hull from scratch
- merge previously calculated convex hull
- reuse convex hull from the previous iteration
Q23 | Which of the following factors account more to the cost of Chan’s algorithm?
- computing a single convex hull
- locating points that constitute a hull
- computing convex hull in groups
- merging convex hulls
Q24 | Chan’s algorithm can be used to compute the lower envelope of a trapezoid.
- true
- false