1

ALGORITHM ANALYSIS

This Chapter “Algorithm Analysis” is taken from our:

ISBN : 9789386146250
 2

Quick Revision Material

C.g(n)
No
f(n) Matter

F(n)
ALGORITHM ANALYSIS AND DESIGN
Any Algorithm must satisfy the following criteria (or
Properties) n0
n
1. Input: It generally requires finite number of inputs. Fig. 1
2. Output: It must produce at least one output. For all values of n to the right of n 0, the value of f(n) is always lies
3. Uniqueness: Each instruction should be clear and on or below Cg(n).
unambiguous. THE NOTATION (BIG 'Omega')
4. Finiteness: It must terminate after a finite number of steps. O-Notation provides as asymptotic upper bound for a function;
-Notation provides as asymptotic upper bound for a function;
ASYMPTOTIC NOTATIONS -Notation, provides an asymptotic lower-bound for a given
function.
These notations are used to describe the Running time of an
algorithm, in terms of functions, whose domains are the set of We say that the function f (n) ( g (n))) [read as "f of n is big
natural numbers, N = {1, 2, ……}. Such notations are convenient "Omega" of g of n"], if and only if there exist two positive
for describing the worst case running time function. T(n) (problem constants C and n0 such that
size input size). The complexity function can be also be used to f (n) C.g (n) : n n0
compare two algorithms P and Q that perform the same task. The
basic Asymptotic Notations are:
1. O(Big-"Oh") Notation. [Maximum number of steps to solve
a problem, (upper bound)]
2. (Big-"Omega") Notation [Minimum number of steps to C.g(n)
No
solve a problem, (lower bound)] f(n) Matter
3. (Theta) Notation [Average number of steps to solve a f(n) = g(m)
problem, (used to express both upper and lower bound of a F(n)
given )f(n)).

THE NOTATION O (BIG 'Oh')

n0
Big 'Oh' Notation is used to express an asymptotic upper bound
n
(maximum steps) for a given function f(n). Let f(n) and g(n) are
two positive functions, each from the set of natural numbers Fig. 2
(domain) to the positive real numbers. Note that for all values of f(n) always lies on or above g(n).
We say that the function f(n) = O (g(n)) [read as "f of n is big
"Oh" of g of n"], if there exist two positive constants C and N0
such that
f (n) C.g (n) : n n0
The intuition behind O-notation is shown in figure-1
 3

THE NOTATION (Theta) 5. Y Y { y}

-Notation provides simultaneous both asymptotic lower bound
and asymptotic upper bound for a given function. 6. T T {( x, y )}
Let f(n) and g(n) are two positive functions, each from the set of 7. end while
natural numbers (domain) to the positive real numbers. In some
DIVIDE AND CONQU ER
cases, we have f (n) O( g ( n)) and f ( g (n)) then
In its simplest form, a divide-and-conquer algorithm divides the
f ( n) ( g (n)) . problem instance into a number of subinstances, recursively
We say that the function f (n) ( g (n)) [read as "f of n is solves each subsistences parately, and then combines the
solutions to the subinstances to obtain the solution to the original
Theta" of g of n"], if and only if there exist three positive constants
problem instance.
C1, C2 and n 0 such that
C1 .g (n) f (n) C2 .g (n) for all n n0 ...(i) BINARY SEARCH
(Note that this inequality (1) represents two conditions to be The algorithm is as follows
satisfied simultaneously viz C1 .g (n) f (n) and Input : An array A [1..n] of n elements sorted in non-decreasing
order and an element x.
f (n) C2 .g (n);
Output : j if x = A [j], 1 j n, and 0 otherwise.
clearly this implies 1. binarysearch (1, n)
if f(n) = O (g (n)) and f = (g(n)) then f(n) = (g(n)). Procedure binarysearch (low, high)
The following figure-1 shows the intuition behind the -Notation. 1. if low > high then return 0
2. else
3. mid [(low + high)/2]
c2g(n) 4. if x = A [mid] then return mid
5. else if x < A [mid] then return binary search (low, mid–1)
f(n) 6. else return binarysearch (mid + 1, high)
c1g(n)
7. end if
f(n)
f(n) = (g(n)) SO RTING AND SEARCHING
Henceforth, in the context of searching and sorting problems, we
will assume that the elements are drawn from a linearly ordered
set, for example the set of integers.
n n0
Let A[1..n] be a sequence of n elements. Consider the problem of
determining whether a given element x is in A. This problem can
be rephrased as follows. Find an index j; 1 j n, such that
Fig. 3 x = A[j] if x is in A, and j = 0 otherwise. A straightforward approach
Note that for all values of n to the right of the n0 the value is to scan the entries in A and compare each entry with x. If after
of f(n) lies at or above C1g(n) and at or below C2.g(n). j comparisons, 1 j n, the search is successful , i.e., x = A[j], j is
Hence inequality (1) simultaneously satisfied for C1 = 1, returned; otherwise a value of 0 is returned indicating an
C2 = 2 and n 1 . unsuccessful search. This method is referred to as sequential
Hence f(n) = (g(n)). search. It is also called linear search.
Minimum Cost Spanning Trees (Prim's Algorithm) ALGORITHM LINEAR SEARCH
Input : An array A [1..n] of n elements of an element x.
The algorithm is outlined below. It finds the set of edges T of a
Output : j if x = A [j], 1 j n, and 0 otherwise.
minimum cost spanning tree.
1. i 1
1. T {}; X {1}; Y V – {1}
2. while Y {} 2. while (j < n) and ( x A[ j])

3. Let (x, y) be of minimum weight such that x X and y Y .

3. j j+1
4. end while
4. X X { y} 5. if x = A [j] then return j else return 0
 4
Algorithm binary search gives a more formal description of this performing the comparison and shifting continues until an element
method. less than or equal to A[i] is found, or when all the sorted sequence
Input : An array A [1..n] of n elements sorted in nondecreasing so far is exhausted.
order and an element x. Input : An array A [1..n] of n elements.
Output : j if x = A [j], 1 j n, and 0 otherwise. Output : A [1..n] sorted in non-decreasing order.
1. low 1; high n; j 0 1. for i 2 to n
2. while (low high) and (j = 0) 2. x A[i]
3. mid [(low + high)/2] 3. j i–1
4. if x = A [mid] then j mid 4. while (j > 0) and (A[j] > x)
5. else if x < A [mid] then high mid – 1 5. A [j + 1] A [j]
6. else low mid + 1 6. j j–1
7. end while 7. end while
8. return j 8. A [j + 1] x
Selection Sort 9. end for
Let A[1..n] be an array of n elements. A simple and straightforward It is easy to see that the number of element comparisons is
algorithm to sort the entries in A works as follows. First, we find minimum when the array is already sorted in nondecreasing order.
the minimum element and store it in A[1]. Next, we find the In this case, the number of element comparisons is exactly n - 1,
minimum of the remaining n -1 elements and store it in A[2]. We as each element A[i], 2 <i <n, is compared with A[i - 1] only. On the
continue this way until the second largest element is stored in other hand, the maximum number of element comparisons occurs
A[n-1]. It is easy to see that the number of element comparisons if the array is already sorted in decreasing order and all elements
performed by the algorithm is exactly are distinct. In this case, the number of element comparisons is as
n 1 n 1
each element A[i], 2 <i <n, is compared with each entry in the
n ( n 1)
(n i) ( n 1) ( n 2) ... 1 i . subarray A[1..i-1]. The number of element comparisons performed
i 1 i 1 2
by Algorithm insertion sort is between n-1 and n(n-1)/2.
Input : An array A [1..n] of n elements. Quicksort
Output : A [1..n] sorted in non-decreasing order. This sorting algorithm has an average running time of (n log n).
1. for i 1 to n – 1 One advantage of this algorithm over Algorithm merge sort is
2. k i that it sorts the elements in place, i.e., it does not need auxiliary
3. for j i + 1 to n {Find the ith smallest element} storage for the elements to be sorted.
4. if A[j] < A[k] then k j Partitioning algorithm
5. end for Let A[low..high] be an array of n numbers, and x = A[low]. We
6. if k i then interchange A[i] and A[k] consider the problem of rearranging the elements in A so that all
elements less than or equal to x precede x which in turn precedes
7. end for
all elements greater than x. After permuting the elements in the
It is also easy to see that the number of element interchanges is
array, x will be A[w] for some w; low w high. For example, if A
between 0 and n -1. Since each interchange requires three element
assignments, the number of element assignments is between 0 = 5 3 9 2 7 1 8 , and low = 1 and high = 7, then after
and 3(n - 1). The number of element comparisons performed by
Algorithm selection sort is n(n-1)/2. The number of element rearranging the elements we will have 1 3 2 5 7 9 8
assignments is between 0 and 3(n - 1).
Insertion Sort Thus, after the elements have been rearranged, w = 4. The action
This algorithm, which is shown below, works as follows. We begin of rearrangement is also called splitting or partitioning around x,
with the subarray of size 1, A[1], which is already sorted. Next, which is called the pivot or splitting element.
A[2] is inserted before or after A[1] depending on whether it is Input : An array of elements A [low..high].
smaller than A[1] or not. Continuing this way, in the ith iteration, Output : (1) A with its elements rearranged, if necessary, as
A[i] is inserted in its proper position in the sorted subarray A[1::i described above.
-1]. This is done by scanning the elements from index i ¡ 1 down (2) w, the new position of the splitting element A [low].
to 1, each time comparing A[i] with the element at the current 1. i low
position. In each iteration of the scan, an element is shifted one 2. x A[low]
position up to a higher index. This process of scanning, 3. for j low + 1 to high
 5

4. if A [j] x then 4. SIFT-DOWN (A[1..j – 1], 1)

5. i i+1 5. end for
6. if i i j then interchange A[i] and A[j] Algorithm heapsort sortsn elementsin O(n log n) timeand (1)
space.
7. end if
Hashing
8. end for
• The integer h(x) is called the hash value of key x
9. interchange A [low] and A[i]
• A hash table for a given key type consists of
10. w i
11. return A and w – Hash function h
The number of element comparisons performed by the above – Array (called table) of size N
algorithm is exactly n - 1. Thus, its time complexity is (n). • When implementing a dictionary with a hash table,
Sorting Algorithm the goal is to store item (k, o) at index i = h(k).
In its simplest form, Algorithm quicksort can be summarized as Example
follows.The elements A[low::high] to be sorted are rearranged • We design a hash table fora dictionary storing items
using Algorithm split so that the pivot element, which is always (SSN, Name), where SSN (social security number) is a
A[low], occupies its correct position A[w], and all elements that nine-digit positive integer
are less than or equal to A[w] occupy the positions A[low::w - 1], • Our hash table uses an array of size N = 10,000 and
while all elements that are greater than A[w] occupy the positions the hash function
A[w + 1::high]. The subarrays A[low::w - 1] and A[w+1::high] are h(x) = last four digits of x
then recursively sorted to produce the entire sorted array. Hash Functions
The formal algorithm is shown as Algorithm quicksort. • A Hash function is usually specified as the
Input : An array A[1..n] of n elements. composition of two functions:
Output : The elements in A sorted in non-decreasing order. – Hash code map:
1. quicksort (A, 1, n) C : keys integers
Procedure quicksort (A, low, high) Compression map:
1. if low < high then : integers [0, N – 1]
2. SPLIT (A [low..high], w) {w is the new position of A[low]} • The hash code map is applied first, and the
3. quicksort (A, low, w – 1) compression map is applied next on the result, i.e.,
4. quicksort (A, w + 1, high)
h(x) = h(c(x))
4. if A [j] x then
• The goal of the hash function is to "disperse" the
5. end if
keys in an apparently random way
Heapsort
Given an array A[1..n], we sort its elements in nondecreasing COMPLEXITY OF PROBLEMS
order efficiently as follows. First, we transform A into a heap with The Class P
the property that the key of each element is the element itself, i.e., The class of decision problems P consists of those decision
key(A[i]) = A[i], 1 <i <n. Next, since the maximum of the entries in problems whose yes/no solution can be obtained using a
A is now stored in A[1], we may interchange A[1] and A[n] so deterministic algorithm that runs in polynomial number of steps,
that A[n] is the maximum element in the array. Now, the element i.e., in O (nk) steps, for some nonnegative integer k, where n is the
stored in A[1] may be smaller than the element stored in one of its input size.
children. Therefore, we use Procedure shift-down to transform sorting: Given a list of n integers, are they sorted in nondecreasing
A[1..n –1] into a heap. Next, we interchange A[1] with A[n –1] order?
and adjust the array A[1..n –2] into a heap. This process of set disjointness: Given two sets of integers, is their intersection
exchanging elements and adjusting heaps is repeated until the empty?
heap size becomes 1, at which point A[1] is minimum. shortest path: Given a directed graph G = (V;E) with positive
Input : An array A[1..n] of n elements. weights on its edges, two distinguished vertices and a positive
Output : Array A sorted in non-decreasing order. integer k, is there a path from s to t whose length is at most k?
1. MAKEHEAP (A) 2-coloring: Given an undirected graph G, is it 2-colorable?, i.e.,
2. for j n down to 2 can its vertices be colored using only 2 colors such that no two
3. interchange A[1] and A[j] adjacent vertices are assigned the same color? Note that G is 2-
 6
colorable if and only if it is bipartite, that is, if and only if it does no. If, on the other hand, y is in the proper format,
not contain cycles of odd length. then the algorithm continues to check whether it is a
We say that a class of problems C is closed under solution to the instance x of the problem. If it is indeed
complementation if for any problem C the complement of a solution to the instance x, then it halts and answers
is also in C. For instance, the complement of the 2-colorable? yes; otherwise it halts and answers no.
Let us call this problem NOT-2-COLOR. We can show that it is in NP-complete Problems
P as follows. Since 2-COLORING is in P, there is a determinsitic The term NP-complete" denotes the subclass of decision
algorithm A which when presented with a 2-colorable graph halts problems in NP that are hardest in the sense that if one of
and answers yes, and when presented with a graph that is not 2- them is proven to be solvable by a polynomial time
colorable halts and answers no. We can simply design a deterministic algorithm, then all problems in NP are solvable
determinsitic algorithm for the problem NOT-2-COLOR by simply by a polynomial time deterministic algorithm, i.e., NP = P.
interchanging the yes and no answers in Algorithm A. This, For proving that a problem is NP-complete, we need the
informally, proves the following fundamental theorem : following definition.
Theorem 10.1 The class P is closed under complementation. • Definition Let and be two decision problems.
The Class NP We say that reduces to in polynomial time,
The class NP consists of those problems for which there exists symbolized as poly , if there exists a
a deterministic algorithm A which, when presented with a claimed
determinsitic algorithm A that behaves as follows.
solution to an instance of , will be able to verify its correctness
When A is presented with an instance I of problem ,
in polynomial time. That is, if the claimed solution leads to a yes
it transforms it into an instance I of problem such
answer, there is a way to verify this solution in polynomial time.
that the answer to I is yes if and only if the answer to
In order to define this class less informally, we must first define
I is yes. Moreover, this transformation must be
the concept of a nondeterministic algorithm. On input x, a
achieved in polynomial time.
nondeterministic algorithm consists of two phases
• Definition A decision problem is said to be NP-
(a) The guessing phase : In this phase, an arbitrary string
hard if for every problem in NP,
of characters y is generated. It may correspond to a
solution to the input instance or not. In fact, it may poly .
not even be in the proper format of the desired • Definition A decision problems is said to be
solution. It may differ from one run to another of the NP-complete if
nondeterministic algorithm. (1) is in NP, and
(b) The verification phase : In this phase, a deterministic
(2) for every problem in NP, poly .
algorithm defines two things. First, it checks whether
the generated solution string y is in the proper format. Thus, the difference between an NP-complete problem
If it is not, then the algorithm halts with the answer and an NP-hard problem is that must be in the class
NP whereas may not be in NP.
 7

(a) d(r, u) < d(r, v) (b) d(r, u) > d(r, v)

Conceptual MCQs (c) d(r, u) d(r, v) (d) None of these
1. Let LASTPOST, LASTIN and LASTPRE denote the last 6. A program takes as input a balanced binary search tree
vertex visited in a postorder, inorder and preorder with n leaf nodes and computes the value of a function
traversal. Respectively, of a complete binary tree. Which g (x) for each node x. If the cost of computing g (x) is min
of the following is always true? [2000, 2 Marks] (number of leaf-nodes in left – subtree of x,number of leaf
(a) LASTIN = LASTPOST – nodes in right – subtree of x) then the worst – case time
(b) LASTIN = LASTPRE complexity of the program is [2004, 2 Marks]
(c) LASTPRE = LASTPOST (a) (n) (b) (n log n)
(d) None of these (c) (n2) (d) (n2 log n)
2. Consider the following functions : 7. Consider the label sequences obtained by the following
pairs of traversals on a labelled binary tree. Which of
n
f (n) 3n these pairs identify a tree uniquely? [2004, 2 Marks]
(i) Preorder and postorder
g (n) 2 n log 2 n (ii) Inorder and postorder
h(n) = n! (iii) Preorder and inorder
Which of the following is true? [2000, 2 Marks] (iv) Level order and postorder
(a) h (n) is (f(n)) (a) (i) only (b) (ii) and (iii)
(b) h (n) is (g(n)) (c) (iii) only (d) (iv) only
8. Two matrices M1 and M2 are to be stored in arrays A and
(c) g (n) is not (f(n)) B respectively. Each array can be stored either in row–
(d) f (n) is (g(n)) major or column–major order in contiguous memory
locations. The time complexity of an algorithm to compute
3. Let G be an undirected graph with distinct edge weight. M1 × M2 will be [2004, 2 Marks]
Let e max be the edge with maximum weight and emin be (a) best if A is in row – major, and B is in column major
the edge with minimum weight. Which of the following order
statements is false? [2000, 2 Marks] (b) best if both are in row – major order
(a) Every minimum spanning tree of G must contain e min (c) best if both are in column – major order
(b) If emax is in a minimum spanning tree, then its (d) independent of the storge scheme
removal must disconnect G 9. Suppose each set is represented as a linked list with
(c) No minimum spanning tree contains e max elements in arbitrary order. Which of the operations
(d) G has a unique minimum spanning tree among union, intersection, membership, cardinality will
4. Let G be an undirected graph. Consider a depth – first be the slowest? [2004, 2 Marks]
traversal of G, and let T be the resulting depth – first (a) Union only
search tree. Let u be a vertex in G and let v be the first (b) Intersection, membership
new (unvisited) vertex visited after visiting u in the (c) Membership, cardinality
traversal. Which of the following statements is always (d) Union, intersection
true? [2000, 2 Marks]
(a) {u, v} must be an edge in G, and u is a descendant 10. Suppose there are log n sorted lists of n / log n
of v in T elements each. The time complexity of producing a sorted
(b) {u, v} must be an edge in G, and v is a descendant list of all these elements is
of u in T (Hint : Use a heap data structure) [2005, 2 Marks]
(c) If {u, v} is not an edge in G, then u is a leaf in T (a) O (n log log n) (b) (n log n)
(d) If {u, v} is not an edge in G, then u and v must have
(c) (n log n) (d) (n 3/2)
the same parent in T
11. Let G (V, E) be an undirected graph with positive edge
5. Consider an undirected unweighted graph G. Let a
breadth – first traversal of G be done starting from a node r. weights Dijkstra’s single source shortest path algorithm
Let d (r, u) and d (r, v) be the lengths of the shortest paths can be implemented using the binary heap data structure
from r to u and v respectively in G. If u is visited before with time complexity [2005, 2 Marks]
v during the breadth – first traversal, which of the (a) O (| V |2) (b) O (| E | + | V | log | V |)
following statements is correct? [2001, 2 Marks] (c) O (| V | log | V |) (d) O ((| E | + | V |) log | V |)
 8
12. An undirected graph G has n nodes. Its adjacency matrix is (a) There must exist a vertex w adjacent to both u and
given by an n × n square matrix whose (i) diagonal elements v in G
are 0’s and (ii) non-diagonal elements are 1’s. Which one of (b) There must exist a vertex w whose removal
the following is true? [2005, 1 Mark] disconnects u and v in G
(a) Graph G has no Minimum Spanning Tree (MST) (c) There must exist a cycle in G containing u and v
(b) Graph G has a unique MST of cost n – 1 (d) There must exist a cycle in G containing u and all its
(c) Graph G has multiple distinct MSTs, each of cost n – 1 neighbours in G
17. Consider an array representation of an n element binary
(d) Graph G has multiple spanning trees of different costs
heap where the elements are stored from index 1 to index
13. Given two arrays of numbers a 1,...an and b1, .... bn where n of the array. For the element stored at index i of the
each number is 0 or 1, the fastest algorithm to find the largest
array (i n), the index of the parent is [2001, 1 Mark]
span (i, j) such that ai + ai + 1 + .... + aj = bi + bi + 1 + .... + bj,
or report that there is not such span, [2006, 2 Marks] i
(a) Takes O (3n) and (2n) time if hashing is permitted (a) i – 1 (b)
2
(b) Takes O (n 3) and (n2.5) time in the key comparison
i i 1
model (c) (d)
(c) Take (n) time and space 2 2
18. Randomized quicksort is an extension of quicksort where
(d) Take O n time only if the sum of the 2n elements is the pivot is chosen randomly. What is the worst case
an even number complexity of sorting n numbers using randomized quick
14. The median of n elements can be found in O(n) time. Which sort? [2001, 1 Mark]
one of the following is correct about the complexity of quick (a) O(n) (b) O(n log n)
sort, in which median is selected as pivot. [2006, 2 Marks] (c) O(n2) (d) O (n!)
(a) (n) (b) (n log n) 19. In a heap with n elements with the smallest element at the
root, the 7th smallest element can be found in time
(c) (n2) (d) (n3)
[2003, 1 Mark]
15. Consider the following code written in a pass-by-
reference language like FORTRAN and these statements (a) (n log n) (b) (n)
about the code (c) (log n) (d) (1)
20. The usual (n2) implementation of insertion sort to sort
Subroutine swap (ix, iy) an array uses linear search to identify the position where
it = ix an element is to be inserted into the already sorted part
L1 : ix = iy of the array. If instead, we use binary search to identify
L2 : iy = it the position, the worst case running time will
end [2003, 1 Mark]
ia = 3 (a) remain 2
(n ) (b) become (n (log n)2)
ib = 8
(c) become (n log n) (d) become (n)
call swap (ia, ib + 5)
print *, ia, ib 21. The time complexity of computing the transitive closure
end of a binary relation on a set of n element is known to be
[2005, 1 Mark]
S1 : The compiler will generate code to allocate a (a) O(n) (b) O(n log n)
temporary nameless cell, initialize it to 13 and pass (c) O(n3/2) (d) O(n3)
the address of the cell swap 22. Level order traversal of a rooted tree can be done by
S2 : On execution the code will generate a run time error starting from the root and performing [2004, 1 Mark]
on line L1 (a) pre-order traversal
S3 : On execution the code will generate a run time error (b) in-order traversal
on line L2 (c) depth first search
S4 : The program will print 13 and 8 (d) breadth first search
S5 : The program will print 13 and –2
23. An element in ann array X is called a leader, if it is greater
Exactly which of the following sets of statements is / are
than all elements to the right of it in X. The best algorithm to
correct? [2006, 2 Marks]
find all leaders in an array [2007, 2 Marks]
(a) S1 and S2 (b) S1 and S4
(c) S3 (d) S1 and S5 (a) solves it in linear time using a left to right pass of the
16. Let T be a depth first search tree in an undirected graph array
G. Vertices u and v are leaves of this tree T. The degrees (b) solves it in linear time using a right to left pass of the
of both u and v in G are at least 2. Which one of the array
following statements is true? [2006, 2 Marks] (c) solves it using divide and conquer in time (n log n)
(d) solves it in time (n2)
 9
24. Consider the following C program fragment in which i, j and (c) The subset sum problem belongs to the class NP
n are integer variables. (d) The subset sum problem is NP-hard
for (i = n, j = 0, i > 0, i/ = 2, j + = i); 33. G is a graph on n vertices and 2n – 2 edges. The edges of G
Let val (j) denotes the value stored in the variable j after can be partitioned into two-edge-disjoint spanning trees.
termination of the for loop. Which one of the following is Which of the following is not true for G? [2008, 2 Marks]
true? [2007, 2 Marks] (a) For every subset of k vertices, the induced subgraph
has at most 2k – 2 edges
(a) val (j) = (log n) (b) val (j) = n (b) The minimum cut in G has at least two edges
(c) val (j) = (n) (d) val (j) = (n log n) (c) There are two edge-disjoint paths between every pair
25. Which of the following in place sorting algorithms needs of vertices
the minimum number of swaps? [2007, 2 Marks] (d) There are two vertex-disjoint paths between every pair
(a) Quick sort (b) Insertion sort of vertices.
(c) Selection sort (d) Heap sort 34. Consider the following statements about the cyclomatic
complexity of the control flow graph of a program module.
26. To implement Dijkstra’s shortest path algorithm on
Which of these are true? [2009, 2 Marks]
unweighted graphs so that it runs in linear time, the data
I. The cyclomatic complexity of a module is equal to the
structure to be used as [2007, 2 Marks]
maximum number of linearly independent circuits in
(a) queue (b) stack
the graph.
(c) heap (d) B-Tree II. The cyclomatic complexity of a module is the number
27. In a binary max heap containing n numbers, the smallest of decisions in the module plus one, where a decision
element can be found in time [2007, 2 Marks] is effectively any conditional statement in the module.
(a) O (n) (b) O (log n)
III. The cyclomatic complexity can also be used as a
(c) O (log log n) (d) O (1)
number of linearly independent paths that should be
28. Let w be the minimum weight among all edge weights in an
tested during path coverage testing.
undirected connected graph. Let e be a specific edge of
(a) I and II (b) II and III
weight w. Which of the following is false? [2007, 2 Marks]
(c) I and III (d) I, II and III
(a) There is a minimum spanning tree containing e
35. Let A be a problem that belongs to the class NP. Then,
(b) If e is not in a minimum spanning tree T, then in the which one of the following is true? [2009, 1 Mark]
cycle formed by adding e to T, all edges have the same (a) There is no polynomial time algorithm for A
weight. (b) If A can be solved deterministically in polynomial
(c) Every minimum spanning tree has an edge of weight w time, then P = NP
(d) e is present in every minimum spanning tree. (c) If A is NP-hard, then it is NP-complete
29. In an unweighted, undirected connected graph, the shortest (d) A may be undecidable
path from a node S to every other node is computed most 36. Which of the following statements is/are correct regarding
efficiently, in terms of time complexity, by [2007, 2 Marks] Bellman-Ford shortest path algorithm?
(a) Dijkstra’s algorithm starting from S P. Always finds a negative weighted cycle, if one exists.
(b) Warshall’s algorithm Q. Finds whether any negative weighted cycle is reachable
(c) Performing a DFS starting from S from the source. [2009, 1 Mark]
(d) Performing a BFS starting from S (a) P only (b) Q only
30. The inorder and preorder traversal of a binary tree are (c) Both P and Q (d) Neither P nor Q
37. What is the number of swaps required to sort n elements
d b e a f c g and a b d e c f g, respectively
using selection sort, in the worst case? [2009, 1 Mark]
The postorder traversal of the binary tree is [2007, 2 Marks]
(a) (n) (b) (n log n)
(a) d e b f g c a (b) e d b g f c a (c) (n2) (d) (n2 log n)
(c) e d b f g c a (d) d e f g b c a 38. What will be the output of the following C program segment?
31. Which of the following sorting algorithm has the lowest char inChar = ‘A’; [2012, 2 Marks]
worst-case complexity? [2007, 1 Mark] switch (inChar) {
(a) Merge sort (b) Bubble sort case ‘A’ : prinf(“Choice A\n”);
(c) Quick sort (d) Selection sort case ‘B’ :
32. The subset-sum problem is defined as follows: Given a set S case ‘C’ : printf (“Choice B’):
of n positive integers and a positive integer W, determine case ‘D’ :
whether there is a subset of S whose elements sum to W. case ‘E’ :
An algorithm Q solves this problem in O (nW) time. Which default : printf (“No Choice”);}
of the following statements is false? [2008, 2 Marks] (a) No choice
(a) Q solves the subset-sum problem in polynomial time (b) Choice A
when the input is encoded in unary (c) Choice A choice B No choice
(b) Q solves the subset-sum problem in polynomial time (d) Program gives no output as it is erroneous
when the input is encoded in binary
 10
39. Which of the following statements are true?
1. The problem of determining whether there exists a Problem Based MCQs
cycle in an undirected graph is in P. 43. Let s be a sorted array of n integers. Let t(n) denotes the
2. The problem of determining whether there exists a time taken for the most efficient algorithm to determine if
cycle in an undirected graph is in NP. there are two elements with sum less than 1000 in s.
3. If a problem A is NP-complete, there exists a Which of the following statements is true?
non-deterministic polynomial time algorithm to solve [2000, 1 Mark]
A. [2013, 1 Mark] (a) t(n) is 0(1) (b) n t(n) n log 2 n
(a) 1, 2 and 3 (b) 1 and 2 only n n
(c) 2 and 3 only (d) 1 and 3 only (c) n log2 n t(n) < (d) t (n) =
2 2
40. Let G be a graph with n vertices and m edges. What is the
tightest upper bound on the running time of Depth First 44. Let f (n) = n2 log n and g(n) = n (log n)10 be two positive
functions of n. Which of the following statements is
Search on G, when G is represented as an adjacency matrix ?
correct? [2001, 1 Mark]
[2014, Set-1, 1 Mark] (a) f(n) = O(g(n)) and g(n) O(f(n))
(a) (n) (b) (n m) (b) g(n) = O(f (n)) and f(n) O(g(n))
(c) f(n) O(g(n)) and g(n) O(f(n))
(c) (n2 ) (d) ( m2 ) (d) f(n) = O(g(n)) and g(n) = O(f(n))
41. Consider the following rooted tree with the vertex labeled P 45. Maximum number of edges in a n-node undirected graph
as the root : without self loops is [2002, 1 Mark]
n n 1
(a) n2 (b)
P 2
n 1 n
(c) n – 1 (d)
2
46. In the worst case, the number of comparisons needed to
Q R search a singly linked list of length n for a given element
is [2002, 1 Mark]
n
(a) log n (b)
2
U V
T (c) log n2 1 (d) n
S
47. How many undirected graphs (not necessarily connected)
can be constructed out of a given set V = {v1, v2,....,vn}of
n vertices? [2001, 2 Marks]
W
n n 1
(a) (b) 2n
2
The order in which the nodes are visited during an in-order n n 1
traversal of the tree is [2014, Set-3, 1 Mark] (c) n! (d) 2 2
(a) SQPTRWUV (b) SQPTUWRV 48. A weight – balanced tree is a binary tree in which for each
(c) SQPTWUVR (d) SQPTRUWV node, the number of nodes in the left sub tree is at least
42. Consider the decision problem 2CNFSAT defined as follows: half and at most twice the number of nodes in the right
{ | is a satisfiable propositional formula in CNF with at sub tree. The maximum possible height (number of nodes
most two literals per clause } on the path from the root to the furthest leaf) of such a
tree on n nodes is best described by which of the
For example, = (x1 x2) (x1 x 3 ) (x2 x4) is a Boolean following? [2002, 2 Marks]
formula and it is in 2CNFSAT. (a) log2n (b) log4/3n
The decision problem 2CNFSAT is (c) log3n (d) log3/2n
[2014, Set-3, 2 Marks] 49. The number of leaf nodes in a rooted tree of n nodes,
with each node having 0 or 3 children is
(a) NP-Complete.
[2002, 2 Marks]
(b) solvable in polynomial time by reduction to directed
graph reachability. n n 1
(a) (b)
(c) solvable in constant time since any input instance is 2 3
satisfiable. n 1 2n 1
(d) NP-hard, but not NP-complete. (c) (d)
2 3
 11

50. Consider the following algorithm for searching for a given (a) 29 (b) 31
number x in an unsorted array A [l ...n] having n distinct (c) 38 (d) 41
values
55. The following are the starting and ending times of
1. Choose an i uniformly at random from l ...nf
2. If A [i] = x then stop else Goto 1; activities A, B, C, D, E, F, G and H respectively in
Assuming that x is present A, what is the expected chronological order :
number of comparisons made by the algorithm before it as bs cs ae ds ce es fs be de gs ee fe hs ge he. Here, xs denotes
terminates? [2002, 2 Marks] the starting time and xe denotes the ending time of
(a) n (b) n – 1
activity X. We need to schedule the activities in a set of
n
(c) 2n (d) rooms available to us. An activity can be scheduled in a
2
51. The running time of the following algorithm room only if the room is reserved for the activity for its
Procedure A (n) entire duration. What is the minimum number of rooms
If n < = 2 return (1) else return (A( n )); required? [2003, 2 Marks]
(a) 3 (b) 4
is best described by [2002, 2 Marks]
(a) O (n) (b) O (log n) (c) 5 (d) 6
(c) O (log log n) (d) O (1) 56. Let G = (V, E) be a directed graph with n vertices. A path
52. The cube root of a natural number n is defined as the from vi to vj in G is a sequence of vertices (vi, v i + 1,...., vj)
largest natural number m such that m3 n. The such that (vk , vk + 1) E for all k in i through j – 1. A
complexity of computing the cube root of n (n is simple path is a path in which no vertex appears more
represented in binary notation) is [2003, 2 Marks]
than once. Let A be an n × n array initialized as follows
(a) O(n) but not O(n0.5)
(b) O(n0.5) but not O(log n)k for any constant k > 0 1, if ( j, k) E
(c) O (( log n)k) for some constant k > 0 but not O A [ j, k] =
0, otherwise
((log log n)m) for any constant m > 0
(d) O (( log log n)k) for some constant K > 0.5 but not Consider the following algorithm :
O ((log log n)0.5) for i = 1 to n
53. Let G = (V, E) be an undirected graph with a subgraph for j = 1to n
G1= (V1, E1). Weights are assigned to edges of G as for k = 1 to n
follows A [j, k] = max (A [j, k], A [j, i ] + A [i, k]) ;
0, if e E1 Which of the following statements is necessarily true for
(e )
1, otherwise all j and k after termination of the above algorithm?
A single – source shortest path algorithm is executed on [2003, 2 Marks]
the weighted graph (V, E, w) with an arbitrary vertex v1 (a) A [j, k] n
of V1 as the source. Which of the following can always
be inferred from the path costs computed? (b) If A [j, j] n – 1, then G has a Hamiltonian cycle
[2003, 2 Marks] (c) If there exists a path from j to k, A [j, k] contains the
(a) The number of edges in the shortest paths from v1 longest path length from j to k
to all vertices of G (d) If there exists a path from j to k, every simple path
(b) G1 is connected
from j to k contains at most A [j, k] edges
(c) V1 forms a clique in G
(d) G1 is a tree 57. Let A [1,....., n] be an array storing a bit (1 or 0) at each
54. What is the weight of a minimum spanning tree of the location, and f(m) is a function whose time complexity is
following graph? [2003, 2 Marks] (m). Consider the following program fragment written in
a C like language :
b 2 g 19 counter = 0;
j
6 for (i = 1; i < = n; i + +)
1 c 3 8
a 2 14 { if (A [i] = = 1) counter + + ;
2 5
15 else {f (counter) ; counter = 0;}
d h
4 }
4
8 9 The complexity of this program fragment is
8 f i
11 [2004, 2 Marks]
2
(a) (n ) (b) (n log n) and O(n2)
2
e (c) (n) (d) O (n)
 12
58. The time complexity of the following C function is Which are depth first traversals of the above graph?
(assume n > 0) (a) 1, 2 and 4 (b) 1 and 4
int recursive (int n) { (c) 2, 3 and 4 (d) 1, 3 and 4
if (n = = 1) 64. In the following C function, let n m
return (1) ; int gcd (n, m)
else {
return (recursive (n – 1) + recursive (n – 1); if (n % m == 0) return m;
} [2004, 2 Marks] n = n % m;
(a) O (n) (b) O (n log n) return gcd (m, n);
(c) O (n2) (d) O (2n) }
59. The recurrence equation How many recursive calls are made by this function?
[2007, 2 Marks]
T (1) = 1
(a) (log2 n) (b) (n)
T (n) = 2T (n – 1) + n, n 2
evaluates to [2004, 2 Marks] (c) (log2 log n) (d) n
2
(a) 2n + 1 – n – 2 (b) 2n – n
65. What is the time complexity of the following recursive
(c) 2n + 1– 2n – 2 (d) 2n + n
function?
60. Given the following input (4322, 1334, 1471, 9679, 1989,
int Dosomething (int n) {
6171, 6173, 4199) and the hash function x mod 10. Which it (n < = 2)
of the following statements are true? [2004, 1 Mark] return 1;
(1) 9679, 1989 , 4199 hash to the same value. else
(2) 1471, 6171 hash to the same value. return (Dosomething (floor (sqrt (n))) + n);
(3) All elements hash to the same value } [2007, 2 Marks]
(4) Each element hashes to a different value. (a) 2
(n ) (b) (n log2 n)
(a) 1 only (b) 2 only
(c) (log2 n) (d) (log2 log2 n)
(c) 1 and 2 (d) 3 or 4
66. Consider the following graph :
61. The tightest lower bound on the number of comparisons,
in the worst case, for comparison – based sorting is of 2
the order of [2004, 1 Mark]
(a) n (b) n2 b d
1 4
(c) n log n (d) n log n2 1
62. Consider the following three claims : a 3 2 3 f
5
1. (n + k)m = (nm), where k and m are constants 6
n+1 n c 4 e
2. 2 = O(2 )
3. 22n + 1 = O(2n) 7
Which of these claims are correct? [2003, 1 Mark]
(a) 1 and 2 (b) 1 and 3 Which one of the following cannot be the sequence of
(c) 2 and 3 (d) 1, 2 and 3 edges added, in that order, to a minimum spanning tree
63. Consider the following graph : [2003, 1 Mark] using Kruskal’ algorithm? [2006, 2 Marks]
(a) (a – b), (d – f), (b – f), (d – c), (d – e)
(b) (a – b), (d – f), (d – c), (b – f), (d – e)
a (c) (d – f), (a – b), (d – c), (b – f), (d – e)
(d) (d – f), (a – b), (b – f), (d – e), (d – c)
67. A set X can be represented by an array x [n] as follows
1, if i X
x[i]
0 , otherwise
e b f
Consider the following algorithm in which x, y and z are
h Boolean arrays of size n :
algorithm zzz (x[], y[], z []) {
int i;
for (i = 0; i < n; + + i )
z [i] = (x[i] ^ ~ y [i] (~ x [i] ^ y [i])
g }
The set Z computed by the algorithm is
[2006, 2 Marks]
Among the following sequences
(a) X Y (b) X Y
1. abeghf 2. abfehg
3. abfhge 4. afghbe (c) (X – Y) (Y – X) (d) (X – Y) (Y – X)
 13

68. Consider the following recurrence : {

int i, n;
T (n) = 2T n + 1, T (1) = 1 for (i = 2, 9 < = sqrt (n); i + +)
Which one of the following is true? [2006, 2 Marks] if (n % i = = 0)
{printf (“Not Prime\n”); return 0;}
(a) T(n) = (log log n) (b) T(n) = (log n)
return 1;
(c) T(n) = n (d) T(n) = (n) }
Let T(n) denotes the number of times the for loop is executed
69. A priority–queue is implemented as a max–heap. Initially, by the program on input n. Which of the following is true?
it has 5 elements. The level – order traversal of the heap
is given below. (a) T n O n and T n n
10, 8, 5, 3, 2
Two new elements 1 and 7 are inserted in the heap in that (b) T n O n and T n 1
order. The level – order traversal of the heap after the
insertion of the element is [2005, 2 Marks] (c) T(n) = O(n) and T n n
(a) 10, 8, 7, 5, 3, 2, 1 (b) 10, 8, 7, 2, 3, 1, 5 (d) None of these
(c) 10, 8, 7, 1, 2, 3, 5 (d) 10, 8, 7, 3, 2, 1, 5 77. An array of n numbers is given, where n is an even number.
70. How many distinct binary search trees can be created out
The maximum as well as the minimum of these n numbers
of 4 distinct keys? [2005, 2 Marks]
needs to be determined. Which of the following is true about
(a) 5 (b) 14
the number of comparisons needed? [2007, 2 Marks]
(c) 24 (d) 42 (a) At least 2n – c comparisons, for some constant c, are
71. In a complete k-array tree, every internal node has exactly needed
k children. The number of leaves in such a tree with n (b) At most 1.5n – 2 comparisons are needed
internal nodes is [2005, 2 Marks] (c) At least nlog2 n comparisons are needed
(a) nk (b) (n – 1) k + 1 (d) None of the above
(c) n (k – 1) + 1 (d) n (k – 1) 78. Consider the process of inserting an element into a Max
n Heap, where the Max Heap is represented by an array.
72. Suppose T (n) = 2T + n, T(0) = T (1) = 1 Suppose we perform a binary search on the path from the
2
new leaf to the root to find the position for the newly inserted
Which one of the following is false? [2005, 2 Marks] element, the number of comparisons performed is
(a) T (n) = O (n2) (b) T (n) = (n log n) [2007, 2 Marks]
2
(c) T (n) = (n ) (d) T (n) = O (n log n) (a) (log2 n) (b) (log2 log2 n)
73. A scheme for storing binary trees in an array X is as follows. (c) (n) (d) (n log2 n)
Indexing of X starts at 1 instead of 0. The root is stored at 79. A complete n-array tree is a tree in which each node has n
X[1].For a node stored at X[i], the left child, if any, is stored children or no children. Let l be the number of internal nodes
in X[2i] and the right child, if any in X[2i | 1]. To be able to and L be the number of leaves in a complete n-array tree. If
store any binary tree on n vertices the minimum size of X L = 41, and l = 10, what is the value of n? [2007, 2 Marks]
should be [2007, 2 Marks] (a) 3 (b) 4
(a) log2 n (b) n (c) 5 (d) 6
(c) 2n + 1 (d) 2n – 1 80. Consider a hash table of size seven, with starting index zero,
74. Consider a weighted complete graph G on the vertex set {v1, and a hash function (3x + 4) mod 7. Assuming the hash table
v2, .... vn} such that the weight of the edge (vi, vj) is 2|i – j|. is initially empty, which of the following is the contents of
The weight of a minimum spanning tree of G is the table when the sequence 1, 3, 8, 10 is inserted into the
[2007, 2 Marks] table using hashing? Note that ‘–’ denotes an empty location
(a) n – 1 (b) 2n – 2 in the table. [2007, 2 Marks]
(a) 8, _, _, _, _, _, 10 (b) 1, 8, 10, _, _, _, 3
n (c) 1, _, _, _, _, _, 3 (d) 1, 10, 8, _, _, _, 3
(c) (d) n 2
2 81. The maximum number of binary trees that can be formed
75. Consider the polynomial p(x) = a0 + a1x + a2x2 + a3x3, where with three unlabelled nodes is [2007, 1 Mark]
(a) 1 (b) 5
a i 0, i . The minimum number of multiplications needed
(c) 4 (d) 3
to evaluate p on the input x is [2007, 2 Marks] 82. The height of a binary tree is the maximum number of edges
(a) 3 (b) 4 in any root to leaf path. The maximum number of nodes in a
(c) 6 (d) 9 binary tree of height h is [2007, 1 Mark]
76. Consider the following C code segment: [2007, 2 Marks] (a) 2h – 1 (b) 2h–1 – 1
int is Prime (n) (c) 2h + 1 – 1 (d) 2h + 1
 14

83. We have a binary heap on n elements and wish to insert n 89. Consider the following functions:
more elements (not necessarily one after another) into this f(n) = 2n
heap. The total time required for this is g(n) = n!
[2008, 2 Marks] h(n) = n logn
(a) (log n) (b) (n) Which of the following statements about the asymptotic
(c) (n log n) (d) (n2) behaviour of f(n), g(n) and h(n) is true? [2008, 2 Marks]
84. You are given the postorder traversal, P, of a binary search (a) f(n) = O(g(n)); g(n) = O(h(n))
tree on the n elements 1, 2, ..., n. You have to determine the (b) f(n) = (f(n)); g(n) = O(h(n))
unique binary search tree that has P as its postorder traversal. (c) g(n) = O(f(n)); h(n) = O(f(n))
What is the time complexity of the most efficient algorithm (d) h(n) = O(f(n)); g(n) = (f(n))
for doing this? [2008, 2 Marks] 90. The Breadth First Search algorithm has been implemented
(a) (log n) using the queue data structure. One possible order of visiting
(b) (n) the nodes of the following graph is [2008, 1 Mark]
(c) (n log n)
(d) None of the above, as the tree cannot be uniquely
determined M N O

–3
b e
2 2
1 –5 1 1
85. a c h f R Q P
2 3 2 3
2 (a) MNOPQR (b) NQMPOR
d g
(c) QMNPRO (d) QMNPOR
91. The most efficient algorithm for finding the number of
Dijkstra’s single source shortest path algorithm when run connected components in an undirected graph on n vertices
from vertex a in the above graph, computers the correct and m edges has time complexity [2008, 1 Mark]
shortest path distance to [2008, 2 Marks] (a) (n) (b) (m)
(a) only vertex (b) vertices a, e, f, g, h (c) (m + n) (d) (mn)
(c) vertices a, b, c, d (d) all the vertices 92. In quick sort, for sorting n elements, the (n/4) the smallest
86. Consider the Quick sort algorithm. Suppose there is a element is selected as pivot using an O(n) time algorithm.
procedure for finding a pivot element which splits the list What is the worst case time complexity of the quick sort?
into two sub-lists into two-sub-lists each of which contains [2009, 2 Marks]
at least one-fifth of the elements. Let T(n) be the number of (a) (n) (b) (n log n)
comparisons required to sort n elements. Then (c) (n2) (d) (n2 log n)
93. Consider the following graph: [2009, 2 Marks]
(a) T n 2T n / 5 n [2008, 2 Marks]

(b) T n 2T n / 5 T 4n / 5 n
b 2 e
5
5
(c) T n 2T 4n / 5 n
6 6
(d) T n 2T n / 2 n a d 3 g

87. A B-tree of order 4 is built from scratch by 10 successive 6

5 4
insertions. What is the maximum number of node splitting 3
c f
operations that may take place? [2008, 2 Marks] 6
(a) 3 (b) 4
(c) 5 (d) 6 Which one of the following is not the sequence of edges
88. The minimum number of comparisons required to determined added to the minimum spanning using Kruskal’s algorithm?
if an integer appears more than n/2 times in a sorted array of (a) (b, e) (e, f) (a, c) (b, c) (f, g) (c, d)
n integers is [2008, 2 Marks] (b) (b, e) (e, f) (a, c) (f, g) (b, c) (c, d)
(a) (n) (b) (log n) (c) (b, e) (a, c) (e, f) (b, c) (f, g) (c, d)
(c) (log *n) (d) (1) (d) (b, e) (e, f) (b, c) (a, c) (f, g) (c, d)
 15

94. The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an 99. What is the time complexity of Bellman-Ford single-
initially empty hash table of length 10 using open addressing source shortest path algorithm on a complete graph of n
vertices? [2013, 1 Mark]
with has function h(k) = k mod 10 and linear probing. What
(a) (n2) (b) (n2 log n)
is the resultant has table? [2009, 2 Marks] (c) (n3) (d) (n3 log n)
(a) 0 (b) 0 100. Consider the following operation along the Enqueue and
1 1
Dequeue operations on queues, where k is a global
parameter.
2 2 2 12
Multi-Dequeue(Q){
3 23 3 13 m=k
4 4 while (Q is not empty) and (m > 0){ Dequeue(Q)
5 15 5 5 m=m–1
6 6 }
7 7 }
8 18 8 18
What is the worst case time complexity of a sequence of
n queue operations on an initially empty queue?
9 9
[2013, 2 Marks]
(c) (d) 0 (a) (n) (b) (n + k)
0
(c) (nk) (d) (n2)
1 1
101. Consider the following function:
2 12 2 12, 2 int unknown (int n) {
13, 3, int i, j, k=0;
3 13 3
23 for (i=n/2; i<=n; i++)
4 2 4 for (j=2; j<=n; j=j*2)
5 3 5 5, 15 k = k + n/2;
6 return (k);
6 23
7 }
7 5
The return value of the function is
8 18 8 18
[2013, 2 Marks]
9
9 15 (a) (n2) (b) (n2 log n)
95. The running time of an algorithm is represented by the (c) (n3) (d) (n3 log n)
following recurrence relation [2009, 2 Marks] 102. An operating system uses the Banker’s algorithm for
deadlock avoidance when managing the allocation of three
n , n 3 resource types X, Y, and Z to three processes P0, P1, and
T n n P2. The table given below presents the current system state.
T cn, otherwise
3 Here, the Allocation matrix shows the current number of
Which one of the following represents the time complexity resources of each type allocated to each process and the
Max matrix shows the maximum number of resources of
of the algorithm?
each type required by each process during its execution.
(a) (n) (b) (n log n)
(c) (n2) (d) (n2 log n) Allocation Max
96. Two alternative packages A and B are available for
processing a database having 10 k records. Package A X Y Z X Y Z
requires 0.0001 n2 time units and package B requires 10n P0 0 0 1 8 4 3
log10n time units to process n records. What is the smallest P1 3 2 0 6 2 0
value of k for which package B will be preferred over A? P2 2 1 1 3 3 3
[2010, 1 Mark]
(a) 12 (b) 10 There are 3 units of type X, 2 units of type Y and 2 units of
(c) 6 (d) 5 type Z still available. The system is currently in a safe state.
97. Which one of the following is the tightest upper bound Consider the following independent requests for additional
that represents the number of swaps required to sort n resources in the current state:
numbers using selection sort? [2013, 1 Mark] REQ1: P0 requests 0 units of X, 0 units of Y and 2 units of Z
(a) O(log n) (b) O(n) REQ2: P1 requests 2 units of X, 0 units of Y and 0 units of Z
(c) O(n log n) (d) O(n2) Which one of the following is TRUE?
98. Which one of the following is the tightest upper bound [2014, Set-1, 2 Marks]
that represents the time complexity of inserting an object (a) Only REQ1 can be permitted.
into a binary search tree of n nodes? [2013, 1 Mark] (b) Only REQ2 can be permitted.
(a) O(1) (b) O(log n) (c) Both REQ1 and REQ2 can be permitted.
(c) O(n) (d) O(n log n) (d) Neither REQ1 nor REQ2 can be permitted.
 16
103. Suppose a polynomial time algorithm is discovered that array as the pivot. Then the tightest upper bound for the
correctly computes the largest clique in a given graph. In worst case performance is [2014, Set-3, 1 Mark]
this scenario, which one of the following represents the (a) O (n2) (b) O (n log n)
correct Venn diagram of the complexity classes P, NP and (c) (n log n) (d) O (n3)
NP Complete (NPC)? [2014, Set-1, 2 Marks] 107. Consider a hash table with 100 slots. Collisions are resolved
using chaining. Assuming simple uniform hashing, what is
NP the probability that the first 3 slots are unfilled after the first
3 insertions? [2014, Set-3, 2 Marks]
P
(a) (97×97×97)/1003 (b) (99×98×97)/1003
(a) (c) (97×96×95)/1003 (d) (97×96×95)/(3!×1003)

NPC Common Data MCQs

Common Data for Questions 108 and 109
Consider the following C functions :
int f1 (int n)
P NP {
if (n == 0 || n == 1)
(b) return n;
else
return (2*f1 (n – 1) + 3 * f1(n – 2));
NPC }
int f2 (int n)
{
int i;
P=NP int X[N], Y[N], Z[N];
NPC
X[0] = Y[0] = Z[0] = 0;
X[1] = 1; Y[1] = 2; Z[1] = 3;
(c)
for (i = 2; i <= n; i++) {
X[i] = Y[i – 1] + Z[i – 2];
Y[i] = 2*X[i];
Z[i] = 3*X[i];
}
P=NP=NPC return X[n];
}
108. The running time of f1 (n) and f2 (n) are
(d) [2008, 2 Marks]
(a) (n) and (n) (b) (2n) and (n)
(c) (n) and (2n) (d) (2n) and (2n)
109. f1 (8) and f2 (8) return the values [2008, 2 Marks]
104. Consider a hash table with 9 slots. The hash function is (a) 1661 and 1640 (b) 59 and 59
h(k) = k mod 9. The collisions are resolved by chaining. (c) 1640 and 1640 (d) 1640 and 1661
The following 9 keys are inserted in the order: 5, 28, 19, 15, Common Data for Questions 110 and 111
20, 33, 12, 17, 10. The maximum, minimum, and average chain Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}.
lengths in the hash table, respectively, are Entry Wij in the matrix W below is the weight of the edge {i, j}
[2014, Set-1, 2 Marks]
0 1 8 1 4
(a) 3, 0, and 1 (b) 3, 3, and 3
(c) 4, 0, and 1 (d) 3, 0, and 2 1 0 12 4 9
105. An ordered n-tuple (d1, d2, .., dn) with d1 d2 ... dn is 8 12 0 7 3
called graphic if there exists a simple undirected graph with W= 1 4 7 0 2
n vertices having degrees d1, d2, ..., dn respectively. Which 4 9 3 2 0
of the following 6-tuples is NOT graphic?
[2014, Set-1, 2 Marks] 110. What is the minimum possible weight of a spanning tree T in
(a) (1, 1, 1, 1, 1, 1) (b) (2, 2, 2, 2, 2, 2) this graph such that vertex 0 is a leaf node in the tree T?
(c) (3, 3, 3, 1, 0, 0) (d) (3, 2, 1, 1, 1, 0) [2010, 2 marks]
106. You have an array of n elements. Suppose you implement (a) 7 (b) 8
quicksort by always choosing the central element of the (c) 9 (d) 10
 17
111. What is the minimum possible weight of a path P from vertex 117. What is the average length of the correct answer above
1 to vertex 2 in this graph such that P contains at most 3 question ?
edges? [2010, 2 Marks] [2007, 2 Marks]
(a) 7 (b) 8 (a) 3 (b) 2. 1875
(c) 9 (d) 10 (c) 2.25 (d) 1.9375
Statements for Linked Answer Questions 112 and 113 Statements for Linked Answer Questions 118 and 119
The subset - sum problem is defined as follows : Given a set Consider the following C function :
of n positive integers, S = {a1, a2, a3, ...an}, and positive double foo (int n) {
integer W, is there a subset of S whose elements sum to W? int i ;
A dynamic program for solving this problem uses a 2- double sum;
dimensional Boolean array, X, with n rows and W + 1 if (n = = 0) return 1 .0;
columns. X[i, j], 1 i n,0 j W, is true if and only if there else {
is a subset of {a1, a2, ....ai} whose elements sum to j sum = 0.0;
112. Which of the following is valid for 2 i n and for (i = 0; i < n; i + +)
ai j W? [2008, 2 Marks] sum + = foo (i) :
(a) X [i, j] = X [i – 1, j] X[i, j – ai] return sum;
(b) X [i, j] = X [i – 1, j] X[i – 1, j – ai] }}
(c) X [i, j] = X [i – 1, j] X[i, j – ai] 118. The space complexity of the above function is
(d) X [i, j] = X [i – 1, j] X[i – 1, j – ai] [2005, 2 Marks]
113. Which entry of the array X, if true, implies that there is (a) O (1) (b) O (n)
a subset whose elements sum to W? [2008, 2 Marks] (c) O (n!) (d) O (nn)
(a) X[1, W] (b) X[n, 0] 119. Suppose we modify the above function foo () and store
(c) X[n, W] (d) X[n –1, n] the values of foo (i), 0 < = i < n, as and when they are
Statements for linked Answer Questions 114 and 115
computed. With this modification, the time complexity for
Consider the following C program that attempts to locate
function foo () is significantly reduced. The space
an element X in an array Y [] using binary search. The
complexity of the modified function would be
program is erroneous.
1. f (int Y[10], int X) { [2005, 2 Marks]
2. int u, j, k; (a) O (1) (b) O (n)
3. i = 0; j = 9; (c) O (n2) (d) O (n!)
4. do { Statements for Linked Answer Questions 120 and 121
5. k = (i + j) / 2 We are given 9 tasks T1, T2, ....T9. The execution of each
6. if (Y[k] < x) i = k; else j = k; task requires one unit of time. We can execute one task
7. } while ((Y[k]! = X) & &(i < j)); at a time. Each task Ti has a profit Pi and deadline di.
8. if (Y[k]) = = x) print f (“x is in the array”); Profit Pi is earned if the task is completed before the end
9. else print f (“x is not in the array”); of the di th unit of time.
10. }
114. On which of the following contents of Y and x does the Task T1 T2 T3 T4 T5 T6 T7 T8 T9
program fail? [2008, 2 Marks] Profit
15 20 30 18 18 10 23 16 25
(a) Y is [1 2 3 4 5 6 7 8 9 10 ] and x < 10 Deadline 7 2 5 3 4 5 2 7 3
(b) Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
(c) Y is [2 2 2 2 2 2 2 2 2 2] and x > 2 120. Are all tasks completed in the schedule that gives
(d) Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and maximum profit? [2005, 2 Marks]
x is even (a) All tasks are completed
115. The correction needed in the program to make it work (b) T1 and T6 are left out
properly is [2008, 2 Marks] (c) T1 and T8 are left out
(a) change line 6 to ; if (Y [k] < x) i = k + 1; (d) T4 and T6 are left out
else j = k – 1; 121. What is the maximum profit earned? [2005, 2 Marks]
(b) change line 6 to ; if (Y [k] < x) i = k – 1; (a) 147 (b) 165
else j = k + 1; (c) 167 (d) 175
(c) change line 6 to ; if (Y [k] < = x) i = k; else j = k; Statements for Linked Answer Questions 122 and 123
(d) change line 7 to ; }while ((Y [k] = = x) & &(i < j)) In a permutation a1 .... an of n distinct integers, an inversion is
Statements for Linked Answer Questions 116 and 117 a pair (ai , aj) such that i < i and ai > aj.
Suppose the letters a, b, c, d, e, f have probabilities
122. If all permutations are equally likely, what is the expected
1 1 1 1 1 1 number of inversions in a randomly chosen permutation
, , , , , respectively..
2 4 8 16 32 32 of 1 ... n? [2003, 2 Marks]
116. Which of the following is the Huffman code for the letter n n 1 n n 1
a, b, c, d, e, f ? [2007, 2 Marks] (a) (b)
(a) 0, 10, 110 , 1110, 11110, 11111 2 4
(b) 11, 10, 011, 010, 001, 000 n n 1
(c) 11, 10, 01, 001, 0001, 0000 (c) (d) 2n [log 2 n]
(d) 110, 100, 010, 000, 001, 111 4
 18
123. What would be the worst case time complexity of the of keys in increasing order. Then what approximately
insertion sort algorithm, if the inputs are restricted to is the average number of keys in each leaf level node.
permutations of 1... n with at most n inversions? (i) In the normal case, and
[2003, 2 Marks] (ii) with the insertion as in (b). [2000, 5 Marks]
(a) (n2) (b) (n log n) 127. Consider a rooted n node binary tree represented using
(c) (n1.5) (d) (n) pointers. The best upper bound on the time required to
Statements for Linked Answer Questions 124 and 125: determine the number of subtrees having exactly 4 nodes is
A sub-sequence of a given sequence is just the given sequence O (nalogbn). Then the value of a + 10b is ______.
with some elements (possibly none or all) left out. We are given [2014, Set-1, 1 Mark]
two sequence X[m] and Y[n] of lengths m and n, respectively, 128. Consider an undirected graph G where self-loops are not
with indices of X and Y starting from 0. allowed. The vertex set of G is {(i, j): 1 i 12, 1 j 12}.
124. We wish to find the length of the Longest Common Sub- There is an edge between (a, b) and (c, d) if |a – c| 1 and
sequence (LCS) of X[m] and Y[n] as l(m, n), where an |b – d| 1. The number of edges in this graph is _________.
incomplete recursive definition for the function l (i, j) to [2014, Set-1, 2 Marks]
compute the length of the LCS of X[m] and Y[m] is given 129. Consider the expression tree shown. Each leaf represents a
below numerical value, which can either be 0 or 1. Over all possible
l(i, j) = 0 either i = 0 or j = 0 choices of the values at the leaves, the maximum possible
= expr 1, if i, j > 0 and X[i – 1] = [j – 1] value of the expression represented by the tree is ___.
= expr 2, if i, j > 0 and X[i – 1] = Y[j – 1]
Which one of the following options is correct?
(a) expr 1 l (i – 1, j) + 1 [2009, 2 Marks]
(b) expr 1 l (i, j – 1)
(c) expr 2 max {(l (i –1, j) , l (i, j – 1)}
(d) expr 2 max {(l (i –1, j – 1) , l (i, j)}
125. The values of (i, j) could be obtained by dynamic programming
based on the correct recursive definition of l (i, j) of the form
given above, using an array L [M, N], where M = m + 1 and
N = n + 1, such that L [i, j] = l (i, j).
Which one of the following statements would be true 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1
regarding the dynamic programming solution for the
recursive definition of (i, j)? [2009, 2 Marks] [2014, Set-2, 2 Marks]
(a) All element L should be initialized to 0 for the values 130. The number of distinct minimum spanning trees for the
of (i, j) to be properly computed weighted graph below is _____ [2014, Set-2, 2 Marks]
(b) the values of l (i, j) may be computed in a row major
order or column major order of L(M, N)
2
(c) the values of l (i, j) may be computed in a either row
major order or column major order of L (M, N)
2 1 2 1
(d) L[p, q] needs to be computed before L[r, s] if either
p < r or q < s
2
Numerical Answer Questions 2
1
2
126. (a) Suppose you are given an empty B+-tree where 1 1
each node (leaf and internal) can store up to 5 key
values. Suppose values 1, 2, ... 10 are inserted, in 2 2
order, into the tree, show the tree pictorially
(i) After 6 insertions, and 131. The length of the shortest string NOT in the language (over
(ii) After all 10 insertions = {a, b}) of the following regular expression is
Do NOT show intermediate stages. ______________. [2014, Set-3, 1 Mark]
(b) Suppose instead of splitting a node when it is full, a*b* (ba)*a*
we try to move a value to the left sibling. If there 132. Suppose we have a balanced binary search tree T holding n
is no left sibling, or the left sibling is full, we split numbers. We are given two numbers L and H and wish to
the node. Show the tree after values, 1, 2, ..., 9 have sum up all the numbers in T that lie between L and H. Suppose
been inserted. Assume, as in (a) that each node can there are m such numbers in T. If the tightest upper bound on
hold up to 5 keys. the time to compute the sum is O (na logb n + mc logd n), the
(c) In general, suppose a B+-tree node can hold a value of 10b + 100c + 1000d is _______.
maximum of m keys, and you insert a long sequence [2014, Set-3, 2 Marks]
 19

G(x) is calculated for each x.

CONCEPTUAL MCQs
With the behaviour, we can easily suggest that
1. (b) Lets, draw a tree in context with the given statements program has linear worst case complexity which is
given by (n).
7. (b) For a tree we not only require in order & preorder
but also postorder traversal.
Preorder & postorder help to determine the roots of
binary subtrees, inorder arranges those roots in
order.
Hence (b) is correct option.
8. (d) Since the matrices are stored in array, there is no
dependence of time complexity on row major or
column major. Here only the starting address is
known & on the basis of indexes the next memory
LASTIN–inorder–GDHBIEJAC locations are calculated.
LASTPRE–Preorder–ABDGHEIJC Hence (d) is correct option.
LASTPOST–Postorder–GHDIJEBCA 9. (d) Membership & cardinality functions takes constt.
Here we can see that last vertex is C ln LASTIN and time i.e. 0(1), but union & intersection require
LASTPRE. emparison of 1 element with all the other elements so
2. (d) Solution is obtained by solving the given f (n) and these two would be slowest.
h(n) cannot be solved further. We need to solve g(n). Hence (d) is correct option.
10. (a) There are log n sorted lists, with n / logn elements
12 C each, total elements n. We need to merge these heap
A & procedure sorted. Merging take.
22 log n time & sorting takes 0(n log n).
4
Overall to produce sorted result take 0(n log log n)
E 9 F 11. (b) Dijkstra Algorithm for every vertex we consider the
8
binary heap to find shortest path. This take V logV
6 7
3 time.
B And we need to transverse each edge 1 time atleast.
14 D
So overall complexity O ((| E | + | V |) log | V |)
Solving g(n) will bring out a relation related to f (n). The 12. (c) Given adjacency matrix of order 4 is 4*4
complexity of f (n) is hence, f (n) is O(g (n)). 0 0 1 1 1
3. (c) The minimum spanning tree will contain both
1 1 0 1 1
maximum and minimum edge.
For example, 2 1 1 0 1
The edge ED is the minimum edge with weight = 3 3 1 1 1 0
The edge CF is maximum edge with weight = 22
4. (c) G is an undirected graph. Now, when G is traversed
via depth first. The resultant obtained is T (depth
first tree). V is the first vertex visited after visiting u.
Now, if u and v are not connected, then no cycle is
formed and u is a leaf in T.
However, if u and v are connected, then a cycle will There can be many min spaning but all of n – 1 cost
be formed.
5. (c) In BFS if u is visited before v then either u is some
levels before v or u &v are at the same level but u
is leftmost in v .
d(r,u) # d(r,v)
Hence (c) is correct option
6. (a) As given, input is a balanced binary search tree with
So on.
n leaf nodes.
 20
13. (c) Given that each number of 0 or 1. it with the last element, then we run min heapify
Now, to achieve algorithm, which brings next the smallest element on
ai + ai + 1 + ... + aj = bi + bi + 1 + ... + bj top. This procedure take 0(log n) time.
We need to find the sum total of LHS and RHS and We need to run it for 7 times. So tight bound
then have to compare. (7 log n) = (log n)
We need to do this from very starting like first we need Hence option (c) is correct.
to check. 20. (a) Binary search is efficient when the sorted sequence
Whether a1 = b1 is there, but the worst case scenario for insertion
If not then whether a1 + a2 = b1 + b2 sort would not be sorted sequence so even using
And so on .... binary search instead of linear search the complexity
This will take n comparisons. of comparisons will remain ().
Therfore, the fastest algorithm to find the largest span 21. (d) Warshall’s algorithm might be used for calculation
takes (n) time and space. transitive closure of a set with a elements. This
14. (c) In quick sort the piuot is found in logn time & this runs algorithm has complexity O( ). In transitive closure
for n times. So complexity of Quick sort is 0(nlogn) but two binary relations are there 4 both ranges are the
same set.
since given the median as piuot found in 0(n)
The require three for loops so 0( ).
So for n elements to sort this algorithm will take 0(n2) Hence (d) is correct option.
15. (b) S1 : Yes the compiler will generate a temporary 22. (d) Level order traversal is done by traversing all the
nameless cell & initialize it to 13 and pass to vertices in a particular level & them moving to next
swap. level.This is some as breadth first search where level
S2 : No error by level search is done. Hence (d) is correct option.
S3 : No error 23. (c) In quick sort (divide & conquer) algorithm after every
S4 : Program will print 13 and 8
run we being 1 element at its right place i.e. all the
S5 : False.
Hence (b) is correct option. elements in the left are smaller & in the right are greater
16. (a) Let the graph G be. than it.
So we can apply quick sorts divide & conquer method
of complexity 0(nlogn) to do this, to check whether all
elements in right are smaller than it or not.
24. (c) Here after every iteration the value of i=i/2, & j is the
summation of these i till i reaches to 1.
n
j n n / 2 n / 22......n / 2log 2
(a) is correct since W is the common vertex.
(b) W is removed but u & v are not dis-connected. Sum of this series.
(c) No cycle containing u & v exist. Would give ø(n) order.
(d) Not necessary the graph can be also. 25. (a) Heap is implemented using array & to find maximum or
a minimum element in array we take only n maximum
comparison.
w So complexity is ø(n)
26. (c) Heap is used to implement Dijakstra’s shortest path
u algorithm on unweighted graphs so that it runs on
v
linear time because of the property of heap discussed
17. (b) This is a basic question. We know that to reach a below.
node on level i, the distance to the root is i–1. This Heap is a data structures that allows the following:
implies that if an element is stored at index i of the 1. Add: Heap allows the addition of an element with some
array, then index of the parent is n. priority associated with each element.
18. (b) n randomized quicksort pivot is chosen randomly, 2. Remove: The element with the highest priority is
the case complexity of sorting n. In that case the removed and returned.
worst case O(n2) of quicksort become O(n log n) of 3. Peak : Heap increases the priority of an element to the
randomize quicksort. highest without removing the element from the list.
Hence (b) is correct option. Now, to implement a heap, take a list of elements and
19. (c) Here we can follow simple procedure, we can run according to the priority. The highest priority is O(n)
heap sort for 7 iterations. In each iteration the top time to implement the Dijakstra’s shortest path
most element is the smallest, we note & then replace algorithm on unweighted graphs.
 21
27. (a) Time taken by binary max heap to identify the max 33. (d) Consider this graph with n = 4
element is O(1). Therefore, the time taken by binary
max heap to identify the smallest element is O(n).
28. (d) Minimum weight w
Edge e
Weight w
Now, w is the minimum weight among the edges.
There is a possibility that two edges may contain the
same weight w. This would then be added to minimum
spanning tree. Two spanning trees
Now, when the edge, e is added to the minimum tree
we get a circuit.
Therefore, to avoid the circuit, e cannot be included in
the minimum spanning tree.
29. (d) Since the graph is unweighted and undirected so no
sense in using Dijikstra or Warshall also their
complexities are 0(n2) &0(n3)respectively.
Statement (b), (c) & (d) are correct.
BFS starting from S, traverses all the adjacent nodes,
& then their adjacent nodes, this calculates shortest
path with min complexity. Hence (d) is correct option.
30. (a) In order d b e a f c g
preorder a b d e c f g
1st element of pre order is root

min cent has 3 edges.

Two edge & vertex disjoint paths are present can be
in preorder b is before d e. & c is before f g. seen in two spanning trees but option (A) is false for
K=2 2K – 2= i.e 2 edges
should be there but it is not true.
34. (b) Statement I is incorrect.
debfgca The cyclomatic complexity of the module is not equal
to maximum number of linearly independent circuits in
the graph.
31. (a) The complexities of worst case when all the elements Statement II is correct.
are reverse sorted for all algorithms are. The cyclomatic complexity of a module is the number
Norge 0(nlog2n) of decisions in the module plus one, where a decision
is effectively any conditional statement in the module.
Quick 0( )
Statement III is correct.
Selection 0( ) The cyclomatic complexity can also be used as a
Bubble 0( ) number of linearly independent paths that should be
Merge no has no effect of input nature since it keeps tested during path coverage testing.
35. (c) Problems which are both NP &NP hard are called NP
on dividing into
complete problems. So option (C) is correct option.
2 problems of size 4/2 so complexity is lower then other (a) Can’t be correct since P€NP, so there can be any
three. Algorithm with P time.
32. (b) W is an integer so the time taken by the algorithm is (b) Is not true, if some solved deterministically but if
(n) only. Since subset problem is NP complete, it not NP complete then can’t be P=NP.
(d) Is not correct because some problems which are
should be in class NP & NP hard, so option (C) & (D)
NP decidable under certain conditions.
are true. 36. (b) The Bellman-Ford algorithm solves the single-source
Using unary integer the algorithm will be solved in (n) shortest paths problem for a graph. This is done with
time but using binary it would take more time depending both positive and negative edge weights.
upon no. of bits. Let pictorially understands the concept of the Bellman-
Ford algorithm.
 22

t x executed then case B and then case C and then case D

5 and E and finally the default case will be executed and
6 –2 print.
–3 Choice A
8 –4 7 Choice B No choice
s 0 39. (a) Using Depth First search Algorithm to check if there
2
is a cycle in an undirected graph. Whenever a back
7 edge is encountered in DFS then gives undirected
y 9 z graph which has a cycle.
Initialization 1. Also if there is a cycle in the undirected graph,
we must encounter a back edge in DFS. DFS
t 5 x can be done a O (| E | + | V |) time for graph G
2 4 = (V, E). So it can be in P.
6 –2
–3 2. P NP, This is also in NP.
3. NP-complete problem A NP by definition
s 0 8 –4 7 every problem in NP can be solved in
2 polynomial time using non-deterministic turing
7 7, s 2, t machine. So, answer is (a) i.e., 1, 2, 3 are true.
9 40. (c) Let the graph G contains n vertices. When the graph
y z is represented as an adjacency list, the depth first
After pass 1 search of the graph takes (m + n) time.
However, when the graph is represented as Adjacency
t 5 x matrix, since it has a size of n × n, to perform depth
6 first search on the graph, for every vertex, we
6 –2
–3 transverse the row corresponding to that vertex to
find out all adjacent vertices. This need to be
s 0 8 –4 7 performed for all n vertices (n times for each vertex).
2 So, the time complexity becomes
7 (n × n) = (n2)
7, s
9 C
y z F
After pass 2
A B
t 5 x
6 4
6 –2
–3 E
8 7 D
s 0 –4 (Graph G)
2
Adjacency List:–
7 7, s 2, t
9 Vertex Neighbours
y z
After pass 3 A B, C, E, F
The order of edges examined in each pass B A, D
(t, x), (t, z), (x, t), (y, x), (y, t), (y, z), (z, x), (z, s), (s, t), C A, F
(s, y). D B
37. (c) In selection sort the worst case would be when the
elements are reverse sorted, here the algorithm selects E A
the min element the first element, and during linear F A, C
scan if element found min then a swap takes place.
So during n iterations maximum. Adjacency Matrix:
n swap can occur in each iteration. A B C D E F
No. of swaps = n[n + (n – 1) + (n – 2) ............1]
= (n2) is correct option. A 0 1 1 0 1 1
38. (c) In switch case statements, there can be more cases, B 1 0 0 1 0 0
which case satisfied the condition will be executed, so
C 1 0 0 0 0 1
we have to add break statement after every case in
switch. If there is no break statement then all switch D 0 1 0 0 0 0
cases will be executed and default case will also be E 1 0 0 0 0 0
executed.
In the given program, there is no error so, case A is F 1 0 1 0 0 0 6 6
 23
41. (a) The in order transversal is as : So, the maximum possible height would be the range
left, root, middle, right and therefore, is log1n.
Nodes are visited in SQPTRWUV order. 49. (d) Consider following rooted trees
42. (b) 2 SAT is in P. This we can prove by reducing 2 SAT a
to directed graph reachability problem which is
known to be in P.
Procedure for reducing 2 SAT to reachability problem : b c d
1. Let be CNF with clauses of length 2 and let P be
the set of propositional variable (literals) in e f g
2. Build a graph G = (V, E) with V = P { plp P}
n=4
and (x, y) Eiff there is a clause in that is (2n + 1)/3 = 3
equivalent to x y (all the clauses are converted No. of leaf nodes = 3
to equivalent implications and the graph built is Hence (d) is correct option.
called as implication graph) 50. (a) Given array A[1.....n], an element A[i] is chosen
3. Observe that is unsatisfiable iff there is a p P randomly from 1 to n.
such that there is both a path from p to p and This would require n selections & comparisons to
from p to p in G.. find x in array.
This condition can be tested by running the Hence (a) is correct option.
reachability algorithm several times. 51. (b) This is a recursive procedure. Which always calls
PROBLEM BASED MCQs itself by value n
So the recursion gas till n >2.
43. (a) t(n) is 0 (1) this is called constant growth. t(n) Let n = 256
does not grow at all as a function of n as it is a Rec 1 n = 256
constant. For example, Array access has this 2 n = 16
characteristics. A[i] takes the same time independent 3 n = 4 recursion = 4
of the array A. 4n=2
44. (a) Since f(n) is polynomially greater than g(n) log2 256 = 8
So f(n) = 0(g(n)) Hence (b) is correct option.
But g(n) 0(f(n)) 52. (c) n is represented in binary let W suppose using K bit.
Hence (a) is correct option. To calculate its cube root the time taken is 0(log n)k
45. (b) Total no. of nodes = n but it can't be
For an edge of n nodes we select any 2 which make 0(log n)m
a graph. Since K < m, K > 0, m > 0.
So nc2 n(n – 1)/2 edges m is the cube root, since we are doing in binary so
n = 4 ; ( 4 3)/2 = 6 we take K.
46. (d) Worst case of searching occurs when the element to Hence (c) is correct option.
be searched is at the end of the list so no. of 53. (b) Since, G = (V, E) is an undirected graph, then C 1 will
comparisons required to search complete list would be connected as for the computed path costs. This
be n. Hence (d) is correct option. can be clearly explained from the example
47. (d) Here, we need to find the number of undirected Graph 1
graphs to be constructed
Now, S = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 ... n – 1
= n (n – 1)/2 constructed graphs
= 2S
n ( n –1)
2 2
48. (a) Since, it is given that the number of nodes in the left
sub tree is at least half of the girht_subtree.

Weight of edge be 1.
A to B will cost only 1 neglecting the weight of
other edges
Graph 2
E1
Number of nodes in the at most twice of the right A B
subtree.
E5 E2

D C
E3
 24
Here, A to B will not cost only 1 as they are not
connected. So, they needs to be connected. Index Hash value
54. (b) Starting from vertex a 4322 2
{(a, b), (a, c), (a, d), (a, c)} min = (a, c) = 1
{(a, b), (a, d), (a, e), (c, d)} min = (a, d) = 2 1334 4
{(a, b), (a, e), (c, d), (b, d), (d, h)} min = (b, d) = 3 1471 1
(c, d) not selected since it make cycle 9679 9
{(a, b), (a, e), (d, h), (b, g)} min = (b, g)=2
{(a, b), (a, e), (d, h), (g, h), (g, j), (g, i)} (g, h) =8 1989 9
{(a, e), (d, h), (g, j), (g, i), (h, i), (h, f), (e, h)} (h, i) = 4 6171 1
{(a, e), (d, h), (g, j), (g, i), (h, f), (e, h)(e, i), (f, i), (j, i)} min 6173 3
= (e, i) = 2
4199 9
{(a, e), (d, h), (g, j), (g, i), (h, f), (e, h), (f, i), (j, i), (e, f)} = 4
{(a, e), (d, h), (g, j), (g, i), (e, h), (f, i), (j, i), (e, f)} (j, i) = 5 By the table above, it is observed that statement 1
8 15 19 14 8 9 5 11 and statement 2 are correct.
Sum 1 + 2 + 3 + 2 + 8 + 4 + 2 + 4 + 5 61. (c) Sorting worst case occurs when arrays are reverse
= 31 sorted, we need to select every element once & for
Hence (b) is correct option. every element min no. of comparison might be log 2n.
55. (b) Sequence asbscsaedsceesfsbedegseefehsgehe So overall min. complexity 0(n log n)
No. of rooms 0 1 2 3 2 3 2 3 4 3 2 3 2 1 2 1 0 Hence (c) is correct option.
Maximum no. of rooms required at a time = 4 option 62. (a) Statement 1 is correct
(b). Consider k to be constant
Here the logic is very simple increase the no. of room f(n) = (n + k)m
if some activity start & decrease by 1 if activity f(n) = (1 + n)m
ends. f(n) = O(nm)
56. (d) Here A during initialization gives the adjacency Statement 2 is correct
matrix for directed graph G(V, E). And for very (j,k) f(n) = 2n+1
we calculate A[j,k], which stores maximum of the sum f(n) = 2n.2
of edges making a simple path. f(n) = O2n
So if there exists a simple path from j to k . A[j,k] Statement 3 is incorrect
contain no. of edges in that path. f(n) = 22n+1
a b c f(n) = 22n.2
a 0 1 1 f(n) = O22n
b 0 0 1 Therefore, we can see that the only statement 3 is false.
c 0 0 0 63. (d) DFS traversal takes the path to the end & then move
57. (c ) Here the fragment of code contains for loop which to other branch.
goes from 1 to n. a
Since due to given conditions m < n.
So complexity of code is (n) e b f
Hence (c) is correct option.
58. (d) The C function given above is resursive. h
g
The output of the program thus, obtained is

Hence option (d) is correct.

64. (a) In gcd is replaced by n/m in every iteration so
running time has to be less than O(n) or (n) even
less than ( n).
Such inputs which produces the output in the form as It has to be (log2 n) since recursion cause the
given in the figure have the complexity of the order of 2n. problem size reduced by n/2 every iteration.
Therefore, the complexity is O (2n). Hence (a) is correct option.
59. (a) 65. (d) Here T(n) = T( n) + n
60. (c) The solution can be achieved by finding the hash e.g. n = 16, n = 4, n = 2 so
values of the input. Recursion tree
 25
69. (d) Initial level order traversal with 10, 8, 5, 3, 2

We find that Now, let us insert the values

2–k log2n = 1
2k = log2n = 1
k = log2log2n
T(n) = (log2log2 n)
66. (d) Let us check each option

10

8 5

(a) (a – b), (d – f), (b – f), (d – c), (d – e) 3 2 1 7

(b) (a – b), (d – f), (d – c), (b – f), (d – e), (d – c) & (b – f)
has same weight so correct.
inserting 7 here
(c) (d – f), (a – b), (d – c), (d – f), (d – e) possible
(d) (d – f), (a – b), (b – f), (d – e) (d – c).
(b – f) has weight = 2
(d – e) has weight = 3
(d – c) has weight = 2
So (d – e) can't be taken before (d – c)
So (d) is incorrect.
Hence (d) is correct option.
67. (d) The condition given in the FOR loop is
z[i] = {x[i] ~ y[i]} (~ x[i] y[i])
Therefore, the level order traversal comes out to be
Now, we clearly can see that the condition reflect the 10, 8, 7, 3, 2, 1, 5
XOR operation and in the XOR operation set 70. (b) The number of keys as per given are 4
obtained is Applying the direct formula
(X Y ) (X Y) Bn = 1/(n + 1) × (2n! / n!n!)
Since, the formula is X Y = X – Y where, Bn is number of binary trees and n is the
Result obtained is (X – Y) (Y – X) number of keys.
68. (a) T(1) = 1 Bn = 1/(4 + 1) × (8! / 4!4!)
Bn = 1/5 × (8 × 7 × 6 × 5 × 4!) / 4!4!
T(n) = 2T( n ) 1] Bn = 8 × 7 × 6/(4 × 3 × 2)
Also we know that log2 2 = 1 Bn = 56/4
log2 2 = 1 Bn = 14
The total number of binary trees with n = 4 is 14.
n2–k problem size at level k of recursion
71. (c) No. of internal nodes = n
n2–k constant as the recursion is stopped once the Each node has k children
value is achieved. So total nk
Suppose n2–k Leaf nodes = nk – n
Solving, = n(k – 1)
2–k log2 n = 1 So considering not node also.
k = (log log n) No. of leaf nodes = n(k – 1) + 1
T(n) = (log log n) Hence (c) is correct option.
 26
72. (b) Since, T(n) 2T(n/2) + 2 for n > 2
n T(n) = 3n/2 – 2
T(n) 2T n
2 = 1.5n – 2
T(0) = T(1) = 1 78. (a) In a Max heap we insert 1 element this takes 0 (1) time
T(n) can be further computed as
since it is an array. Now to find correct position we
log n
T (n) n (2 / 2)i perform Binary search, & we know BS an array takes
i 0 0(log2n) time
log n So (a) is correct option.
T (n) n (1)i 79. (c) Each internal node has n children & so total nodes I # n
i 0
T(n) = (n log n) No. of leaf in them
73. (b) Right child & left child of element X[i] are shared in I* n – 1
array at X[2i+1] &X[2i] respectively & index is at X[1] I(n – 1)
& X[2] & X[3] are its child. So till index 3 we stored 3 But root can’t produce leaf
elements & so on. So we require the array of size n to I(n – 1) + 1 = L
store n elements. n = L – 1/ l + 1
74. (b) The minimum spanning tree is formed when n=(41 – 1 )/10 +1 =5
Vi {1, 2, ....} 80. (b) As given,
Lets construct a tree on the basis of Size of the hash table is 7.
(vi, vj) is 2|i – j| Starting index = 0
Considering the maximum value (n) to be 4. Now, hash function h(x) = (3x + 4) mod 7
v1 h(x) = (3x + 4) mod 7
h(1) = (3.1 + 4) mod 7
2 |2 – 1| 2 |3 – 2| h(1) = 7 mod 7 = 0 at the 0th location
Similarly, h(3) = 6th location
v2 v3 and h(8) = 0th location
Since, 0th position is already occupied then the location
2 |4 – 3| will be next location to it. So, h(8) will be 1st location.
Also h(10) = 6th location and the 6th position is
v4 occupied, so h(10) is hashed to 2nd position.
As Vi is connected to Vi + 1, Diagrammatically.
The minimum weight of each edge = 2
Therefore, the weight of tree with n – 1 edges 0 1
= 2(n – 1) = 2n – 2. 1 8
75. (a) The minimum number of multiplications can be found
out by simplifying the given expression 2 10
p(x) = a0 + x(a1 + a2x + a3x2) 3 –
p(x) = a0 + x(a1 + (a3x + a2)x) 4 –
Here we can see three multiplications
1. a3 *x 5 –
2. x(a2 + a3x) 6 3
3. x * (a1 + x(a2 + a3x))
76. (b) The loop runs from 2 to n . So maximum iterations can
be n. 81. (b) It is given that n = 3
When n = 2 loop has only 1 iteration so. 1 &n are lower 1 2n
Cn
& upper bounds respectively. n 1
(1) <= T(n) <= 0(n) 1 6
C3
77. (b) One possible way to do this is we select first element 3 1
as max & also min. Then we compare it with all others. 1.6!
5
At most this would take 2n comparisons during linear 4 3!3!
search. But if we use divide & conquer as for merge Therefore, there are 5 trees that can be formed with
three unlabelled node.
sort we have.
 27

1
2

Order a be f c h g d
a b= 1 ac= 3 ab= 6
3 ae = 2 af= 0 a g = 3
4
ah = 2

82. (c) This is a formula to calculate the total number of nodes. Since there is no - ve cycle so Dijkstra gives correct
It is 2h + 1 – 1.
result for all vertices.
Let consider some examples to prove this.
1. Simplest could be taking the binary tree of h (height) 86. (b) Pivot element is found in Quick sort in every iteration
= 0. all the elements to its left are smaller than & all in the
Now, the binary tree of height h will have only 1 node. right are greater than it. So if 1/5th of sorted sequence
is the pivot. So sequence is divided into 1/5th & 4/5th
Using formula 2 ^ (0 + 1) – 1 = 1. Hence, the formula is of the sequence. So recursion will be
correct. T(n) = T(n/5) + T(4n/5) + n
2. Binary tree of h (height) = 2
87. (a) In B tree the data is stored at leaves only a particular
1 node can have maximum. 3 keys, so when 4th insertion
comes first split is required, during 7th second split &
3 so on, so for 10 insertions max. 3 splits are required.
2
We can prove it mathematically.
7 No. of split < = 1 + logm/2[n/2]
4 5 6 Here m order = 4 n = 10 b = 3
Using formula 2 ^ (2 + 1) – 1 = 7. Hence, the formula is K <= 1+ log2 [10/3] = 1 + log 2[4]
correct. K<= B
83. (b) Heaps are implemented as simple arrays, to insert n
88. (b) Since all the elements are sorted so we can apply
more elements each element take (1) time. So total
binary search here efficiently. In BS the size of array
time would be (n).
required to compare reduces by n/2 in every iteration.
84. (b) To construct a BST from post order we also require
Here since the sequence is sorted so the same element
in-order traversal since given the elements are 1 2.......n
would come Consecutive.
So their sorted order would be in order. Using both 89. (d) Since
BST can be constructed in a linear scan. So it will take f(n) = 2n
only 4n time. g(n) = n!
h(n) = n logn
85. (d) We apply Dijkstra Algorithm. It can also be shown as
f(n) = O (2n)
 28
g(n) = O(n!) Complexity of this algorithm is same as 1 DFS run
h(n) = O (nlogn)
0(m + n) since
Now,
As per the asymptotic order of function n log n C2 n DFS is the basis of articulation point.
for all n n 0 92. (b) Pivot in guide sort is the index which is sorted in that
Let us assume C = 1 and n 0 = 2 run, all the elements in its left are smaller than it &
It comes out to be 2 log 2 22 elements greater than it are on its right side.
h(n) = O(f(n)) one result So the recursion becomes.
Now, T(n) = T(n/4) + T(3n/4) + n
g(n) = n! & f(n) = 2n
As per the asymptotic order of function Solution to this recursion is (nlogn)
93. (d) Kruskal’s algorithm, arranging edges in ascending
n! C2n for n n 0
Let us assume C = 1 and n = 4 order.
{2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 6}
24 24
16
g(n) = (f(n)) second result
Therefore, the two results are
h(n) = O(f(n)); g(n) = (f(n))
90. (c) Applying BFS algorithm on the following figure
M N O (a)

R Q P
Let start form Q
Q comes in queue first (b)
Changing the status of the Q’s child to 1
Queue obtained, Q | M | N | P
Changing the status of the M’s child to 1
Queue obtained, Q | M | N | P | R
Changing the status of the N’s child to 1
Queue obtained Q | M | N | P | R | O
The queue’s final status is as per the table below
Q M N O P R
2 1 1 1 1 (c)
2 2 1 1 1
2 2 2 1 1 1

M N O

(d)

R Q P

(a, c) can’t be taken after (b, c).

91. (c) The algorithm we use for finding the number of Hence (d) is correct option.
connected components in an undirected graph on n 94. (c) Enter the keys and check if the collision occurs. If the
vertices is to calculate articulation point detection collision occurs then at what point.
Key 12
algorithm.
12 mod 10 = 2
This articulation point divides the graph into 2 Key 18
connected components. 18 mod 10 = 8
Key 13
13 mod 10 = 3
Key 2
2 mod 10 = 2 Collision occurred
 29
(2 + 1) mod 10 = 3 Collision tree with n nodes is O (n).
(3 + 1) mod 10 = 4 99. (c) The time complexity of Bellman-Ford algorithm on a
Key 3 graph with n vertices and m edges is O (nm).
3 mod 10 = 3 For a complete graph, m = nC2 = O (n2)
(3 + 1) mod 10 = 4 Collision (Since there is an edge between all pair of vertices)
(4 + 1) mod 10 = 5 The complexity = O (n2 . n)
Key 23 = O (n3)
23 mod 10 = 3 Collision Solution is (c).
(3 + 1) mod 10 = 4 Collision 100. (a) To compute the worst case time complexity of a
(4 + 1) mod 10 = 5 Collision sequence of n queue operations on an initially
(5 + 1) mod 10 = 6 empty queue is (n).
Key 5 Complexity of a squence of 'n' queue operations =
5 mod 10 = 5 Collision Total complexity of Enqueue operations ( ) + Total
(5 + 1) mod 10 = 6 Collision complexity of Dequeue operations ( ).
(6 + 1) mod 10 = 7 Total complexity of Dequeue operations ( ) Total
Key 15 complexity of Enqueue operations
15 mod 10 = 5 Collision ...(i)
(5 + 1) mod 10 = 6 Collision Total complexity of queue operations ( ) n ...(ii)
(6 + 1) mod 10 = 7 Collision Total complexity of n operations = +
(7 + 1) mod 10 = 8 Collision + [From ...(i)]
(8 + 1) mod 10 = 9 n+n [From ... (ii)]
This gives us the following has table 2n
Worst Case Time Complexity of 'n' operations is
0 (a) (n).
1 101. (b) The return value of the function is (n2 log n)
2 12 n
3 13 The outer for loop goes + 1 iterations.
4 2 2
5 3 The inner for loop runs independent of the outer
6 23 loop.
7 5 n
8 18 And for each inner iteration, gets added to k.
2
9 15
n
95. (a) For n < = 3 T(n) = n × # outer loops × # inner loops per outer loop.
2
i.e (n) # Inner loops = (log n) [ 2 (log n) = (n)]
For n > 3
n n
T(n) = T(n/3) + Cn 1 . (log n) (n2 log n)
This can be solved by Master’s Theorem 2 2
a = 1 b = 2 logba = log31= 0 102. (b) Only REQ2 can be permitted.
f (n) = Cn 103. (d) P = NP = NPC
n logba < f(n) We know that clique problem is NP - Hard.
n0 < f(n) Given that it can be solved in polynomial time.
So, T (n) = (f(n)) case III We also know that a problem is NPC if it is both NP
= (Cn) and NP hard. So using given also it can also be solved
= (n) in polynomial time.
Whole complexity ¥ n A problem in NP can be transformed in NPC in
T(n) = (n)+ (n) polynomial time; so NP problem can also be solved in
= (n) polynomial time using given algo.
Hence (a) is correct option. Finally P is the set of all problems that can be solved
10n log10 n 10log10 in polynomial time, hence we get
96. (c) approx 106 P = NP = NPC.
2 0.001
0.0001 n 104. (a)
Therefore, the value of k comes out to be 6. Given no. of slots = 9
97. (b) The tightest upper bound that represents the Given hash fune (k) = k mod 9.
number of swaps required to sort n numbers using Collisions are resolved by chaining.
selection sort are O (n). Given 9 keys : 5, 28, 19, 15, 20, 33, 12, 17, 10.
98. (c) The tightest upper bound that represents the time High table after insertions will be as follows :–
complexity of inserting an object into a binary search
 30
Key (Place in Hash descending order, irrespective of position of pivot
Table) element in array.
0 5 mod 9 = 5 107. (a) Insertion done is such a way that first three slots
are unfilled
1 28 19 10 28 mod 9 = 1 First insertion
2 20 19 mod 9 = 1 97 C1 97
P(A) = 100 C 100
3 12 15 mod 9 = 6 1
Second insertion
4 20 mod 9 = 2
97 C1 97
5 5 33 mod 9 = 6 P(B) = 100 C 100
1
6 15 33 12 mod 9 = 3 Third insertion
7 97 C1 97
17 mod 9 = 8 P(C) = 100 C 100
1
8 17 10 mod 9 = 1 Total probability = P(A) × P(B) × P(C)
(Hash table)
Maximum chain length = 3 (At position 1) 97 97 97
=
Minimum chain length = 0 (At positions 0, 4, 7) 100 100 100
0 3 1 1 0 1 2 0 1 9
= (97 × 97 × 97)/ 1003
Avg chain length = = =1
9 9 COMMON DATA MCQs
105. (c) An ordered n type is graphic if it is a degree sequence
108. (b) Procedure f1 has the nature
of some simple undirected graph. options with
T(0) = 0, T(1) = 1=20
corresponding graphs are shown below:–
T(n) = 2T(n – 1)+3T(n – 2)
(a) is Graphic seq. (1, 1, 1, 1, 1, 1)
Solution to this recursion is 2n
A B So (2n)
Procedure f2 has a single for loop from 2 to n so the
C D complexity will be (n).
Hence (b) is correct option.
109. (c) For f(1), we are given that
E F
(2 * f1 (n –1) + 3 * f1 (n – 2))
(b) is Graphic seq. (2, 2, 2, 2, 2, 2) For f(2), we are given that
A B C X[0] = Y[0] = Z[0] = 0;
X[1] = 1; Y[1] = 2; Z[1] = 3;
And for loop we are given that:
X[i] = Y[i – 1] + Z[i – 2];
Y[i] = 2 * X[i];
Z[i] = 3 * X[i];
F E D Calculating f(1),
(d) is Graphic seq. (3, 2, 1, 1, 1, 0) f(n) = (2* f1 (n – 1) + 3* f1(n – 2))
C f(2) = (2* f1 (2 – 1) + 3* f1 (2 – 2))
f(2) = (2* 1 + 3* 0) = 2
A D F Similarly,
f(3) = 7
B E f(4) = 20
(c) is not graphic seq. (3, 3, 3, 1, 0, 0) f(5) = 61
f(6) = 182
Clearly we can safely remove isolated vertices (i.e. vertices f(7) = 547
with zero degree) to prepare the graph with this degree f(8) = 1640
sequence. Remaining sequence is (3, 3, 3, 1). Let us name Therefore, f1(8) returns 1640.
these as A, B, C, D Now vertex with degree 1 (is D) f2(8) will also return the same value as f2(n) is the
Must be connect only one A, B or C. If we remove this also non-recursive function of f1(n).
then 3 vertices remains A, B and C. One of them will have 110. (a) Let {0,1,2,3,4} be {a,b,c,d,e}
degree = 2 and other's degree = 3. Now remove vertex with
degree 2, finally two vertices remains that must have degree
= 2 which is not possible in a simple undirected graph.
Hence the seq. (3, 3, 3, 1, 0, 0) is not graphic.
106. (a) The highest upper bound for the worst case
performance is O (n 2). This occurs when elements
of the input array are already in ascending or
 31

Drawing spanning true using Prim’s Algorithms start As i = 4

with a Now, k = (4 + 9)/2 = 6
Therefore, y[6] < x is true.
(A) &(a,b),(a,c),(a,d),(a,e) (a,b) = 1
i = 6 and j = 9
(B) &(a,c), (a,d), (a,e), (b,c), (b,d), (b,e) (a,d) = 1 III iteration
(D) &(a,c), (a,e), (b,c), (b,d), (b,e), (c,d) (d,e) = 2 As i = 6
(E) &(a,c), (a,e), (b,c), (b,d), (b,e), (c,d), (c,e) (c,e) = 3 Now, k = (6 + 9) / 2 = 7
Therefore, y[7] < x is true
i = 7 and j = 9
IV iteration
As i = 7
Now, k = (7 + 9)/2 = 8
Therefore, y[8] < x is true
i = 8 and j = 9
V iteration
As i = 8
Now, k = (8 + 9) / 2 = 8
Therefore, y[8] < x is true
i = 8 and j = 9
As we have proved that 4[8]! = x & i < j, the program
Weight = 1 + 1 + 2 + 3 = 7 will remain forever in loop.
111. (b) Min possible path from B to C so we draw all paths 115. (a) The correction in the program is needed as in the
from B to C above solution we can see that the program cannot
B C = 12 work properly.
Now, when y[k] < x
B AC = 1 + 8 = 9 Increase 1 to k + 1
B EC = 9 + 3 = 12 Otherwise, decrease j to k –1
B EC = 4 + 2 + 3 = 9 This will ensure that in the while condition, element
B A EC = 1 + 4 + 3 = 8 at k position will be checked for equality.
This is min path. 116. (a) We know that characters with high probability need
less number of bits and vice-versa.
Hence (b) is correct option. The number of bits required are 1, 2, 3, 4, 5, 5
112. (b) Dynamic programming can be successfully used, i.e a, b, c, d, e, f, are represented by 0, 10, 110, 1110,
n rows for n elements &w + 1 columns. 11110, 11111
Each row is filled on the basis of its previous rows Diagrammatically,
& the (j – ai) – th column.
If any of them is 0 then X[i, j] should be zero.
This require X[i, j] = X[i – 1, j] # [i – 1, j – ai]
Hence (b) is correct option.
113. (c) The algorithm of dynamic programming has n rows
& w columns.These would be filled dynamically
depending upon previous rows &columns. So X[n,w]
will be filled in the last & this would give the result.
If X[n,w] = 1 i.e. TRUE, then we know that there is
subset present
whose sum = integer w.
Otherwise subset not present.
Hence (c) is correct option.
114. (c) We are given that
i = 0; j = 9;
k = (i + j)/2
I iteration
Let consider x = 4
Now, k = (0 + 9)/2 = 4 117. (d) The formula used here is
Therefore, y[4] < x is true Average length = Bits required Probability
i = 4 and j = 9
II iteration = 1/2 × 1 + 2 × 1/4 + 3 × 1/8 + 4 1/16 + 5 1/32
 32
+ 5 1/32 L[4, 5] require
= 1.9375 L[3, 4]L[3, 5] here (3, 4), (3, 5) & (4, 4)
118. (c) We need to store largest variables double sum. The
L[4, 4]L[4, 5] need to be calculated before [4, 5]
function foo() has recursive calls n times.
For every recursion we need 1 sum variable, size of So L[p, q] required to be calculated before L[r, s] if
largest double would be 1 : 2 : 3 :........n = n! p < r or q < s.
So complexity 0(n!)
This factorial is the no. of sub recursions in every NUMERICAL ANSWER QUESTIONS
recursion.
Hence (c) is correct option. 4
119. (b) Here we store values in foo(i ) only when they are 126. (a)
completed then in every recursion we require space
to store 1 double.
1 2 3 4 5 6
So overall n calls we require 0(n)
Hence (b) is correct option. (b)
120. (d) As per given, the total tasks are 9.
Let consider R initially empty. Now, R is to be fed
with the tasks. 4 7
The tasks will be allotted to tasks as per the given
profit and associated deadlines.
T4 and T6 will be left out as the maximum profit 1 2 3 4 5 6 7 8 9 10
is achieved without entering them.
121. (a) This is calculated by summing all the profits given
in the table. This is 5
15 + 20 + 30 + 18 + 18 + 10 + 23 + 16 + 25 = 147
Therefore, the maximum profit is 147.
122. (b) Since, Permutations are equally likely, 1 2 3 4 5 6 7 8 9
Expected number of inversions in a randomly chosen
permutation = 1/2(nC2)
= (1/2) n! (2!.(n – 2)!) m m
(c) (i) or
= 1/2 . n(n – 1) (n – 2) !/ (2. (n – 2)!) 2 2
= n(n – 1)/4 (ii) m
123. (a) Here at most n inversions are allowed, it means ai>aj 127. 1 to 1
only for n times. Value of a + 10b = 1.
52134 {(5,2), (2, 1), (5, 1), (5, 4), (5, 3)} We can find the subtree with 4 nodes in O(n) time, we can
Best case of insertion sort when all are sorted takes use following Algorithm:
0(n) time. (1) Transverse the tree in bottom up manner and find
Worst case when reverse sorted take 0(n 2) size of subtree rooted with current node.
So here the solution in between 0(n) & O(n2) (2) If size becomes 4, then print the current node.
Only n inversions means only n comparison required, int print 4 subtree (struct Node *root)
each comparison take log n time. {
So time complexity is 0(n log n). if (root = = NULL)
124. (c) LCS problem is solved using dynamic programming in return 0;
which every row is dependent upon previous rows & int l = print 4 subtree (root left);
columns. If two literals at ith row & jth column doesn’t int r = print 4 subtree (root right);
if ((l + r + 1) = = 4)
match then.
printf (“%d”, root data);
Eve fill l[i, j] with max [L[i–1,j],[I ,j –1]] i.e max of return (l + r + 1)
previous cell in row & column. }
So expr 1 =L[i–1, j–1]+1 128. 506 edges
expr 2 =max([l[i–1,j],L[i,j –1]]) The vertices of Graphs are ordered pair (i, j) where two
vertices (a, b) and (c, d) are connected by an edge only
125. (d) During solution through dynamic programming option
if |a – c| < 1 and |b – d| < 1. Also given that 1 < i < 12,
(b) & (c) are incorrect since the solution is done in row i < j < 12.
major order. But not in column major order. So, for example (1, 2) is connected to (1, 1), (2, 1), (2, 2),
(a) is true but not necessary. (2, 3) and (1, 3)
(d) is correct eg. Similarly (5, 5) is connected to (4, 4), (4, 5), (4, 6), (5, 4),
 33

(5, 6), (6, 4), (6, 5) and (6, 6) and (1, 12) is connected only
to (1, 11), (2, 11) and (2, 12). 129. 6
So, different vertices are connected to different number of
vertices. However we can visualize this easily using 6
following diagram:– +
3 3
–
+
1 2 3 4 5 6 7 8 9 10 11 12 2 –1 2
1
1 + – – +
2
1 1 0 1 1 0 1 1
3
130. 6
4
5 a 2
6 2 1 2 1
7 b c
8 2 2
9 A 1 1 2 1
10 B d e
11 2
2
12 Edges picked to make MST is given the double line.
In the right side of MST, we could either pick ‘d’ or ‘e’
In the left side we could either pick ‘a’, ‘b’ or ‘c’ in MST.
There are two options for one edge to be picked and three
Each cell of the table represents corresponding vertex option for other edge to be picked.
of the graph. For example the cell ‘A’ represents vertex Total possible MSTs = 2 × 3 = 6
(9, 0) of the graph, similarly ‘B’ represents vertex (10, 131. 3
2) of the graph. a * b * (ba) * a *
Now, we easily see that there are three kind of vertices Length 0 is present (as it accepts )
in the graph (or table): Length 1 is present (a, b)
(i) Corner vertices which are connected to ‘3’ neighbours. Length 2 is present (aa, ab, ba, bb)
Length 3 is not present (bab not present)
No. of such vertices = 4
it is 3
Total no. of edges for such vertices = 4 × 3 = 12
132. 110
(ii) Vertices in first/ last row of first/last column except It takes (log n) time to determine numbers n1 and n2 in
corner vertices, which are connected to ‘5’ neighbours balanced binary search tree T such that
each. 1. n1 is the smallest number greater than or equal to
No. of such vertices = 40 L and there is no predecessor n 1 of n1 such that n 1
Total no. of edges for such vertices = 40 × 5 = 200 is equal to n1.
(iii) Internal cells (vertices) that are connected to ‘8’ 2. n2 is the largest number less than or equal to H and
neighbours each. there is no successor of n 2 of n2 such that is equal
No. of such vertices = 100 to n2.
Total no. of edges for these vertices = 100 × 8 = 800 Since thee are m elements between n 1 and n 2, it takes ‘m’
Edge total of all above cases = 12 + 200 + 800 = 1012 time to add elements between n1 and n2.
So time complexity is O (log n + m)
However in above calculation each edge is counted
So the given expression becomes O (n 0log n + m log0 n)
twice, so, finally total no. of edges in the graph =
And a + 10b + 100c + 1000d = 0 + 10 × 1 + 100 × 1 + 1000 × 1
1012 = 10 + 100 = 110
= 506. Because a = 0, b = 1, c = 1 and d = 0
2