Quiznetik

Design and Analysis of Algorithms | Set 2

1. Quick sort uses join operation rather than merge operation.

A. true

B. false

Correct : A. true

2. How many sub arrays does the quick sort algorithm divide the entire array into?

A. one

B. two

C. three

D. four

Correct : B. two

3. Which is the worst method of choosing a pivot element?

A. first element as pivot

B. last element as pivot

C. median-of-three partitioning

D. random element as pivot

Correct : A. first element as pivot

4. The shortest distance between a line and a point is achieved when?

A. a line is drawn at 90 degrees to the given line from the given point

B. a line is drawn at 180 degrees to the given line from the given point

C. a line is drawn at 60 degrees to the given line from the given point

D. a line is drawn at 270 degrees to the given line from the given point

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)?

A. 4.5 units

B. 5.4 units

C. 4.3 units

D. 3.3 units

Correct : D. 3.3 units

6. What is the distance between the lines 3x- 4y+7=0 and 3x-4y+5=0?

A. 1 unit

B. 0.5 unit

C. 0.8 unit

D. 0.4 unit

Correct : D. 0.4 unit

7. What will be the slope of the line given by ax + by + c = 0?

A. -a/b

B. -b/a

C. -c/a

D. a/c

Correct : A. -a/b

8. What will be the slope of the line given by 10x + 5y + 8=0?

A. -5

B. -2

C. -1.25

D. 5

Correct : B. -2

9. Which of the following areas do closest pair problem arise?

A. computational geometry

B. graph colouring problems

C. numerical problems

D. string matching

Correct : A. computational geometry

10. What is the runtime efficiency of using brute force technique for the closest pair problem?

A. o(n)

B. o(n log n)

C. o(n2)

D. o(n3 log n)

Correct : C. o(n2)

11. The most important condition for which closest pair is calculated for the points (pi, pj) is?

A. i>j

B. i!=j

C. i=j

D. i<j

Correct : D. i<j

12. What is the basic operation of closest pair algorithm using brute force technique?

A. euclidean distance

B. radius

C. area

D. manhattan distance

Correct : A. euclidean distance

13. Which of the following is similar to Euclidean distance?

A. manhattan distance

B. pythagoras metric

C. chebyshev distance

D. heuristic distance

Correct : B. pythagoras metric

14. Which of the following strategies does the following diagram depict?

A. divide and conquer strategy

B. brute force

C. exhaustive search

D. backtracking

Correct : B. brute force

15. Manhattan distance is an alternative way to define a distance between two points.

A. true

B. false

Correct : A. true

16. What is the optimal time required for solving the closest pair problem using divide and conquer approach?

A. o(n)

B. o(log n)

C. o(n log n)

D. o(n2)

Correct : C. o(n log n)

17. In divide and conquer, the time is taken for merging the subproblems is?

A. o(n)

B. o(n log n)

C. o(n2)

D. o(log n)

Correct : B. o(n log n)

18. The optimal time obtained through divide and conquer approach using merge sort is the best case efficiency.

A. true

B. false

Correct : A. true

19. Which of the following strategies does the following diagram depict?

A. brute force

B. divide and conquer

C. exhaustive search

D. branch and bound

Correct : B. divide and conquer

20. Which of the points are closer to each other?

A. p1 and p11

B. p3 and p8

C. p2 and p3

D. p9 and p10

Correct : C. p2 and p3

21. Cross product is a mathematical operation performed between

A. 2 scalar numbers

B. a scalar and a vector

C. 2 vectors

D. any 2 numbers

Correct : C. 2 vectors

22. Cross product is also known as?

A. scalar product

B. vector product

C. dot product

D. multiplication

Correct : B. vector product

23. The concept of cross product is applied in the field of computer graphics.

A. true

B. false

Correct : A. true

24. Which of the following equals the a x b ( a and b are two vectors)?

A. – (a x b)

B. a.b

C. b x a

D. – (b x a)

Correct : D. – (b x a)

25. Cross product of two vectors can be used to find?

A. area of rectangle

B. area of square

C. area of parallelogram

D. perimeter of rectangle

Correct : C. area of parallelogram

26. What will be the cross product of the vectors 2i + 3j + k and 3i + 2j + k?

A. i + 2j + k

B. 2i + 3j + k

