1) Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
(A) O(log n)
(B) O(n)
(C) O(n log n)
(D) O(n^2)

Answer (B)

2) Consider the following operation along with Enqueue and Dequeue operations on
queues, where k is a global parameter

MultiDequeue(Q){
   m = k
   while (Q is not empty and m  > 0) {
      Dequeue(Q)
      m = m - 1
   }
}

What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue?
(A) Θ(n)
(B) Θ(n + k)
(C) Θ(nk)
(D) Θ(n²)

Answer (A)
Since the queue is empty initially, the condition of while loop never becomes true. So the time complexity is Θ(n)

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

Answer (D)

Following are the steps to follow to solve Tower of Hanoi problem recursively.

Let the three pegs be A, B and C. The goal is to move n pegs from A to C.
To move n discs from peg A to peg C:
    move n-1 discs from A to B. This leaves disc n alone on peg A
    move disc n from A to C
    move n?1 discs from B to C so they sit on disc n

The recurrence function T(n) for time complexity of the above recursive solution can be written as following.

T(n) = 2T(n-1) + 1

4) Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijstra shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.

(A) SDT
(B) SBDT
(C) SACDT
(D) SACET

Answer (D)

5) Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are
(A) Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT
(B) Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR
(C) Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT
(D) Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT

Answer (A)

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

(A) A(n) = Ω(W(n))
(B) A(n) = Θ(W(n))
(C) A(n) = O(W(n))
(D) A(n) = o(W(n))

Answer (C)
The worst case time complexity is always greater than or same as the average case time complexity.

7) The worst case running time to search for an element in a balanced in a binary search tree with n2^n elements is
(A) Θ(n log n)
(B) Θ(n2ⁿ)
(C) Θ(n)
(D) Θ(log n)

Answer (C)
Time taken to search an element is Θ(h) where h is the height of Binary Search Tree (BST). The growth of height of a balanced BST is logerthimic in terms of number of nodes. So the worst case time to search an element would be Θ(Log(n*2^n)) which is Θ(Log(n) + Log(2^n)) Which is Θ(Log(n) + n) which can be written as Θ(n).

8) Assuming P != NP, which of the following is true ?
(A) NP-complete = NP
(B) NP-complete ∩ P = Φ
(C) NP-hard = NP
(D) P = NP-complete

Answer (B)
The answer is B (no NP-Complete problem can be solved in polynomial time). Because, if one NP-Complete problem can be solved in polynomial time, then all NP problems can solved in polynomial time. If that is the case, then NP and P set become same which contradicts the given condition.

9) The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.

The appropriate expression for the two boxes B1 and B2 are
(A) B1 : (1 + height(n->right)), B2 : (1 + max(h1,h2))
(B) B1 : (height(n->right)), B2 : (1 + max(h1,h2))
(C) B1 : height(n->right), B2 : max(h1,h2)
(D) B1 : (1 + height(n->right)), B2 : max(h1,h2)

Answer (A)
The box B1 gets exected when left subtree of n is NULL and right sbtree is not NULL. In this case, height of n will be height of right subtree plus one.
The box B2 gets executed when both left and right sbtrees of n are not NULL. In this case, height of n will be max of heights of left and right sbtrees of n plus 1.

10) A list of n string, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
(A) O(n log n )
(B) O(n² log n)
(C) O(n^2 + log n)
(D) O(n^2)

Answer (B)
The recurrence tree for merge sort will have height Logn. And O(n²) work will be done at each level of the recurrence tree (Each level involves n comparisons and a comparison takes O(n) time in worst case). So time complexity of this Merge Sort will be O(n² log n).