GATE 2016 - Algorithms Test 3
This Test will cover complete Algorithms with very important questions, starting off from basics to advanced level.
Q. In an Unweighted, Undirected connected Graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by?
Q. The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity __________ ?
Q. The minimum number of comparisons required to determine, if an integer appears more than n/2 times in a sorted array of n integers?
Q. A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?
Q. G is a graph on n vertices and 2n-2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?
Q. We have a binary heap on n elements and wish to insert n more elements(not necessarily one after another) into this heap. Total time required for this is?
Q. What is the number of swaps required to sort n elements using selection sort, in the worst case?
Q. In quick sort, for sorting n elements, the (n/4)th smallest element is selected as Pivot using an O(n) time algorithm. What is the worst case time complexity of the Quick Sort?
Q. Two alternative package A and B are available for processing a database having 10^k records. Package A requires 0.00001 n^2 time units and package B requires 10nlog(n) [Base of log is 10] time units to process n records. What is the smallest value of k for which B will be preferred over A?
Q. Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?
Q. The recurrence relation capturing the optimal execution time of the Tower of Hanoi problem with n discs is?
Q. The worst case running to search for an element in a balanced binary search tree with n2^n elements is?
Q. Assuming P not equal to NP, which of the following is TRUE?
Q. A list of n strings, each of length n, is sorted into lexicographic order using the Merge-Sort algorithm. The worst case running time of this computation is?
Q. You are given the Postorder traversal, P, of a binary search tree on the n elements 1,2,...,n. You have to determine the unique Binary Search Tree that has P as its Postorder traversal. What is the Time Complexity of the most efficient algorithm for doing this?
