Q.1
Which of the following is false in the case of a spanning tree of a graph G?
  • it is tree that spans g
  • it is a subgraph of the g
  • it includes every vertex of the g
  • it can be either cyclic or acyclic
Q.2
Which of the following problems is NOT solved using dynamic programming?
  • 0/1 knapsack problem
  • matrix chain multiplication problem
  • edit distance problem
  • fractional knapsack problem
Q.3
Which of the following problems should be solved using dynamic programming?
  • mergesort
  • binary search
  • longest common subsequence
  • quicksort
Q.4
Problems that cannot be solved by any algorithm are called?
  • tractable problems
  • intractable problems
  • undecidable problems
  • decidable problems
Q.5
What is the time complexity of Kruskal’s algorithm?
  • o(log v)
  • o(e log v)
  • o(e2)
  • o(v log e)
Q.6
What will be the recurrence relation of the code of recursive selection sort?
  • t(n) = 2t(n/2) + n
  • t(n) = 2t(n/2) + c
  • t(n) = t(n-1) + n
  • t(n) = t(n-1) + c
Q.7
Master’s theorem is used for?
  • solving recurrences
  • solving iterative relations
  • analysing loops
  • calculating the time complexity of any code
Q.8
What is the running time of the Floyd Warshall Algorithm?
  • big-oh(v)
  • theta(v2)
  • big-oh(ve)
  • theta(v3)
Q.9
Which of the following sorting algorithm is NOT stable?
  • selection sort
  • brick sort
  • bubble sort
  • merge sort
Q.10
What is the worst case time complexity of a quick sort algorithm?
  • o(n)
  • o(n log n)
  • o(n2)
  • o(log n)
Q.11
Which of the following is false about the Kruskal’s algorithm?
  • it is a greedy algorithm
  • it constructs mst by selecting edges in increasing order of their weights
  • it can accept cycles in the mst
  • it uses union-find data structure
Q.12
What is the running time of Bellmann Ford Algorithm?
  • o(v)
  • o(v2)
  • o(elogv)
  • o(ve)
Q.13
Which of the following is the most commonly used data structure for implementing Dijkstra’s Algorithm?
  • max priority queue
  • stack
  • circular queue
  • min priority queue
Q.14
What is the LCM of two coprime numbers?
  • 1
  • 0
  • addition of two coprime numbers
  • multiplication of two coprime numbers
Q.15
Which of the following is false about Prim’s algorithm?
  • it is a greedy algorithm
  • it constructs mst by selecting edges in increasing order of their weights
  • it never accepts cycles in the mst
  • it can be implemented using the fibonacci heap
Q.16
What is the objective of tower of hanoi puzzle?
  • to move all disks to some other rod by following rules
  • to divide the disks equally among the three rods by following rules
  • to move all disks to some other rod in random order
  • to divide the disks equally among three rods in random order
Q.17
Who formulated the first ever algorithm for solving the Hamiltonian path problem?
  • martello
  • monte carlo
  • leonard
  • bellman
Q.18
How many sub arrays does the quick sort algorithm divide the entire array into?
  • one
  • two
  • three
  • four
Q.19
Which of the following sorting algorithms is used along with quick sort to sort the sub arrays?
  • merge sort
  • shell sort
  • insertion sort
  • bubble sort
Q.20
Problems that can be solved in polynomial time are known as?
  • intractable
  • tractable
  • decision
  • complete
0 h : 0 m : 1 s