(C) The given problem can be reduced to the 3-SAT problem
(D) It’s faster than Greedy
Q2. In the above question, which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?
(A) X[1, W]
(B) X[n ,0]
(C) X[n, W]
(D) X[n -1, n]
Q3. Given a sorted array of integers, what can be the minimum worst case time complexity to find ceiling of a number x in given array? Ceiling of an element x is the smallest element present in array which is greater than or equal to x. Ceiling is not present if x is greater than the maximum element present in array. For example, if the given array is {12, 67, 90, 100, 300, 399} and x = 95, then output should be 100.
(A) O(LogLogn)
(B) O(n)
(C) O(Logn)
(D) O(Logn * Logn)
Q4. Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
(A) Insertion Sort with time complexity O(kn)
(B) Heap Sort with time complexity O(nLogk)
(C) Quick Sort with time complexity O(kLogk)
(D) Merge Sort with time complexity O(kLogk)
Q5. The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is.
(A) T(n) = 2T(n – 2) + 2
(B) T(n) = 2T(n – 1) + n
(C) T(n) = 2T(n/2) + 1
(D) T(n) = 2T(n – 1) + 1
Q6. Which of the following is true about Kruskal andPrim MST algorithms? Assume that Prim is implemented for adjacency list representation using Binary Heap and Kruskal is implemented using union by rank.
(A) Worst case time complexity of both algorithms is same
(B) Worst case time complexity of Kruskal is better than Prim
(C) Worst case time complexity of Prim is better than Kruskal
(D) None
Q7. Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?
(A) 0, 10, 110, 1110, 11110, 11111
(B) 11, 10, 011, 010, 001, 000
(C) 11, 10, 01, 001, 0001, 0000
(D) 110, 100, 010, 000, 001, 111
Q8. Which of the following standard algorithms is not Dynamic Programming based.
(A) Bellman–Ford Algorithm for single source shortest path
(B) Floyd Warshall Algorithm for all pairs shortest paths
(C) 0-1 Knapsack problem
(D) Prim's Minimum Spanning Tree
Q9. Kadane algorithm is used to find:
(A) Maximum sum subsequence in an array
(B) Maximum sum subarray in an array
(C) Maximum product subsequence in an array
(D) Maximum product subarray in an array
Q10. Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?