Design And Analysis Of Algorithms Set 6 MCQs

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