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