C. i + j – 5k

D. 2i – j – 5k

Correct : C. i + j – 5k

27. What will be the cross product of the vectors 2i + 3j + k and 6i + 9j + 3k?

A. i + 2j + k

B. i – j – 5k

C. 0

D. 2i – j – 5k

Correct : C. 0

28. Which of the following operation will give a vector that is perpendicular to both vectors a and b?

A. a x b

B. a.b

C. b x a

D. both a x b and b x a

Correct : D. both a x b and b x a

29. is a method of constructing a smallest polygon out of n given points.

A. closest pair problem

B. quick hull problem

C. path compression

D. union-by-rank

Correct : B. quick hull problem

30. What is the other name for quick hull problem?

A. convex hull

B. concave hull

C. closest pair

D. path compression

Correct : A. convex hull

31. How many approaches can be applied to solve quick hull problem?

A. 1

B. 2

C. 3

D. 4

Correct : B. 2

32. What is the average case complexity of a quick hull algorithm?

A. o(n)

B. o(n log n)

C. o(n2)

D. o(log n)

Correct : B. o(n log n)

33. What is the worst case complexity of quick hull?

A. o(n)

B. o(n log n)

C. o(n2)

D. o(log n)

Correct : C. o(n2)

34. What does the following diagram depict?

A. closest pair

B. convex hull

C. concave hull

D. path compression

Correct : B. convex hull

35. Which of the following statement is not related to quickhull algorithm?

A. finding points with minimum and maximum coordinates

B. dividing the subset of points by a line

C. eliminating points within a formed triangle

D. finding the shortest distance between two points

Correct : D. finding the shortest distance between two points

36. The quick hull algorithm runs faster if the input uses non- extreme points.

A. true

B. false

Correct : A. true

37. To which type of problems does quick hull belong to?

A. numerical problems

B. computational geometry

C. graph problems

D. string problems

Correct : B. computational geometry

38. Which of the following algorithms is similar to a quickhull algorithm?

A. merge sort

B. shell sort

C. selection sort

D. quick sort

Correct : D. quick sort

39. Who formulated quick hull algorithm?

A. eddy

B. andrew

C. chan

D. graham

Correct : A. eddy

40. The time is taken to find the ‘n’ points that lie in a convex quadrilateral is?

A. o(n)

B. o(n log n)

C. o(n2)

D. o(log n)

Correct : A. o(n)

41. Chan’s algorithm is used for computing

A. closest distance between two points

B. convex hull

C. area of a polygon

D. shortest path between two points

Correct : B. convex hull

42. What is the running time of Chan’s algorithm?

A. o(log n)

B. o(n log n)

C. o(n log h)

D. o(log h)

Correct : C. o(n log h)

43. Who formulated Chan’s algorithm?

A. timothy

B. kirkpatrick

C. frank nielsen

D. seidel

Correct : A. timothy

44. The running time of Chan’s algorithm is obtained from combining two algorithms.

A. true

B. false

Correct : A. true

45. Which of the following is called the “ultimate planar convex hull algorithm”?

A. chan’s algorithm

B. kirkpatrick-seidel algorithm

C. gift wrapping algorithm

D. jarvis algorithm

Correct : B. kirkpatrick-seidel algorithm

46. Which of the following algorithms is the simplest?

A. chan’s algorithm

B. kirkpatrick-seidel algorithm

C. gift wrapping algorithm

D. jarvis algorithm

Correct : A. chan’s algorithm

47. What is the running time of Hershberger algorithm?

A. o(log n)

B. o(n log n)

C. o(n log h)

D. o(log h)

Correct : B. o(n log n)

48. Which of the following statements is not a part of Chan’s algorithm?

A. eliminate points not in the hull

B. recompute convex hull from scratch

C. merge previously calculated convex hull

D. reuse convex hull from the previous iteration

Correct : B. recompute convex hull from scratch

49. Which of the following factors account more to the cost of Chan’s algorithm?

A. computing a single convex hull

B. locating points that constitute a hull

C. computing convex hull in groups

D. merging convex hulls

Correct : C. computing convex hull in groups

50. Chan’s algorithm can be used to compute the lower envelope of a trapezoid.

A. true

B. false

Correct : A. true

51. Which of the following is false in the case of a spanning tree of a graph G?

