Explore topic-wise InterviewSolutions in .

Right option is (a) true

The explanation is: An extension of Chan’s ALGORITHM can be used for proving solutions to complex problems like computing the LOWER ENVELOPE L(S) where S is a set of ‘N’ line segments in a TRAPEZOID.

The correct answer is (C) COMPUTING CONVEX hull in groups

Easiest EXPLANATION - The majority of the cost of the algorithm lies in the pre-processing (i.e.) computing convex hull in groups. To reduce cost, we reuse convex hulls from previous ITERATIONS.

The correct choice is (b) recompute CONVEX hull from scratch

The best I can explain: Chan’s algorithm implies that the convex hulls of LARGER points can be arrived at by merging previously CALCULATED convex hulls. It makes the algorithm simpler instead of recomputing every TIME from scratch.

The correct ANSWER is (b) O(n log n)

Easy EXPLANATION - Hershberger’s algorithm is an output sensitive algorithm whose RUNNING time was ORIGINALLY O(n log n). He USED Chan’s algorithm to speed up to O(n log h) where h is the number of edges.

Correct choice is (a) CHAN’s algorithm

Easiest explanation - Chan’s algorithm is very practical for moderate SIZED problems WHEREAS Kirkpatrick-Seidel algorithm is not. Although, they both have the same running time. Gift wrapping algorithm is a non-output sensitive algorithm and has a longer running time.

Correct choice is (b) Kirkpatrick-Seidel algorithm

Easy explanation - Kirkpatrick-Seidel algorithm is called as the ultimate PLANAR CONVEX hull algorithm. Its RUNNING time is the same as that of Chan’s algorithm (i.e.) O(n LOG h).

The correct CHOICE is (a) True

Best explanation: The O(N log h) running time of Chan’s ALGORITHM is obtained by combining the running time of Graham’s scan [O(n log n)] and JARVIS MATCH [O(nh)].

The correct answer is (a) Timothy

Best explanation: CHAN’s ALGORITHM was formulated by Timothy Chan. Kirkpatrick and Seidel formulated the Kirkpatrick-Seidel algorithm. FRANK Nielsen developed a paradigm RELATING to Chan’s algorithm.

Right choice is (c) O(n LOG h)

For explanation: The RUNNING TIME of Chan’s algorithm is calculated to be O(n log h) where h is the number of VERTICES of the convex hull.

Correct choice is (b) Convex hull

The best I can EXPLAIN: Chan’s algorithm is an output-sensitive algorithm USED to compute the convex hull set of n POINTS in a 2D or 3D space. CLOSEST pair algorithm is used to compute the closest distance between two points.

Correct OPTION is (a) EDDY

The best I can explain: Eddy formulated quick HULL ALGORITHM. Graham invented graham SCAN. Andrew formulated Andrew’s algorithm and Chan invented Chan’s algorithm.

Right option is (d) quick sort

Explanation: Quickhull ALGORITHM is SIMILAR to a quick sort algorithm with respect to the run time AVERAGE case and WORST case efficiencies.

Correct option is (d) FINDING the shortest distance between two POINTS

Easy explanation - Finding the shortest distance between two points belongs to closest pair algorithm while the REST is quickhull.

The correct answer is (b) CONVEX hull

Easiest EXPLANATION - The above diagram is a DEPICTION of convex hull, also KNOWN as quick hull, since it encloses n points into a convex POLYGON.

Right option is (c) O(N^2)

Best explanation: The WORST CASE complexity of quickhull algorithm using divide and conquer approach is MATHEMATICALLY FOUND to be O(N^2).

Correct choice is (b) O(N log N)

For EXPLANATION: The average case complexity of quickhull ALGORITHM USING DIVIDE and conquer approach is mathematically FOUND to be O(N log N).

The correct option is (b) 2

To explain: Most commonly, TWO approaches are adopted to solve quick HULL problem- brute force APPROACH and divide and CONQUER approach.

Correct option is (a) CONVEX hull

Best EXPLANATION: The other NAME for quick hull problem is convex hull problem WHEREAS the closest pair problem is the problem of finding the closest distance between TWO points.

The correct option is (b) quick HULL problem

Easy EXPLANATION - Quick hull is a METHOD of constructing a smallest CONVEX polygon out of n given POINTS in a plane.

Right choice is (d) both a X b and b x a

Best EXPLANATION: The resultant VECTOR from the CROSS product of two VECTORS is perpendicular to the plane containing both vectors. So both a x b and b x a will give a vector that is perpendicular to both vectors a and b.

