Aoa

Q1 Which of the following problem does not belongs to class P a) Given a graph with n vertices, determine whether it can be coloured using n colours b) Given a graph with n vertices, determine whether it can be coloured using n - 1 colours. c) Given a graph and an integer k, determine whether it can be coloured using k + 1 colours. d) Given a graph, determine whether it has a clique of size 3. Q2. If X and Y are two decision problems and both are NP-complete. Is the problem Z, where Z = X ∩ Y , NP-complete? (The problem Z can also be described in this way: given an input a, output YES if and only if the correspond output for X and Y are both YES.) (a) Yes, it is NP-complete. (b) No, it is not NP-complete. (c) None of the above Q3 Which of the following statements is not true? (A) Dynamic programming and greedy algorithms depend on optimal substructure:Problem P contains two sub-problems P1 and P2 that are structurally similar to P but smaller in size. (B) Dynamic programming depends on overlapping sub-problems: Problem P contains sub problems P1 and P2, and P1 and P2 in turn share numerous sub-problems Q1through Qn. (C) Greedy algorithms depend on the greedy choice property: The optimal solution to problem P can be determined without first obtaining optimal solutions to subproblems of P. (D) None of the above Q4Suppose c is an integer greater than 1, and some function f is defined such that f(0) = f(1) = 1. Then which of the following statements must not be true? (A) If f(n) = f(n/2) + c, then f(n) ∈ O(lg n) (B) If f(n) = f(n − 2) + c, then f(n) ∈ O(n) (C) If f(n) = c * f(n − 2), then f(n) ∈ O(cn) (D) None of the above Q5 What is the worst case time complexity of the following function written in C? int worstFunction (int n, int a[ ]) { int i, m, k=1; for(i = 0; i < 5; i++) { if(a[i] == n) { m = n; while(m) { if(m%3==2)k++; m /= 2; } } } return k; } (A) O(5m) (B) O(nm) (C) O(log n) (D) O(2n) Q6 which of the following statement is false: (a) If an operation takes O(1) amortized time, then that operation takes O(1) worst case time (b) If an operation takes O(1) worst case time then that operation takes O(1) amortized time. (c) For a graph G and a node v in that graph, the DFS and BFS trees of G rooted at v always contain the same number of edges. (d) Any BFS tree for a connected graph G is a spanning tree. Q7What is the complexity of the algorithm below (assuming that n and m are approximately equal in value)? int doit (int n, m) { if (n*m==0) return n; return max(doit(n-1,m), doit(n-1,m-1), doit(n,m-1)) +1; }

(a) O(n) (b) O(n log n) (c) O(n2) (d) O(2n) Q8Below is some code for a variation of depth first search. Assume that the graph is undirected and connected, that vertices are just integers from 1 to n, that Visited and Color are arrays indexed by vertices, and that the driver simply calls DFS(x,1) for some arbitrary vertex x. Initially all vertices have Visited set to false. Suppose that we want to set a global variable twoColorable to false if G is not two-colorable. What code should we put on the blank line? (The code works by trying to color the vertices color 1 or color 2; note that if c ∈ {1, 2}, then 3 -c is just the other element of {1, 2} void DFS(v,c) { Visited[v] = true; Color[v] = c; for (each w such that v → w) if (Visited[w]) ______________________ else DFS(w,3- c); } } A.if (Color[v] == Color[w]) twoColorable = false; B. if (Color[v] != Color[w]) twoColorable = false; C. if (Color[v] > Color[w]) twoColorable = false; D. if (Color[v] < Color[w]) twoColorable = false; Q9. We showed a lower bound of (n log n) for sorting algorithms that fit the decision tree model. However, we also described an algorithm that can sort n records with keys in the range 0::m - 1 in O(m) time. Why is this not a contradiction? A. This time bound for this algorithm did not include the time for the initial comparisons of the keys. B. This time bound for the algorithm assumed that all permutations of the input were equally likely. C. The algorithm did not fit the decision tree model. D. (n log n) and O(m + n) are the same thing. Q10 Suppose that a binary decision tree has 74 leaves. What is the lowest possible value of the worst-case number of comparisons made by the algorithm corresponding to this tree? A. 5 B. 6 C. 7 D. 8 E. 9 Q11. Suppose that a 2-3 tree has height 6. What is the smallest number of keys that could be present? (In measuring the height, assume the tree is extended, so that leaves contain no data. Thus the number of leaves in a 2-3 tree of height 1 is either 2 or 3.) A. 61 B. 62 C. 63 D. 64 E. 65 Q12. Suppose that we start with an empty 2-3 tree and insert the keys 1,2,3,4,5,6,7 in that order. How many node splits will occur? a 5 B. 4 C. 3 D. 2 E. 1 Q13. Suppose that we insert a 65 into the AVL tree shown below. What rotation will we need to perform? A. A single rotation rooted at the node containing 30. B. A double rotation rooted at the node containing 30. C. A single rotation rooted at the node containing 50. D. A double rotation rooted at the node containing 50 Q14Suppose that we wish to represent a directed graph G in which each edge has a numerical