A. it is tree that spans g

B. it is a subgraph of the g

C. it includes every vertex of the g

D. it can be either cyclic or acyclic

Correct : D. it can be either cyclic or acyclic

52. Every graph has only one minimum spanning tree.

A. true

B. false

Correct : B. false

53. Consider a complete graph G with 4 vertices. The graph G has spanning trees.

A. 15

B. 8

C. 16

D. 13

Correct : C. 16

54. The travelling salesman problem can be solved using

A. a spanning tree

B. a minimum spanning tree

C. bellman – ford algorithm

D. dfs traversal

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?

A. graph m has no minimum spanning tree

B. graph m has a unique minimum spanning trees of cost 2

C. graph m has 3 distinct minimum spanning trees, each of cost 2

D. graph m has 3 spanning trees of different costs

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?

A. every minimum spanning tree of g must contain cd

B. if ab is in a minimum spanning tree, then its removal must disconnect g

C. no minimum spanning tree contains ab

D. g has a unique minimum spanning tree

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.

A. true

B. false

Correct : A. true

58. Which of the following is not the algorithm to find the minimum spanning tree of the given graph?

A. boruvka’s algorithm

B. prim’s algorithm

C. kruskal’s algorithm

D. bellman–ford algorithm

Correct : D. bellman–ford algorithm

59. Which of the following is false?

A. the spanning trees do not have any cycles

B. mst have n – 1 edges if the graph has n edges

C. edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the msts of the graph

D. removing one edge from the spanning tree will not make the graph disconnected

Correct : D. removing one edge from the spanning tree will not make the graph disconnected

60. Kruskal’s algorithm is used to

A. find minimum spanning tree

B. find single source shortest path

C. find all pair shortest path algorithm

D. traverse the graph

Correct : A. find minimum spanning tree

61. Kruskal’s algorithm is a

A. divide and conquer algorithm

B. dynamic programming algorithm

C. greedy algorithm

D. approximation algorithm

Correct : C. greedy algorithm

62. What is the time complexity of Kruskal’s algorithm?

A. o(log v)

B. o(e log v)

C. o(e2)

D. o(v log e)

Correct : B. o(e log v)

63. Consider the following graph. Using Kruskal’s algorithm, which edge will be selected first?

A. gf

B. de

C. be

D. bg

Correct : C. be

64. Which of the following edges form minimum spanning tree on the graph using kruskals algorithm?

A. (b-e)(g-e)(e-f)(d-f)

B. (b-e)(g-e)(e-f)(b-g)(d-f)

C. (b-e)(g-e)(e-f)(d-e)

D. (b-e)(g-e)(e-f)(d-f)(d-g)

Correct : A. (b-e)(g-e)(e-f)(d-f)

65. Which of the following is false about the Kruskal’s algorithm?

A. it is a greedy algorithm

B. it constructs mst by selecting edges in increasing order of their weights

C. it can accept cycles in the mst

D. it uses union-find data structure

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.

A. true

B. false

Correct : B. false

67. Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure.

A. s1 is true but s2 is false

B. both s1 and s2 are false

C. both s1 and s2 are true

D. s2 is true but s1 is false

Correct : D. s2 is true but s1 is false

68. Which of the following is true?

A. prim’s algorithm initialises with a vertex

B. prim’s algorithm initialises with a edge

C. prim’s algorithm initialises with a vertex which has smallest edge

D. prim’s algorithm initialises with a forest

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?

A. o(log v)

B. o(v2)

C. o(e2)

D. o(v log e)

Correct : B. o(v2)

70. Prim’s algorithm is a

A. divide and conquer algorithm

B. greedy algorithm

C. dynamic programming

D. approximation algorithm

Correct : B. greedy algorithm

71. Prim’s algorithm resembles Dijkstra’s algorithm.

A. true

B. false

Correct : A. true

72. Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.

A. true

B. false

Correct : A. true

73. Prim’s algorithm can be efficiently implemented using for graphs with greater density.

A. d-ary heap

B. linear search

C. fibonacci heap

D. binary search

Correct : A. d-ary heap

74. Which of the following is false about Prim’s algorithm?

A. it is a greedy algorithm

B. it constructs mst by selecting edges in increasing order of their weights

C. it never accepts cycles in the mst

