Q.1
Which of the following is not the algorithm to find the minimum spanning tree of the given graph?
  • boruvka’s algorithm
  • prim’s algorithm
  • kruskal’s algorithm
  • bellman–ford algorithm
Q.2
How many priority queue operations are involved in Dijkstra’s Algorithm?
  • 1
  • 3
  • 2
  • 4
Q.3
In what time can the Hamiltonian path problem can be solved using dynamic programming?
  • o(n)
  • o(n log n)
  • o(n2)
  • o(n2 2n)
Q.4
What is a subset sum problem?
  • finding a subset of a set that has sum of elements equal to a given number
  • checking for the presence of a subset that has sum of elements equal to a given number and printing true or false based on the result
  • finding the sum of elements present in a set
  • finding the sum of all the subsets of a set
Q.5
The problem of finding a path in a graph that visits every vertex exactly once is called?
  • hamiltonian path problem
  • hamiltonian cycle problem
  • subset sum problem
  • turnpike reconstruction problem
Q.6
What is the average running time of a quick sort algorithm?
  • o(n2)
  • o(n)
  • o(n log n)
  • o(log n)
Q.7
In which of the following cases, the maximum sum rectangle is thematrix itself?
  • when all the elements are negative
  • when all the elements are positive
  • when some elements are positive and some negative
  • when diagonal elements are positive and rest are negative
Q.8
The shortest distance between a line and a point is achieved when?
  • a line is drawn at 90 degrees to the given line from the given point
  • a line is drawn at 180 degrees to the given line from the given point
  • a line is drawn at 60 degrees to the given line from the given point
  • a line is drawn at 270 degrees to the given line from the given point
Q.9
Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?
  • o(log v)
  • o(v2)
  • o(e2)
  • o(v log e)
Q.10
To which class does the Euler’s circuit problem belong?
  • p class
  • np class
  • partition class
  • complete class
Q.11
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
Q.12
Which of the following techniques can be used to search an element in an unsorted array?
  • iterative linear search
  • recursive binary search
  • iterative binary search
  • normal binary search
Q.13
Which of the following strategies does the following diagram depict?
  • divide and conquer strategy
  • brute force
  • exhaustive search
  • backtracking
Q.14
The Euler’s circuit problem can be solved in?
  • o(n)
  • o( n log n)
  • o(log n)
  • o(n2)
Q.15
The problem of maximizing the sum of weights on edges connecting matched pairs of vertices is?
  • maximum- mass matching
  • maximum bipartite matching
  • maximum weight matching
  • maximum node matching
Q.16
What is the length of an augmenting path?
  • even
  • odd
  • depends on graph
  • 1
Q.17
Who was the first person to solve the maximum matching problem?
  • jack edmonds
  • hopcroft
  • karp
  • claude berge
Q.18
Which of the following problems is similar to that of a Hamiltonian path problem?
  • knapsack problem
  • closest pair problem
  • travelling salesman problem
  • assignment problem
Q.19
What is the set partition problem?
  • finding a subset of a set that has sum of elements equal to a given number
  • checking for the presence of a subset that has sum of elements equal to a given number
  • checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result
  • finding subsets with equal sum of elements
Q.20
Which of the following is not true about subset sum problem?
  • the recursive solution has a time complexity of o(2n)
  • there is no known solution that takes polynomial time
  • the recursive solution is slower than dynamic programming solution
  • the dynamic programming solution has a time complexity of o(n log n)
0 h : 0 m : 1 s