value associated with it, called a cost. One approach would be to use adjacency lists, and let the nodes in the lists have a field for cost. Another approach would be to use a cost matrix. What is a possible advantage of the cost matrix? (Let n be the number of vertices in G, and e be the number of edges.) A. It uses only O(n) space in the worst case. B. It uses only O(n + e) space in the worst case. C. It makes it possible to find the cost between two arbitrary vertices i and j in O(1) time, assuming that the vertices are represented as integers from 1 to n. D. It makes it possible to perform a depth-first search of the graph in worst-case O(n + e) time Q15Assume n (n > 0) is a non-negative integer. What value is returned by calling the following function? int f (int n) { if (n == 0) return 0; else return (f(n/3 + 1) + n - 1); } a. 1 b. n/3 + 1 c. n/3 + n + 1 d. n/3 + n e. none of the above Q16Which of the following functions grows fastest? a. NlogN b. NloglogN c. N1.5 d. NlogN2 e. Nlog2N Q17In the array implementation of a list, a. The insert operation, in general, is order O(N), but the remove operation takes constant time. b. The remove operation, in general, is order O(N), but the insert operation takes constant time. c. Both the insert and remove operations, in general, are order O(N). d. Both the insert and remove operations, in general, take constant time. e. none of the above Q18The value of 3100 (mod 20) is: a. 20

b. 10 c. 5

d. 1

e. none of the above

Q19Which of the following closed forms is equivalent to the recurrence relation: T(1) = 1 T(n) = 3T(n/3 ) + 2n A. n + 3n log 2 n B. 3n + n log 2 n C. 2n + n log 3 n D. n + 2n log 3 n E. 3n + 2n log 3 n Q20. For a directed graph with n nodes which is implemented using an adjacency matrix, what is the execution time required to determine if the graph is weakly connected? A. O(|V|) B. O(|V| + |E|) C. O(|V|2) D. O(|V|2 + |V| *|E|) E. O(|V|3) Q21. Which is true of a Hamiltonian tour? (a) Determining whether there is a tour is NP-hard, but not NP-complete. (b) Determining whether there is a tour is O(E) where E is the number of edges, but actually identifying the tour is O(n2). (c) Determining whether there is a tour is O(E) where E is the number of edges, and actually identifying the tour is O(E). (d) Determining whether there is a tour is NP-complete

Q22 Given the graph above where the y-axis represents the running time of a specific algorithm and the x-axis represents several input instances. What can we say A, B and C respectively represents (a) Best Case, Average Case, Worst Case (b) Average Case, Worst Case, Best Case (c) Average Case, Best Case, Worst Case (d) Worst Case, Average Case, Best Case (e) Worst Case, Best Case, Average Case Q23The most efficient way to find the median (element in which half the elements are higher and half lower) of an array of n numbers is a. Sort the elements using quicksort and pick the middle. b. Use a variant of quicksort, where you throw away half of the nodes after a partition. c. Find the average of the numbers. Check to see if the average is also the median. If so, you are done. If not, guess another number and try again. d. Use a max heap and deleteMax n/2 times. Q24 What is true of the minimal cost spanning tree algorithm (for a connected, undirected graph) when there are negative edges present? (a) There is no problem. The original algorithm handles this case without modification. (b) You must add a constant to each edge before solving the problem in the traditional manner. Just subtract the constant after you are finished. (c) The algorithm will not be able to give any answer. (d) In some cases, there is no such thing as a minimal cost spanning tree with negative edges. Q25 We need to determine if a directed graph is cyclic. This can be accomplished most efficiently by a. Doing a regular traversal. If you reach a node which has already been visited, the graph is cyclic. b. Do a graph traversal keeping track of the nodes which are on the path (in the dfs tree) from the root to the node. If a node has an edge to anything that is already on the path, the graph is cyclic. c. Perform a topological ordering. If it fails, the graph is cyclic. d. none of the above will work. Q26 I need to ensure that every house has electricity, but I want to minimize the cost of the wire used in connected them to the power plant. Which algorithm would I use? a. All pairs shortest path. b. Single source shortest path. c. Hamiltonian tour. d. Minimal cost spanning tree. e. Topological ordering Q27 Suppose that we are representing a heap in memory using the array representation The elements of the heap are stored in A[1],A[2], : : : ,A[23]; A[1] contains the root value. Where could we find the left child of the right child of the left child of the root?

A. A[14] B. A[13] C. A[12] D. A[11] E. A[10] Q28Suppose we are performing Depth-First Search on a directed graph G with 50 vertices. Assume that G has no cycles. Two of the vertices are x and y, and there is an edge from x to y. Which of the following are possible relative orders in which the calls to the recursive DFS procedure could start and finish? A. DFS(v) starts, : : :, DFS(v) finishes, : : :, DFS(w) starts, : : :, DFS(w) finishes. B. DFS(w) starts, : : :, DFS(v) starts, : : :, DFS(v) finishes, : : :, DFS(w) finishes. C. DFS(v) starts, : : :, DFS(w) starts, : : :, DFS(w) finishes, : : :, DFS(v) finishes. D. A and B E. B and C

Solution: 1 c 2 c 3 d 4 d 5 c 6 a 7 d 8a 9 c 10 b 11 12 a 13 14 c 15 e 16 e 17 c 18 a 19 20 b 21 d 22 d 23 24 a 25 a 26 d 27 e 28