D. it can be implemented using the fibonacci heap

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?

A. max priority queue

B. stack

C. circular queue

D. min priority queue

Correct : D. min priority queue

76. How many priority queue operations are involved in Dijkstra’s Algorithm?

A. 1

B. 3

C. 2

D. 4

Correct : B. 3

77. How many times the insert and extract min operations are invoked per vertex?

A. 1

B. 2

C. 3

D. 0

Correct : A. 1

78. The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be equal to

A. total number of vertices

B. total number of edges

C. number of vertices – 1

D. number of edges – 1

Correct : B. total number of edges

79. What is running time of Dijkstra’s algorithm using Binary min- heap method?

A. o(v)

B. o(vlogv)

C. o(e)

D. o(elogv)

Correct : D. o(elogv)

80. The running time of Bellmann Ford algorithm is lower than that of Dijkstra’s Algorithm.

A. true

B. false

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.

A. true

B. false

Correct : A. true

82. Dijkstra’s Algorithm is the prime example for

A. greedy algorithm

B. branch and bound

C. back tracking

D. dynamic programming

Correct : A. greedy algorithm

83. Bellmann ford algorithm provides solution for problems.

A. all pair shortest path

B. sorting

C. network flow

D. single source shortest path

Correct : D. single source shortest path

84. Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not.

A. true

B. false

Correct : A. true

85. How many solution/solutions are available for a graph having negative weight cycle?

A. one solution

B. two solutions

C. no solution

D. infinite solutions

Correct : C. no solution

86. What is the running time of Bellmann Ford Algorithm?

A. o(v)

B. o(v2)

C. o(elogv)

D. o(ve)

Correct : D. o(ve)

87. How many times the for loop in the Bellmann Ford Algorithm gets executed?

A. v times

B. v-1

C. e

D. e-1

Correct : B. v-1

88. Dijikstra’s Algorithm is more efficient than Bellmann Ford Algorithm.

A. true

B. false

Correct : A. true

89. What is the basic principle behind Bellmann Ford Algorithm?

A. interpolation

B. extrapolation

C. regression

D. relaxation

Correct : D. relaxation

90. Bellmann Ford Algorithm can be applied for

A. undirected and weighted graphs

B. undirected and unweighted graphs

C. directed and weighted graphs

D. all directed graphs

Correct : C. directed and weighted graphs

91. Bellmann Ford algorithm was first proposed by

A. richard bellmann

B. alfonso shimbe

C. lester ford jr

D. edward f. moore

Correct : B. alfonso shimbe

92. Bellmann Ford Algorithm is an example for

A. dynamic programming

B. greedy algorithms

C. linear programming

D. branch and bound

Correct : A. dynamic programming

93. A graph is said to have a negative weight cycle when?

A. the graph has 1 negative weighted edge

B. the graph has a cycle

C. the total weight of the graph is negative

D. the graph has 1 or more negative weighted edges

Correct : C. the total weight of the graph is negative

94. Floyd Warshall’s Algorithm is used for solving

A. all pair shortest path problems

B. single source shortest path problems

C. network flow problems

D. sorting problems

Correct : A. all pair shortest path problems

95. Floyd Warshall’s Algorithm can be applied on

A. undirected and unweighted graphs

B. undirected graphs

C. directed graphs

D. acyclic graphs

Correct : C. directed graphs

96. What is the running time of the Floyd Warshall Algorithm?

A. big-oh(v)

B. theta(v2)

C. big-oh(ve)

D. theta(v3)

Correct : D. theta(v3)

97. What approach is being followed in Floyd Warshall Algorithm?

A. greedy technique

B. dynamic programming

C. linear programming

D. backtracking

Correct : B. dynamic programming

98. Floyd Warshall Algorithm can be used for finding

A. single source shortest path

B. topological sort

C. minimum spanning tree

D. transitive closure

Correct : D. transitive closure

99. What procedure is being followed in Floyd Warshall Algorithm?

A. top down

B. bottom up

C. big bang

D. sandwich

Correct : B. bottom up

100. Floyd- Warshall algorithm was proposed by

A. robert floyd and stephen warshall

B. stephen floyd and robert warshall

C. bernad floyd and robert warshall

D. robert floyd and bernad warshall

Correct : A. robert floyd and stephen warshall