The correct answer is (c) i + J – 5k

The best EXPLANATION: We can FIND the cross PRODUCT of the GIVEN vectors by solving the determinant.

Right answer is (b) PERPENDICULAR to the plane containing both VECTORS

The BEST EXPLANATION: The RESULTANT vector from the cross product of two vectors is perpendicular to the plane containing both vectors. In other words, it should be perpendicular to both the vectors involved in the cross product.

The CORRECT answer is (c) AREA of parallelogram

Best explanation: CROSS product of TWO vectors can be used to find the area of parallelogram. For this, we NEED to consider the vectors as the adjacent sides of the parallelogram.

The correct ANSWER is (d) – (b x a)

Easiest EXPLANATION - The vector PRODUCT a x b is equal to – (b x a). The MINUS sign shows that these vectors have opposite DIRECTIONS.

Correct ANSWER is (a) true

The best I can explain: The concept of CROSS PRODUCT FIND its APPLICATION in the field of computer graphics. It can be used to find the winding of polygon about a point.

The correct answer is (c) |a|.|B| sin(θ)

Best explanation: The GENERAL formula for finding the MAGNITUDE of cross product of TWO vectors is |a|.|b| sin(θ). Its DIRECTION is perpendicular to the plane containing a and b.

The correct CHOICE is (c) |a|.|b| sin(180)

To explain: The resultant of CROSS product of 2 parallel VECTORS is always 0 as the angle between them is 0 or 180 degrees. So the answer is |a|.|b| sin(180).

Right option is (b) vector product

The best EXPLANATION: CROSS product is ALSO known as a vector product. It is a MATHEMATICAL operation that is PERFORMED on 2 vectors in 3D plane.

Correct OPTION is (C) 2 vectors

Easiest EXPLANATION - CROSS product is a mathematical OPERATION that is performed on 2 vectors in a 3D plane. It has many applications in computer programming and physics.

The correct choice is (b) Divide and CONQUER

The best I can explain: The above diagram depicts the IMPLEMENTATION of divide and conquer. The problem is divided into SUB PROBLEMS and are separated by a line.

The CORRECT answer is (c) p2 and p3

The explanation is: From symmetry, we determine that the CLOSEST pair is p2 and p3. But the exact calculations have to be done USING Euclid’s algorithm.

Correct ANSWER is (c) O(N LOG N)

The BEST EXPLANATION: The optimal TIME for solving using a divide and conquer approach is mathematically found to be O(N log N).

Right option is (b) Brute force

The EXPLANATION is: Brute force is a STRAIGHT forward approach to solve CRITICAL problems. Here, we use brute force technique to find the CLOSEST distance between p1 and P2.

Right answer is (a) EUCLIDEAN distance

Easy explanation - The basic operation of CLOSEST pair ALGORITHM is Euclidean distance and its formula is given by d=√(xi-xj)^2+(yi-yj)^2.

The correct choice is (d) i
Easiest explanation - To avoid COMPUTING the DISTANCE between the same pair of POINTS TWICE, we consider only the pair of points (pi, pj) for which i

Right answer is (c) O(N^2)

Easy EXPLANATION - The efficiency of closest pair algorithm by BRUTE force TECHNIQUE is MATHEMATICALLY found to be O(N^2).

The CORRECT answer is (a) Brute force

For explanation: Brute force is a STRAIGHT forward approach that SOLVES CLOSEST pair problem USING that algorithm.

The CORRECT answer is (a) computational geometry

For EXPLANATION: Closest pair PROBLEM ARISES in two most important AREAS- computational geometry and operational research.

The correct choice is (B) -1/2

The BEST explanation: For two lines to be perpendicular the PRODUCT of their slopes should be EQUAL to -1. So as the slope of given line is 2 so the slope of line perpendicular to it will be -1/2.

Correct CHOICE is (b) fabs()

EASIEST explanation - In C++ the ABSOLUTE value of an argument can be found by using the FUNCTION fabs(). It is available under the header file math.h.

Right ANSWER is (c) (68/25,-49/25)

The EXPLANATION is: The foot of PERPENDICULAR can be found by equating the DISTANCE between the two points and the distance between point and line. This is found to be (68/25,-49/25).

The CORRECT OPTION is (b) -2

Easy EXPLANATION - The slope of a line given by the equation AX + by + c=0 has the slope of -a/b. So the slope of the given line will be -2.