1. Quick sort uses join operation rather than merge operation.
Correct : A. true
2. How many sub arrays does the quick sort algorithm divide the entire array into?
Correct : B. two
3. Which is the worst method of choosing a pivot element?
Correct : A. first element as pivot
4. The shortest distance between a line and a point is achieved when?
Correct : A. a line is drawn at 90 degrees to the given line from the given point
5. What is the shortest distance between the line given by -2x + 3y + 4 = 0 and the point (5,6)?
Correct : D. 3.3 units
6. What is the distance between the lines 3x- 4y+7=0 and 3x-4y+5=0?
Correct : D. 0.4 unit
7. What will be the slope of the line given by ax + by + c = 0?
Correct : A. -a/b
8. What will be the slope of the line given by 10x + 5y + 8=0?
Correct : B. -2
9. Which of the following areas do closest pair problem arise?
Correct : A. computational geometry
10. What is the runtime efficiency of using brute force technique for the closest pair problem?
Correct : C. o(n2)
11. The most important condition for which closest pair is calculated for the points (pi, pj) is?
Correct : D. i<j
12. What is the basic operation of closest pair algorithm using brute force technique?
Correct : A. euclidean distance
13. Which of the following is similar to Euclidean distance?
Correct : B. pythagoras metric
14. Which of the following strategies does the following diagram depict?
Correct : B. brute force
15. Manhattan distance is an alternative way to define a distance between two points.
Correct : A. true
16. What is the optimal time required for solving the closest pair problem using divide and conquer approach?
Correct : C. o(n log n)
17. In divide and conquer, the time is taken for merging the subproblems is?
Correct : B. o(n log n)
18. The optimal time obtained through divide and conquer approach using merge sort is the best case efficiency.
Correct : A. true
19. Which of the following strategies does the following diagram depict?
Correct : B. divide and conquer
20. Which of the points are closer to each other?
Correct : C. p2 and p3
21. Cross product is a mathematical operation performed between
Correct : C. 2 vectors
22. Cross product is also known as?
Correct : B. vector product
23. The concept of cross product is applied in the field of computer graphics.
Correct : A. true
24. Which of the following equals the a x b ( a and b are two vectors)?
Correct : D. – (b x a)
25. Cross product of two vectors can be used to find?
Correct : C. area of parallelogram
26. What will be the cross product of the vectors 2i + 3j + k and 3i + 2j + k?
Correct : C. i + j – 5k
27. What will be the cross product of the vectors 2i + 3j + k and 6i + 9j + 3k?
Correct : C. 0
28. Which of the following operation will give a vector that is perpendicular to both vectors a and b?
Correct : D. both a x b and b x a
29. is a method of constructing a smallest polygon out of n given points.
Correct : B. quick hull problem
30. What is the other name for quick hull problem?
Correct : A. convex hull
31. How many approaches can be applied to solve quick hull problem?
Correct : B. 2
32. What is the average case complexity of a quick hull algorithm?
Correct : B. o(n log n)
33. What is the worst case complexity of quick hull?
Correct : C. o(n2)
34. What does the following diagram depict?
Correct : B. convex hull
35. Which of the following statement is not related to quickhull algorithm?
Correct : D. finding the shortest distance between two points
36. The quick hull algorithm runs faster if the input uses non- extreme points.
Correct : A. true
37. To which type of problems does quick hull belong to?
Correct : B. computational geometry
38. Which of the following algorithms is similar to a quickhull algorithm?
Correct : D. quick sort
39. Who formulated quick hull algorithm?
Correct : A. eddy
40. The time is taken to find the ‘n’ points that lie in a convex quadrilateral is?
Correct : A. o(n)
41. Chan’s algorithm is used for computing
Correct : B. convex hull
42. What is the running time of Chan’s algorithm?
Correct : C. o(n log h)
43. Who formulated Chan’s algorithm?
Correct : A. timothy
44. The running time of Chan’s algorithm is obtained from combining two algorithms.
Correct : A. true
45. Which of the following is called the “ultimate planar convex hull algorithm”?
Correct : B. kirkpatrick-seidel algorithm
46. Which of the following algorithms is the simplest?
Correct : A. chan’s algorithm
47. What is the running time of Hershberger algorithm?
Correct : B. o(n log n)
48. Which of the following statements is not a part of Chan’s algorithm?
Correct : B. recompute convex hull from scratch
49. Which of the following factors account more to the cost of Chan’s algorithm?
Correct : C. computing convex hull in groups
50. Chan’s algorithm can be used to compute the lower envelope of a trapezoid.
Correct : A. true
51. Which of the following is false in the case of a spanning tree of a graph G?
Correct : D. it can be either cyclic or acyclic
52. Every graph has only one minimum spanning tree.
Correct : B. false
53. Consider a complete graph G with 4 vertices. The graph G has spanning trees.
Correct : C. 16
54. The travelling salesman problem can be solved using
Correct : B. a minimum spanning tree
55. Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true?
Correct : C. graph m has 3 distinct minimum spanning trees, each of cost 2
56. Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false?
Correct : C. no minimum spanning tree contains ab
57. If all the weights of the graph are positive, then the minimum spanning tree of the graph is a minimum cost subgraph.
Correct : A. true
58. Which of the following is not the algorithm to find the minimum spanning tree of the given graph?
Correct : D. bellman–ford algorithm
59. Which of the following is false?
Correct : D. removing one edge from the spanning tree will not make the graph disconnected
60. Kruskal’s algorithm is used to
Correct : A. find minimum spanning tree
61. Kruskal’s algorithm is a
Correct : C. greedy algorithm
62. What is the time complexity of Kruskal’s algorithm?
Correct : B. o(e log v)
63. Consider the following graph. Using Kruskal’s algorithm, which edge will be selected first?
Correct : C. be
64. Which of the following edges form minimum spanning tree on the graph using kruskals algorithm?
Correct : A. (b-e)(g-e)(e-f)(d-f)
65. Which of the following is false about the Kruskal’s algorithm?
Correct : C. it can accept cycles in the mst
66. Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm.
Correct : B. false
67. Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure.
Correct : D. s2 is true but s1 is false
68. Which of the following is true?
Correct : A. prim’s algorithm initialises with a vertex
69. Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?
72. Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.
Correct : A. true
73. Prim’s algorithm can be efficiently implemented using for graphs with greater density.
Correct : A. d-ary heap
74. Which of the following is false about Prim’s algorithm?
Correct : B. it constructs mst by selecting edges in increasing order of their weights
75. Which of the following is the most commonly used data structure for implementing Dijkstra’s Algorithm?
Correct : D. min priority queue
76. How many priority queue operations are involved in Dijkstra’s Algorithm?
Correct : B. 3
77. How many times the insert and extract min operations are invoked per vertex?
Correct : A. 1
78. The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be equal to
Correct : B. total number of edges
79. What is running time of Dijkstra’s algorithm using Binary min- heap method?
Correct : D. o(elogv)
80. The running time of Bellmann Ford algorithm is lower than that of Dijkstra’s Algorithm.
Correct : B. false
81. Dijkstra’s Algorithm run on a weighted, directed graph G={V,E} with non-negative weight function w and source s, terminates with d[u]=delta(s,u) for all vertices u in V.
Correct : A. true
82. Dijkstra’s Algorithm is the prime example for
Correct : A. greedy algorithm
83. Bellmann ford algorithm provides solution for problems.
Correct : D. single source shortest path
84. Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not.
Correct : A. true
85. How many solution/solutions are available for a graph having negative weight cycle?
Correct : C. no solution
86. What is the running time of Bellmann Ford Algorithm?
Correct : D. o(ve)
87. How many times the for loop in the Bellmann Ford Algorithm gets executed?
Correct : B. v-1
88. Dijikstra’s Algorithm is more efficient than Bellmann Ford Algorithm.
Correct : A. true
89. What is the basic principle behind Bellmann Ford Algorithm?
Correct : D. relaxation
90. Bellmann Ford Algorithm can be applied for
Correct : C. directed and weighted graphs
91. Bellmann Ford algorithm was first proposed by
Correct : B. alfonso shimbe
92. Bellmann Ford Algorithm is an example for
Correct : A. dynamic programming
93. A graph is said to have a negative weight cycle when?
Correct : C. the total weight of the graph is negative
94. Floyd Warshall’s Algorithm is used for solving
Correct : A. all pair shortest path problems
95. Floyd Warshall’s Algorithm can be applied on
Correct : C. directed graphs
96. What is the running time of the Floyd Warshall Algorithm?
Correct : D. theta(v3)
97. What approach is being followed in Floyd Warshall Algorithm?
Correct : B. dynamic programming
98. Floyd Warshall Algorithm can be used for finding
Correct : D. transitive closure
99. What procedure is being followed in Floyd Warshall Algorithm?