Algorithms
Question 1 
A message is made up entirely of characters from the set X = {P, Q, R, S, T}. The table of probabilities for each of the characters is shown below:
If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is __________.
225  
226  
227  
228 
General procedure to solve Huffman coding problem
Step1: Arrange into either descending/ ascending order according to that profits.
Step2: Apply optimal merge pattern procedure.
Step3: Make left subtree value either 0 or 1, for right subtree, viceversa.
= 2 × 0.34 + 2 × 0.22 + 2 × 0.19 + 3 × 0.17 + 3 × 0.08
= 2.25
∴ So, for 100 characters, 2.25 * 100 = 225
Question 2 
Consider a sequence of 14 elements: A = [5, 10, 6, 3, 1, 2, 13, 4, 9, 1, 4, 12, 3, 0]. The subsequence sum . Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)
19  
39  
29  
09 
Ex:
{A, B, C, D}
{A, AB, AC, AD, ABC, ABD, ACD, B, BC, BD, BCD, C, CD, D }
Step1: Array of elements A = [5, 10, 6, 3, 1, 2, 13, 4, 9, 1, 4, 12, 3, 0 ]
Step2: As per the given question, if they want to find maximum subsequence means
{6,3,13,4,4,12}
= 42
Step3: But according to given recurrence relation, the sequence should be continuous. {6,3,13,4,4,12}.
This is not continuous subsequence.
Step4: The continuous sequence is {6, 3, 1, 2, 13, 4, 9, 1, 4, 12}
Total is {29}.
Note: We can't get more than 29 maximum subsequence sum.
Question 3 
An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _____.
0.08  
0.01  
1  
8 
Step2: Pivot element = uniformly random.
Step3: Worst case position in the pivot element is either first (or) last.
Step4: So total 2 possibilities among 25 distinct elements
= 2/25
= 0.08
Question 4 
There are n unsorted arrays: A_{1}, A_{2}, ..., A_{n}. Assume that n is odd. Each of A_{1}, A_{2}, ..., A_{n} contains n distinct elements. There are no common elements between any two arrays. The worstcase time complexity of computing the median of the medians of A_{1}, A_{2}, ..., A_{n} is
O(n)  
O(n log n)  
Ω(n^{2} log n)  
O(n^{2}) 
But it is similar to quicksort but in quicksort, partitioning will take extra time.
→ Find the median will be (i+j)/2
1. If n is odd, the value is Ceil((i+j)/2)
2. If n is even, the value is floor((i+j)/2)
> Here, total number of arrays are
⇒ O(n)*O(n)
⇒ O(n^{2})
Note:
They are clearly saying that all are distinct elements.
There is no common elements between any two arrays.
Question 5 
Consider the following undirected graph G:
Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is _________.
4  
5  
6  
7 
If x = 5 then the total number of MWSTs are 4.
If r = 1
If r = 2
If r = 3
If r = 4
If r = 5
Question 6 
Consider the weights and values of items listed below. Note that there is only one unit of each item.
The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by V_{opt}. A greedy algorithm sorts the items by their valuetoweight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by V_{greedy}.
The value of V_{opt} − V_{greedy} is ______ .
16  
17  
18  
19 
V_{opt} is clearly = 60
For V_{greedy} use the table (Do not take the fraction as per the question),
Item 4 picked,
Profit = 24
Remaining weight = 11 – 2 = 9
Next item 3 picked (item 1 cannot be picked since its capacity is greater than available capacity),
Profit = 24 + 20 = 44
Remaining capacity = 9 – 4 = 5
Now no item can be picked with available capacity.
So V_{greedy} = 44
∴ V_{opt} – V_{greedy} = 60 – 44 = 16
Question 7 
Consider the following functions from positives integers to real numbers
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
Step1: Take n=2048 or 2^{11} (Always take n is very big number)
Step2: Divide functions into 2 ways
1. Polynomial functions
2. Exponential functions
Step3: The above functions are belongs to polynomial. So, simply substitute the value of n,
First compare with constant values.
→ 100 / 2048 = 0.048828125
→ 10 > 100/ 2048
→ log_{2} 2048 =11
→ √n = 45.25483399593904156165403917471
→ n = 2048
So, Option B is correct
Question 8 
Consider the following table
Match the algorithm to design paradigms they are based on:
(P)↔(ii), Q↔(iii), (R)↔(i)  
(P)↔(iii), Q↔(i), (R)↔(ii)  
(P)↔(ii), Q↔(i), (R)↔(iii)  
(P)↔(i), Q↔(ii), (R)↔(iii) 
(Q) QuickSort is a Divide and Conquer algorithm.
(R) Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem using Dynamic Programming.
Some important points regarding Greedy Vs Dynamic Programming
Greedy: →
It always gives polynomial time complexity
→ It is not an optimal
→ It always selects only either minimum or maximum among all possibilities
→ Ex: Dijkstra’s algorithm for SSSP, Optimal Merge Pattern, Huffman coding, Fractional knapsack problem, etc..,
Dynamic Programming:
→ It gives either polynomial or exponential time complexity.
→ It gives always an optimal result.
→ It checks all possibilities of a problem.
→ Ex: Longest Common sequence, Matrix chain Multiplication, Travelling sales Problem, etc.
Question 9 
(I) Minimum Spanning Tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
(I) only  
(II) only  
both (I) and (II)  
neither (I) nor (II) 
Let us take an example
Step 1:
Using kruskal’s algorithm, arrange each weights in ascending order.
17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Step 2:
Step 3:
17+18+20+21+22+23+26 = 147
Step 4:
Here, all the elements are distinct. So the possible MCST is 1.
StatementII: May or may not happen, please take an example graph and try to solve it. This is not correct always.
So, we have to pick most appropriate answer.
Question 10 
Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is _________.
5  
6  
7  
8 
→ As in this array sequence of 0’s is followed by sequence of 1’s, the array is sorted. We can apply binary search directly without sorting it.
So number of probes = ceil(log_{2} 31) = 4.954196310386876
⇒ here we are using ceiling so it becomes 5
Question 11 
Match the algorithms with their time complexities:
Algorithm Time complexity (P) Towers of Hanoi with n disks (i) Θ(n^{2}) (Q) Binary search given n stored numbers (ii) Θ(n log n) (R) Heap sort given n numbers at the worst case (iii) Θ(2^{n}) (S) Addition of two n×n matrices (iv) Θ(log n)
P→(iii), Q→(iv), R→(i), S→(ii)  
P→(iv), Q→(iii), R→(i), S→(ii)  
P→(iii), Q→(iv), R→(ii), S→(i)  
P→(iv), Q→(iii), R→(ii), S→(i) 
→ Tower of Hanoi with n disks takes θ(2^{n}) time
It is a mathematical game or puzzle.
It consists of three rods and a number of disks of different sizes, which can slide onto any rod.
The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
3. No disk may be placed on top of a smaller disk.
With 3 disks, the puzzle can be solved in 7 moves.
The minimal number of moves required to solve a Tower of Hanoi puzzle is 2^{n}1, where n is the number of disks.
→ Binary Search given n sorted numbers takes Ɵ(log_{2} n)
→ Heap sort given n numbers of the worst case takes Ɵ(n log n)
→ Addition of two n×n matrices takes Ɵ(n^{2})
Question 12 
Consider the recurrence function
Then T(n) in terms of Θ notation is
Θ(loglogn)  
Θ(logn)  
Θ(√n)  
Θ(n) 
(or)
T(n) = 2T(n^{(1⁄2)}) + 1
Here, Assume n = 2^{k}
T(2^{k}) = 2T(2^{k})^{(1⁄2)} + 1
T(2^{k}) = 2T(2^{(k/2)} ) + 1
Assume T(2^{k}) = S(k)
S(k) = 2S(k/2) + 1
Apply Master’s theorem Case1
a=2, b=2
S(k) = k^{(log22 )}
S(k) = θ(k')
but S(k) = T(2^{k})
T(2^{k}) = θ(k')
but n = 2^{k}
k = logn
T(n) = θ(logn)
Question 13 
Consider the following C function.
int fun (int n) { int i, j; for (i = 1; i <= n; i++) { for (j = 1; j < n; j += i) { printf("%d %d",i,j); } } }
Time complexity of fun in terms of Θ notation is
Θ(n√n)  
Θ(n^{2})  
Θ(n logn)  
Θ(n^{2} logn) 
int fun(int n)
{
int i, j;
for (i = 1; i <= n ; i++) /* It is independent loop. So, it takes O(n) time */
{
for (j = 1; j < n; j += i) /* It is dependent loop, It always incrementing with the help of i. It will take approximately O(log n) times*/
{
printf("%d %d", i, j); /* It takes O(1) time */
}
}
}
So, the overall complexity of the program is θ(n logn) times.
Question 14 
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
Θ(nlogn), Θ(nlogn), and Θ(n^{2})  
Θ(n^{2} ), Θ(n^{2} ), and Θ(nlogn)  
Θ(n^{2}), Θ(nlogn), and Θ(nlogn)  
Θ(n^{2}), Θ(nlogn), and Θ(n^{2}) 
Question 15 
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is __________.
7  
8  
9  
10 
Now consider vertex A to make Minimum spanning tree with Maximum weights.
As weights are 1, 2, 3, 4, 5, 6. AB, AD, AC takes maximum weights 4, 5, 6 respectively.
Next consider vertex B, BA = 4, and minimum spanning tree with maximum weight next is BD & BC takes 2, 3 respectively.
And the last edge CD takes 1.
So, 1+2+4 in our graph will be the Minimum spanning tree with maximum weights.
Question 16 
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
I only  
II only  
both I and II  
neither I nor II 
The MSTs of G may or may not include the lightest edge.
Take rectangular graph labelled with P,Q,R,S.
Connect with PQ = 5, QR = 6, RS = 8, SP = 9, PR = 7.
When we are forming a cycle RSPR. PR is the lightest edge of the cycle.
The MST abcd with cost 11
PQ + QR + RS does not include it.
Statement2: True
Suppose there is a minimum spanning tree which contains e. If we add one more edge to the spanning tree we will create a cycle.
Suppose we add edge e to the spanning tree which generated cycle C.
We can reduce the cost of the minimum spanning tree if we choose an edge other than e from C for removal which implies that e must not be in minimum spanning tree and we get a contradiction.
Question 17 
I. Quicksort runs in Θ(n^{2}) time
II. Bubblesort runs in Θ(n^{2}) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time
I and II only  
I and III only  
II and IV only  
I and IV only 
→ The recurrence relation for Quicksort, if elements are already sorted,
T(n) = T(n1)+O(n) with the help of substitution method it will take O(n^{2}).
→ The recurrence relation for Merge sort, is elements are already sorted,
T(n) = 2T(n/2) + O(n) with the help of substitution method it will take O(nlogn).
We can also use master's theorem [a=2, b=2, k=1, p=0] for above recurrence.
Question 18 
The FloydWarshall algorithm for allpair shortest paths computation is based on
Greedy paradigm.  
DivideandConquer paradigm.  
Dynamic Programming paradigm.  
Neither Greedy nor DivideandConquer nor Dynamic Programming paradigm. 
It takes worst case time complexity is O(V^{3}) and worst case space complexity is O(V^{2}).
→ The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).
→ A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices.
Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.
Question 19 
Let A_{1}, A_{2}, A_{3} and A_{4} be four matrices of dimensions 10 × 5, 5 × 20, 20 × 10, and 10 × 5, respectively. The minimum number of scalar multiplications required to ﬁnd the product A_{1}A_{2}A_{3}A_{4} using the basic matrix multiplication method is _________.
1500  
1501  
1502  
1503 
The optimal parenthesized sequence is A_{1}((A_{2}A_{3})A_{4}) out of many possibilities, the possibilities are
1. ((A_{1}A_{2})A_{3})A_{4}
2. ((A_{1}(A_{2}A_{3}))A_{4})
3. (A_{1}A_{2})(A_{3}A_{4})
4. A_{1}((A_{2}A_{3})A_{4})
5. A_{1}(A_{2}(A_{3}A_{4}))
→ A_{1}((A_{2}A_{3})A_{4}) = (5 x 20 x 10) + (5 x 10 x 5) + (10 x 5 x 5) = 1000 + 250 + 250 = 1500
Question 20 
The given diagram shows the ﬂowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst case time complexity of this function is O(n^{α}), then the least possible value (accurate upto two decimal positions) of α is _________.
2.3219280  
2.3219281  
2.3219282  
2.3219283 
According to flow chart total 5 worst case possibilities of function calls.
The remaining function calls/return statements will execute only constant amount of time.
So, total function calls 5.
The Recurrence will be
A(n) = 5A(n/2) + O(1)
Apply Master’s theorem,
A=5, b=2, k=0, p=0
a > b^{k} case
A(n) = n^{(logba )} = n^{(log25)} = n^{2.3219280}
∴α = 2.3219280
Question 21 
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(≥ 2) numbers? In the recurrence equations given in the options below, c is a constant.
T(n) = 2T(n/2) + cn  
T(n) = T(n – 1) + T(1) + cn  
T(n) = 2T(n – 1) + cn  
T(n) = T(n/2) + cn

Hence recurrence relation T(n) = T(n  1) + T(1) + cn.
Question 22 
Match the following:
(P) Prim's algorithm for minimum spanning tree (i) Backtracking (Q) FloydWarshall algorithm for all pairs shortest paths (ii) Greedy method (R) Mergesort (iii) Dynamic programming (S) Hamiltonian circuit (iv) Divide and conquer
Piii, Qii, Riv, Si  
Pi, Qii, Riv, Siii  
Pii, Qiii, Riv, Si  
Pii, Qi, Riii, Siv 
Floydwarshall always changes it distance at each iteration which is nothing but dynamic programming.
Merge sort in merge sort first we always divide and merge to perform sorting hence divide and conquer.
Hamiltonian circuit used to reach the entire vertex once, if some vertex is repeating in its path it will backtrack.
Question 23 
An algorithm performs (log N)^{1/2} find operations, N insert operations, (log N)^{1/2} delete operations, and (log N)^{1/2} decreasekey operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decreasekey operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?
Unsorted array  
Minheap  
Sorted array  
Sorted doubly linked list 
Question 24 
The graph shown below 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ______________.
69  
70  
71  
72 
⇒ Total sum = 10 + 9 + 2 + 15 + 7 + 16 + 4 + 6 = 69
> First we compare AC and AB we find 9 at AC it means AB must greater than AC and for minimum possible greater value than 9 will be 10
> Second we compare BE and CD in which we select BE is 15 which CD possible weight 16.
> Third, we compare ED and FD in which we select FD 6 means ED must be greater than 6 so possible value greater than 6 is 7 .
Note: Add First+Second+Third=(AB=10)+(CD=16)+(ED=7)
Question 25 
Given below are some algorithms, and some algorithm design paradigms
A. Dijkstra’s Shortest Path 1. Divide and Conquer B. FloydWarshall algorithm to 2. Dynamic Programming compute all pairs shortest path C. Binary search on a sorted array 3. Greedy design D. Backtracking search on a graph 4. Depthfirst search 5. Breadthfirst search
Match the above algorithms on the left to the corresponding design paradigm they follow Codes:
1i, 2iii, 3i, 4v.  
1iii, 2iii, 3i, 4v.  
1iii, 2ii, 3i, 4iv.  
1iii, 2ii, 3i, 4v. 
(2) → All Pair shortest path algorithm is using Dynamic Programming technique. It takes worst case time complexity is O(V3) and worst case space complexity is O(V2).
→ The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).
→ A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.
(3) Binary search on a sorted array:
Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
(4) Backtracking search on a graph uses Depthfirst search
Question 26 
Suppose you are provided with the following function declaration in the C programming language.
int partition (int a[], int n);
The function treats the first element of a[] as a pivot, and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part. The following partially given function in the C programming language is used to find the kth smallest element in an array a[ ] of size n using the partition function. We assume k ≤ n
int kth_smallest (int a[], int n, int k) { int left_end = partition (a, n); if (left_end+1==k) { return a [left_end]; } if (left_end+1 > k) { return kth_smallest (____________________); } else { return kth_smallest (____________________); } }
The missing argument lists are respectively
(a, left_end, k) and (a + left_end + 1, n – left_end – 1, k – left_end – 1)
 
(a, left_end, k) and (a, n – left_end – 1, k – left_end – 1)  
(a + left_end + 1, n – left_end – 1, k – left_end – 1) and (a, left_end, k)  
(a, n – left_end – 1, k – left_end – 1) and (a, left_end, k) 
Question 27 
Consider a typical disk that rotates at 15000 rotations per minute (RPM) and has a transfer rate of 50×106 bytes/sec. If the average seek time of the disk is twice the average rotational delay and the controller’s transfer time is 10 times the disk transfer time, the average time (in milliseconds) to read or write a 512byte sector of the disk is _____________.
6  
6.1  
6.2  
6.3 
1 rotation → 60 /15000 sec = 4 ms
∴ Average rotational delay = 1/2 × 4 ms = 2 ms
Average seek time = 2 × Average rotational delay
= 2 × 2 ms = 4 ms
Time to transfer 512 byte,
50 × 10^{6}B  1s
512 B  512B/ 50×10^{6}B/s = 0.01 ms
∴ Controllers transfer time
= 10 × Disk transfer time
= 10 × 0.01 ms
= 0.01 ms
∴ Avg. time = (4 + 2 + 0.1 + 0.01)ms
= 6.11 ms
Question 28 
Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?
256  
512  
1024  
2048 
where c is some constant
It is given that for n = 64,
cn log n = 30
c × 64 log 64 = 30
c × 64 × 6 = 30
c = 5/64
Now, the value of n for
c n log n = 360
5/64 × n log n = 360
n log n = 360×64/5
= 72 × 64 = 2^{9} × 9
So for n = 2^{9}, it satisfies.
So, n = 2^{9} = 512
Question 29 
Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes __________.
995  
996  
997  
998 
Question 30 
There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins is _______.
12  
13  
14  
15 
No. of coins picked: 1 2 4 8 16
There are two types of weights of coin, i.e., 10gm and 11gm. And total weight of picked coins are 323gm.
Let there be x number of 10gm coins and y number of 11gm coins.
So, 10x + 11y = 323  (1)
And we also know that total number of coins picked is
1 + 2 + 4 + 8 + 16 = 31 which is equal to x + y, so,
= 31  (2)
Solving equation (1) and (2), we get
y = 13
Means total there are 13 coins of 11gm.
Now we can chose bag number 1, 3 and 4, we will get a total sum of 13 coins picked from them.
So product of labelled bag number = 1×3×4 = 12
Question 31 
Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?
Question 32 
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is __________.
148  
149  
150  
151 
(∵ T(n) = T(floor(n/2))+T(ceil(n/2))+2)
Question 33 
Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?
T(n) = 2T(n/2) + Logn
Θ(n)  
Θ(nlog n)  
Θ(n^{2})  
Θ(logn) 
Apply Master’s theorem,
a=2, b=2, k=0, p=1
According to Master’s theorem, we can apply CaseI
(I) If a>b^{k}, then T(n) = θ(n^{(logba )}) = θ(n^{(log22)}) = θ (n)
Question 34 
Consider two strings A = "qpqrr" and B = "pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x+10y = _________.
34  
35  
36  
37 
A = “qpqrr” B = “pqprqrp”
The longest common subsequence (not necessarily contiguous) between A and B is having 4 as the length, so x=4 and such common subsequences are as follows:
(1) qpqr
(2) pqrr
(3) qprr
So y = 3 (the number of longest common subsequences) hence x+10y = 4+10*3 = 34
Question 35 
Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ______.
358  
359  
360  
361 
In the above implementation, total number of comparisons is
(441) + (941) + (651) + (1591) = 358
Hint: The number of comparisons for merging two sorted sequences of length m and n is m+n1.
Question 36 
The number of distinct minimum spanning trees for the weighted graph below is _______.
6  
7  
8  
9 
Minimum Spanning Tree:
From the diagram, CFDA gives the minimum weight so will not disturb them, but in order to reach BE=1 we have 3 different ways ABE/ DBE/ DEB and we have HI=1, the shortest weight, we can reach HI=1 through GHI/ GIH.
So 3*2=6 ways of forming Minimum Spanning Tree with sum as 11.
Question 37 
Consider the following rooted tree with the vertex labeled P as t he root:
The order in which the nodes are visited during inorder traversal is
SQPTRWUV  
SQPTUWRV  
SQPTWUVR  
SQPTRUWV 
Inorder Traversal: Left, Root, Middle, Right.
So, during inorder traversal whenever we visit the node second time then print it.
So, output will be,
S Q P T R W U V
Question 38 
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.
19  
20  
21  
22 
Note: We should not consider backtrack edges, it reduces recursion depth in stack.
So the maximum possible recursive depth will be 19.
Question 39 
You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
O(n^{2})  
O(n log n)  
Θ(n logn)  
O(n^{3}) 
Question 40 
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(n^{a}log^{b}n + m^{c}log^{d}n), the value of a + 10b + 100c + 1000d is ____.
110  
111  
112  
113 
1. n_{1} is the smallest number greater than or equal to L and there is no predecessor n_{1}' of >n_{1} such that n_{1}' is equal to n_{1}.
2. n_{2}2' of n_{2} such that is equal to n_{2}.
Since there are m elements between n_{1} and n_{2}, it takes ‘m’ time to add all elements between n_{1} and n_{2}.
So time complexity is O(log n+m)
So the given expression becomes O(n^{0}log'n+m'log^{0}n)
And a+10b+100c+1000d = 0+10*1+100*1+1000*1 = 10+100 = 110
Because a=0, b=1, c=1 and d=0
Question 41 
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?
(97×97×97)/100^{3}  
(99×98×97)/100^{3}  
(97×96×95)/100^{3}  
(97×96×95)/(3!×100^{3}) 
They are picked with equal probability of Hash function since it is uniform hashing.
So to avoid the first 3 slots to be unfilled
= 97/100*97/100*97/100 =((97*97*97))⁄100^{3}
Question 42 
Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChildrightSibling representation. Each node of the tree is of type treeNode.
typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) { int value=0; if (tree != NULL) { if (tree>leftMostChild == NULL) value = 1; else value = DoSomething(tree>leftMostChild); value = value + DoSomething(tree>rightSibling); } return(value); }
When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the
number of internal nodes in the tree.  
height of the tree.  
number of nodes without a right sibling in the tree.  
number of leaf nodes in the tree. 
Here, that condition is if (tree → leftMostchild = = Null)
⇒ Which means if there is no left most child of the tree (or the subtree or the current node as called in recursion)
⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all).
⇒ Which means the node under consideration is a leaf node.
⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered.
⇒ The function returns the number of leaf nodes in the tree.
Question 43 
Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.
int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n1; do { k = (i+j)/2; if (x <= listA[k]) j = k1; if (listA[k] <= x) i = k+1; } while (i <= j); if (listA[k] == x) return(k); else return 1; }
Which one of the following statements about the function ProcessArray is CORRECT?
It will run into an infinite loop when x is not in listA.  
It is an implementation of binary search.  
It will always find the maximum element in listA.  
It will return −1 even when x is present in listA. 
k = (i+j)/2;
where k keeps track of current middle element & i, j keeps track of left & right children of current subarray.
So it is an implementation of Binary search.
Question 44 
Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
O(log n)  
O(n)  
O(n log n)  
O(n^{2}) 
Selection sort time complexity O(n^{2}) in terms of number of comparisons. Each of these scans requires one swap for n1 elements (the final element is already in place).
Question 45 
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?
O(1)  
O(log n)  
O(n)  
O(n log n) 
Question 46 
Consider the languages L_{1} = ϕ and L_{2 }= {a}. Which one of the following represents L_{1}L_{2}* ∪ L_{1}*?
{є}  
ϕ  
a*  
{є,a} 
Rϕ = ϕR = ϕ
So L_{1} L_{2} * = ϕ
and L_{1} * = {ϕ}* = {ϵ}
So L_{1}L_{2}* ∪ L_{1}* = {ϵ}
Question 47 
What is the time complexity of BellmanFord singlesource shortest path algorithm on a complete graph of n vertices?
Θ(n^{2})  
Θ(n^{2} log n)  
Θ(n^{3})  
Θ(n^{3} log n) 
Bellman–Ford runs in O(V * E) time, where V and E are the number of vertices and edges respectively.
Note: For complete graph: E = n(n1)/2 = O(n^{2})
Question 48 
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
1/8  
1  
7  
8 
The probability that there exists one edge between two vertices = 1/2
So, the total probability that all three edges of the above exists
= 1/2 × 1/2 × 1/2 (as they are independent events)
= 1/8
Total number of ways in which we can select ‘3’ such vertices among ‘8’ vertices = ^{8}C_{3} = 56
Total number of cycles of length ‘3’ out of 8 vertices = 56 × 1/8 = 7
Question 49 
Which of the following statements is/are TRUE for undirected graphs?
 P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.
P only  
Q only  
Both P and Q  
Neither P nor Q 
The sum of the degrees of all the vertices of a graph is an even number (exactly twice the number of edges).
In every graph, the number of vertices of odd degree must be even.
Question 50 
The line graph L(G) of a simple graph G is defined as follows: · There is exactly one vertex v(e) in L(G) for each edge e in G. · For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e'are incident with the same vertex in G. Which of the following statements is/are TRUE?
 (P) The line graph of a cycle is a cycle.
(Q) The line graph of a clique is a clique.
(R) The line graph of a planar graph is planar.
(S) The line graph of a tree is a tree.
P only  
P and R only  
R only  
P, Q and S only 
R) False. We can give counter example. Let G has 5 vertices and 9 edges which is planar graph. Assume degree of one vertex is 2 and of all others are 4. Now, L(G) has 9 vertices (because G has 9 edges) and 25 edges. But for a graph to be planar,
E ≤ 3v  6
For 9 vertices E ≤ 3 × 9  6
⇒ E ≤ 27  6
⇒ E ≤ 21. But L(G) has 25 edges and so is not planar.
As (R) is false, option (B) & (C) are eliminated.
Question 51 
The number of elements that can be sorted in Θ(log n) time using heap sort is
Θ(1)  
Θ(√logn)  
Θ (logn/loglogn)  
Θ(log n) 
So, Θ((logn/ log log n)log(logn/log log n))
= Θ(logn/log logn (log logn  log log logn))
= Θ((log n/log logn) × log log n)
= Θ(log n)
Hence, option (C) is correct answer.
Question 52 
What is the return value of f(p,p), if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.
int f(int &x, int c) { c = c  1; if (c==0) return 1; x = x + 1; return f(x,c) * x; }
3024  
6561  
55440  
161051 
f(5,5) → f(x,4)*x
f(x,3)*x*x
f(x,2)*x*x*x
⇒x*x*x*x = x^{4}
Now x = x+1, there are 4 different calls namely f(6,4),f(7,3),f(8,2),f(9,1)
Because of pass by reference, x in all earlier functions is replaced with 9.
⇒ 9*9*9*9 = 9^{4} = 6561
Question 53 
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
10, 20, 15, 23, 25, 35, 42, 39, 30  
15, 10, 25, 23, 20, 42, 35, 39, 30  
15, 20, 10, 23, 25, 42, 35, 39, 30  
15, 10, 23, 25, 20, 35, 42, 39, 30 
From the data,
The Postorder traversal sequence is:
→ 15, 10, 23, 25, 20, 35, 42, 39, 30.
Question 54 
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.
MultiDequeue(Q){ m = k while (Q is not empty and m > 0) { Dequeue(Q) m = m  1 } }
What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue?
Θ(n)  
Θ(n + k)  
Θ(nk)  
Θ(n^{2}) 
i. One option is to perform all Enqueue operations i.e. n Enqueue operations. Complexity will be Ѳ(n).
or
ii. We can perform a mix of Enqueue and Dequeue operations. It can be Enqueue for first n/2 times and then Dequeue for next n/2, or Enqueue and Dequeue alternately, or any permutation of Enqueues and Dequeues totaling ‘n’ times. Completity will be Ѳ(n).
or iii. We can perform Enqueues and MultiDequeues. A general pattern could be as follows: Enqueue Enqueue …(ktimes) MultiDequeue Enqueue Enqueue …(ktimes) MultiDequeue …Up to total n …. K items enqueued ….k items deleted….k items enqueued…..k items deleted  and so on.
The number of times this kEnqueues, MultiDequeue cycle is performed = n/k+1
So, Complexity will be k times Enqueue + 1 MultiDequeue) ×n/k+1
Which is (2k×n/k+1) = (n)
or
iv. We can just perform n MultiDequeues (or n Dequeues for the matter):
Each time the while condition is false (empty queue), condition is checked just once for each of the ‘n’ operations. So Ѳ(n).
Question 55 
Assuming P ≠ NP, which of the following is TRUE?
NPcomplete = NP  
NPcomplete ∩ P = ∅  
NPhard = NP  
P = NPcomplete 
The definition of NPcomplete is,
A decision problem p is NPcomplete if:
1. p is in NP, and
2. Every problem in NP is reducible to p in polynomial time.
It is given that assume P ≠ NP , hence NPcomplete ∩ P = ∅ .
This is due to the fact that, if NPcomplete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NPcomplete also, then it means that P1 (NPcomplete problem) can be solved in polynomial time also (as it is also in P class) and this implies that every NP problem can be solve in polynomial time, as we can convert every NP problem into NPcomplete problem in polynomial time.
Which means that we can convert every NP problem to P1 and solve in polynomial time and hence P = NP, which is contradiction to the given assumption that P ≠ NP.
Question 56 
Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?
A(n) = Ω (W(n))  
A(n) = Θ (W(n))  
A(n) = O (W(n))  
A(n) = o (W(n)) 
So, A(n) would be upper bounded by W(n) and it will not be strict upper bound as it can even be same (e.g. Bubble Sort and merge sort).
A(n) = O(W(n))
Note: Option A is wrong because A(n) is not equal to Ω(w(n)) .
Question 57 
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sublists each of which contains at least onefifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
T(n) ≤ 2T(n/5) + n
 
T(n) ≤ T(n/5) + T(4n/5) + n  
T(n) ≤ 2T(4n/5) + n  
T(n) ≤ 2T(n/2) + n

So, T(n/5) comparisons are needed for the first subset and T(4n/5) comparisons needed for second subset.
Now, suppose that one subset contains more than n/5 elements then another subset will contain less than 4n/5 elements. Due to which time complexity will be less than
T(n/5) + T(4n/5) + n
Because recursion tree will be more balanced.
Question 58 
The subsetsum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to
An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?
Q solves the subsetsum problem in polynomial time when the input is encoded in unary
 
Q solves the subsetsum problem in polynomial time when the input is encoded in binary
 
The subset sum problem belongs to the class NP  
The subset sum problem is NPhard 
Question 59 
Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to
only vertex a  
only vertices a, e, f, g, h  
only vertices a, b, c, d  
all the vertices 
A  B ⇒ 1
A  C ⇒ 1 + 2 = 3
A  E ⇒ 1  3 = 2
A  F ⇒ 1 3 + 2 = 0
A  G ⇒ 1  3 + 2 + 3 = 3
A  C ⇒ 1 + 2 = 3
A  H ⇒ 1 + 2  5 = 2
Question 60 
Let A be an n×n matrix such that the elements in each row and each column are arranged in ascending order. Draw a decision tree which finds 1^{st}, 2^{nd} and 3^{rd} smallest elements in minimum number of comparisons.
Theory Explanation. 
Question 61 
(a) Consider the following algorithm. Assume procedure A and procedure B take O(1) and O(1/n) unit of time respectively. Derive the time complexity of the algorithm in Onotation.
algorithm what (n) begin if n = 1 then call A else begin what (n1); call B(n) end end.
(b) Write a constant time algorithm to insert a node with data D just before the node with address p of a singly linked list.
Theory Explanation. 
Question 62 
(a) Solve the following recurrence relation:
x_{n} = 2x_{n1}  1, n>1 x_{1} = 2
(b) Consider the grammar
S → Aa  b A → Ac  Sd  ε
Construct an equivalent grammar with no left recursion and with minimum number of production rules.
Theory Explanation. 
Question 63 
A two dimensional array A[1...n][1...n] of integers is partially sorted if
∀i, j ∈ [1...n−1], A[i][j] < A[i][j+1] and A[i][j] < A[i+1][j]
Fill in the blanks:
(a) The smallest item in the array is at A[i][j] where i=............and j=..............
(b) The smallest item is deleted. Complete the following O(n) procedure to insert item x (which is guaranteed to be smaller than any item in the last row or column) still keeping A partially sorted.
procedure insert (x: integer); var i,j: integer; begin (1) i:=1; j:=1, A[i][j]:=x; (2) while (x > ...... or x > ......) do (3) if A[i+1][j] < A[i][j] ......... then begin (4) A[i][j]:=A[i+1][j]; i:=i+1; (5) end (6) else begin (7) ............ (8) end (9) A[i][j]:= ............. end
Theory Explanation. 
Question 64 
Insert the characters of the string K R P C S N Y T J M into a hash table of size 10.
Use the hash function
h(x) = (ord(x) – ord("a") + 1) mod10
and linear probing to resolve collisions.
(a) Which insertions cause collisions?
(b) Display the final hash table.
Theory Explanation. 
Question 65 
A complete, undirected, weighted graph G is given on the vertex {0, 1,...., n−1} for any fixed ‘n’. Draw the minimum spanning tree of G if
(a) the weight of the edge (u,v) is ∣u − v∣
(b) the weight of the edge (u,v) is u + v
Theory Explanation. 
Question 66 
Let G be the directed, weighted graph shown in below figure.
We are interested in the shortest paths from A.
(a) Output the sequence of vertices identified by the Dijkstra’s algorithm for single source shortest path when the algorithm is started at node A.
(b) Write down sequence of vertices in the shortest path from A to E.
(c) What is the cost of the shortest path from A to E?
Theory Explanation. 
Question 67 
Consider the following program that attempts to locate an element x in a sorted array a[] using binary search. Assume N>1. The program is erroneous. Under what conditions does the program fail?
var i,j,k: integer; x: integer; a:= array; [1...N] of integer; begin i:= 1; j:= N; repeat k:(i+j) div 2; if a[k] < x then i:= k else j:= k until (a[k] = x) or (i >= j); if (a[k] = x) then writeln ('x is in the array') else writeln ('x is not in the array') end;
Theory Explanation. 
Question 68 
Merge sort uses
Divide and conquer strategy  
Backtracking approach  
Heuristic search  
Greedy approach 
Question 69 
The postfix expression for the infix expression
A + B*(C + D)/F + D*E is:
AB + CD + *F/D + E*  
ABCD + *F/DE*++  
A *B + CD/F *DE++  
A + *BCD/F* DE++  
None of the above 
A B C D + * F / + D E * +
Question 70 
Which of the following statements is true?
 I. As the number of entries in a hash table increases, the number of collisions increases.
II. Recursive programs are efficient
III. The worst case complexity for Quicksort is O(n^{2})
I and II  
II and III  
I and IV  
I and III 
Recursive program requires stack for storing the function state. Any recursive program can be rewritten as an iterative one. Advantage of recursion is "less programming effort", while it always lags behind iterative one in terms of performance.
Question 71 
Consider the following sequence of numbers
92, 37, 52, 12, 11, 25
Use bubble sort to arrange the sequence in ascending order. Give the sequence at the end of each of the first five passes.
Theory Explanation. 
Question 72 
How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to the edge).
Theory Explanation. 
Question 73 
FORTRAN implementation do not permit recursion because
they use static allocation for variables  
they use dynamic allocation for variables  
stacks are not available on all machines  
it is not possible to implement recursion on all machines 
→ Recursion requires dynamic allocation of data.
Question 74 
The recurrence relation that arises in relation with the complexity of binary search is:
T(n) = T(n/2) + k, k a constant  
T(n) = 2T(n/2) + k, k a constant  
T(n) = T(n/2) + log n  
T(n) = T(n/2) + n 
∴ T(n) = 2T(n/2) + k, k a constant
Question 75 
Which of the following algorithm design techniques is used in the quicksort algorithm?
Dynamic programming  
Backtracking  
Divide and conquer  
Greedy method 
Question 76 
In which one of the following cases is it possible to obtain different results for callby reference and callbyname parameter passing methods?
Passing a constant value as a parameter  
Passing the address of an array as a parameter  
Passing an array element as a parameter  
Passing an array following statements is true 
{ ........
a[ ] = {1, 2, 3, 4}
i = 0
fun(a[i]);
print a[0];
}
fun(int x)
{
int i = 1;
x = 8;
}
O/p:
Callbyreference = 8
Callbyvalue = 1
Question 77 
Which one of the following statements is false?
Optimal binary search tree construction can be performed efficiently using dynamic programming.  
Breadthfirst search cannot be used to find connected components of a graph.  
Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.  
Depthfirst search can be used to find connected components of a graph. 
Question 78 
Consider the following two functions:
Which of the following is true?
g_{1}(n) is O(g_{2}(n))  
g_{1} (n) is O(^{3})  
g_{2} (n) is O(g_{1} (n))  
g_{2} (n) is O(n)  
Both A and B 
Growth rate of g_{1} is less than that of g_{2} i.e., g_{1}(n) = O(g_{2}(n)) = O(n).
Question 79 
An array A contains n integers in locations A[0],A[1], …………… A[n1]. It is required to shift the elements of the array cyclically to the left by K places, where 1≤K≤n1. An incomplete algorithm for doing this in linear time, without using another is given below. Complete the algorithm by filling in the blanks. Assume all variables are suitably declared.
min:=n; i=0; while _____do begin temp:=A[i]; j:=i; while _____do begin A[j]:=_____; j:=(j+K) mod n; if j
Theory Explanation. 
Question 80 
(a) Use the patterns given to prove that
(You are not permitted to employ induction)
(b) Use the result obtained in (a) to prove that
Theory Explanation. 
Question 81 
Consider the following recursive function:
function fib (1:integer);integer; begin if (n=0) or (n=1) then fib:=1 else fib:=fib(n1) + fib(n2) end;
The above function is run on a computer with a stack of 64 bytes. Assuming that only return address and parameter and passed on the stack, and that an integer value and an address takes 2 bytes each, estimate the maximum value of n for which the stack will not overflow. Give reasons for your answer.
Theory Explanation. 
Question 82 
An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge. An incomplete scheme for a greedy algorithm to find a maximum independent set in a tree is given below:
V: Set of all vertices in the tree; I:=φ; While V ≠ φdo begin select a vertex u; ∈ V such that V:= V – {u}; if u is such that then 1:= I ∪ {u} end; output(I);
(a) Complete the algorithm by specifying the property of vertex u in each case
(b) What is the time complexity of the algorithm.
Theory Explanation. 
Question 83 
For parameters a and b, both of which are ω(1), T(n) = T(n^{1/a})+1, and T(b)=1.
Then T(n) is
θ(log_{a} log_{b} n)  
θ(log_{b} log_{a} n)
 
θ(log_{2} log_{2} n)
 
θ(log_{ab} n)

T(n) = [T(n^{1/a2})+1] + 1
= [T(n^{1/a3})+1] + 2
= [T(n^{1/a3})] + 3
= [T(n^{1/ak})] + b
= log_{b} n = a^{k}
= log log_{b} n = k log a
= k= log_{a} log_{b} n
T(n)=1+log_{a} log_{b} n
T(n)=O(log_{a} log_{b} n)
Question 84 
Let G = (V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u,v) ∈ V×V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is
θ(E+V)  
θ(E logV)  
θ(EV)  
θ(V) 
• As T is a minimum spanning tree and we need to add a new edge to existing spanning tree.
• Later we need to check still T is a minimum spanning tree or not, So we need to check all vertices whether there is any cycle present after adding a new edge.
• All vertices need to traverse to confirm minimum spanning tree after adding new edge then time complexity is O(V).
Method2:
Time Complexity:
Total vertices: V, Total Edges : E
• O(logV) – to extract each vertex from the queue. So for V vertices – O(VlogV)
• O(logV) – each time a new pair object with a new key value of a vertex and will be done at most once for each edge. So for total E edge – O(ElogV)
• So overall complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)
Note: Method1 is the most appropriate answer for giving a question.
Question 85 
Consider a graph G = (V, E), where V = {v_{1}, v_{2}, …, v_{100}}, E = {(v_{i}, v_{j})  1 ≤ i < j ≤ 100}, and weight of the edge (v_{i}, v_{j}) is i  j. The weight of the minimum spanning tree of G is ______.
99 
• N =100
• Edge weight is ij for Edge (vi,vj) {1<=i<=100}
• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.
• So, 99 edges of weight is 99.
Question 86 
The root directory of a disk should be placed
at a fixed address in main memory  
at a fixed location on the disk  
anywhere on the disk  
at a fixed location on the system disk  
anywhere on the system disk 
Question 87 
Consider a simple connected graph G with n vertices and nedges (n>2). Then, which of the following statements are true?
G has no cycles.  
The graph obtained by removing any edge from G is not connected.  
G has at least one cycle.  
The graph obtained by removing any two edges from G is not connected.  
Both C and D. 
For example let us consider, n=3.
Question 88 
where O(n) stands for order n is:
O(n)  
O(n^{2})  
O(n^{3})  
O(3n^{2})  
O(1.5n^{2})  
B, C, D and E 
⇒ In this 'n' is constant. So, n is added to n times itself which is O(n^{2}).
Hence, (a) is wrong. And rest (B), (C), (D), (E) are correct.
Question 89 
Consider the recursive algorithm given below:
procedure bubblersort (n); var i,j: index; temp : item; begin for i:=1 to n1 do if A[i] > A [i+1] then begin temp : A[i]; A[i]:=A[i+1]; A[i+1]:=temp end; bubblesort (n1) end
Let a_{n} be the number of times the ‘if…then….’ Statement gets executed when the algorithm is run with value n. Set up the recurrence relation by defining a_{n} in terms of a_{n1}. Solve for a_{n}.
Theory Explanation. 
Question 90 
Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted is __________
O(m log n) 
Question 91 
Following algorithm(s) can be used to sort n integers in the range [1...n^{3}] in O(n) time
Heapsort  
Quicksort  
Mergesort  
Radixsort 
As Radix sort is not comparison based sort (it is counting sort), so can be done in linear time.
Question 92 
Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…..n] are to be sorted, give an input for which Quicksort takes maximum time.
n 
→ The array is already sorted in ascending order.
→ The array is already sorted in descending order.
Question 93 
Consider the function F(n) for which the pseudo code is given below:
Function F(n) begin F1 ← 1 if(n=1) then F ← 3 else For i = 1 to n do begin C ← 0 For j = 1 to F(n – 1) do begin C ← C + 1 end F1 = F1 * C end F = F1 end [n is a positive integer greater than zero]
(a) Derive a recurrence relation for F(n)
(b) Solve the recurrence relation for a closed form solutions of F(n).
Theory Explanation. 
Question 94 
The minimum number of comparisons required to sort 5 elements is _____
7 
= ⌈log(n!)⌉
= ⌈log(5!)⌉
= ⌈log(120)⌉
= 7
Question 95 
The weighted external path length of the binary tree in figure is _____
144 
Question 96 
If the binary tree in figure is traversed in inorder, then the order in which the nodes will be visited is ______
4, 1, 6, 7, 3, 2, 5, 8 
(Left, Root, Right)
So, the order will be
4, 1, 6, 7, 3, 2, 5, 8
Question 97 
Match the pairs in the following questions by writing the corresponding letters only.
(A) The number distinct binary trees with n nodes (P) n!/2 (B) The number of binary strings of length of 2n (Q) (3n/n) with an equal number of 0’s and 1’s (C) The number of even permutations of n objects (R) (2n/n) (D) The number of binary strings of length 6m which (S) 1/n+1(2n/n) are palindromes with 2n 0’s.
AS, BR, CP, DQ 
Question 98 
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with vertices and m edges has the time complexity of:
O(n^{2})  
O(mn)  
O(m+n)  
O(m log n)  
O(m^{2}  
B, D and E 
→ Where m is no. of edges and n is number of vertices then n = O(m^{2})
→ O(m logn) < O(mn)
Question 99 
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: The following sequence of operations is performed on a stack:
PUSH (10), PUSH (20), POP, PUSH (10), PUSH (20), POP, POP, POP, PUSH (20), POPThe sequence of values popped out is:
20, 10, 20, 10, 20  
20, 20, 10, 10, 20  
10, 20, 20, 10, 20  
20, 20, 10, 20, 10 
→ PUSH(10), PUSH(10), PUSH(20), POP = 20 (ii)
→ PUSH(10), PUSH(10), POP = 10 (iii)
→ PUSH(10), POP = 10 (iv)
→ PUSH(20)
→ PUSH(20), POP = 20 (v)
⇒ 20, 20, 10, 10, 20
Question 100 
Match the pairs in the following questions:
(a) Strassen's matrix multiplication algorithm (p) Greedy method (b) Kruskal's minimum spanning tree algorithm (q) Dynamic programming (c) Biconnected components algorithm (r) Divide and Conquer (d) Floyd's shortest path algorithm (s) Depth first search
(a)  (r), (b)  (p), (c)  (s), (d)  (q) 
Kruskal's minimum spanning tree algorithm  Greedy method
Biconnected components algorithm  Depth first search
Floyd's shortest path algorithm  Dynamic programming
Question 101 
The numbers 1, 2, .... n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be
p  
p + 1  
n  p  
n  p + 1 
RST contains elements = p
Root contains = 1 element
1^{st} contains = n  (p + 1) element
Root contains the value is n  p.
Question 102 
In a depthfirst traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is
k  
k + 1  
n  k  1  
n  k 
In this question, we are going to applying the depth first search traversal on each component of graph where G is connected (or) disconnected which gives minimum spanning tree
i.e., k = np
p = n  k
Question 103 
In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.
1. BellmanFord algorithm A: O ( m log n) 2. Kruskal’s algorithm B: O (n^{3}) 3. FloydWarshall algorithm C: O (nm) 4. Topological sorting D: O (n + m)
1→ C, 2 → A, 3 → B, 4 → D  
1→ B, 2 → D, 3 → C, 4 → A  
1→ C, 2 → D, 3 → A, 4 → B  
1→ B, 2 → A, 3 → C, 4 → D 
Krushkal's algorithm → O(m log n)
FloydWarshall algorithm → O(n^{3})
Topological sorting → O(n+m)
Question 104 
A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in what location would the key value 142 be inserted?
2  
3  
4  
6 
165%10 = 5 [occupy 5]
62%10 = 2 [occupy 2]
123%10 = 3 [3 already occupied, so occupies 4]
142%10 = 2 [2, 3, 4, 5 are occupied, so it occupies 6]
Question 105 
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is:
2^{h1}  
2^{h1} + 1  
2^{h}  1  
2^{h} 
Above tree satisfies the property given in the question. Hence, only option (B) satisfies it.
Question 106 
Let T(n) be a function defined by the recurrence T(n) = 2T(n/2) + √n for n ≥ 2 and T(1) = 1 Which of the following statements is TRUE?
T(n) = θ(log n)  
T(n) = θ(√n)  
T(n) = θ(n)  
T(n) = θ(n log n) 
Question 107 
Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?
There exists a cutset in G having all edges of maximum weight  
There exists a cycle in G having all edges of maximum weight  
Edge e cannot be contained in a cycle  
All edges in G have the same weight 
(B) False, because the cutset of heaviest edge may contain only one edge.
(C) False. The cutset may form cycle with other edge.
(D) False. Not always true.
Question 108 
A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in preorder and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is traversed in postorder, the sequence obtained would be
8, 7, 6, 5, 4, 3, 2, 1  
1, 2, 3, 4, 8, 7, 6, 5  
2, 1, 4, 3, 6, 7, 8, 5  
2, 1, 4, 3, 7, 8, 6, 5 
5, 3, 1, 2, 4, 6, 8, 7
Inorder is the sorted sequence, i.e.,
1, 2, 3, 4, 5, 6, 7, 8
And we know that with given inorder and preorder, we can draw a unique BST.
So, the BST will be,
Hence, postorder traversasl sequence is,
2, 1, 4, 3, 7, 8, 6, 5
Question 109 
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is
4  
7  
23  
99 
j = i +1
(or)
j = 3i
Second option will help us reach from 1 to 100 rapidly. The trick to solve this question is to think in reverse way. Instead of finding a path from 1 to 100, try to find a path from 100 to 1.
So, the edge sequence with minimum number of edges is
1 → 3 → 9 → 10 → 11 → 33 → 99 → 100
which consists of 7 edges.
Question 110 
To carry out white box testing of a program, its flow chart representation is obtained as shown in the figure below:
For basis path based testing of this program, its cyclomatic complexity is
5  
4  
3  
2 
Question 111 
An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n  1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n  1)/2⌋, ⌊(n  3)/2⌋, ....., 0. The time required to construct a heap in this manner is
O(log n)  
O(n)  
O(n log log n)  
O(n log n) 
And we know that time complexity for building the heap is O(n).
Question 112 
Which one of the following binary trees has its inorder and preorder traversals as BCAD and ABCD, respectively?
Left root right.
Preorder traversal is,
Root left right.
Question 113 
Let f(n), g(n) and h(n) be functions defined for positive inter such that f(n) = O(g(n)), g(n) ≠ O(f(n)), g(n) = O(h(n)), and h(n) = O(g(n)). Which one of the following statements is FALSE?
f(n) + g(n) = O(h(n)) + h(n))  
f(n) = O(h(n))  
fh(n) ≠ O(f(n))  
f(n)h(n) ≠ O(g(n)h(n)) 
So, f(n)g(n) = O(g(n)h(n)) is True.
Hence, (D) is false.
Question 114 
Consider the undirected graph below:
Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?
(E, G), (C, F), (F, G), (A, D), (A, B), (A, C)  
(A, D), (A, B), (A, C), (C, F), (G, E), (F, G)  
(A, B), (A, D), (D, F), (F, G), (G, E), (F, C)  
(A, D), (A, B), (D, F), (F, C), (F, G), (G, E)

(C) produces connected component every instead a new edge is added but when first vertex is chosen (first vertex is chosen randomly) first edge must be minimum weight edge that is chosen. Therefore, (A, D) must be chosen before (A, B). Therefore (C) is false.
Question 115 
Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.
RECURSIVE ALGORITHM RECURRENCE RELATION P. Binary search I. T(n) = T(nk) + T(k) + cn Q. Merge sort II. T(n) = 2T(n1) + 1 R. Quick sort III. T(n) = 2T(n/2) + cn S. Tower of Hanoi IV. T(n) = T(n/2) + 1
PII, QIII, RIV, SI  
PIV, QIII, RI, SII  
PIII, QII, RIV, SI  
PIV, QII, RI, SIII 
Binary search  T(n/2) + 1
Merge sort  T(n) = 2T(n/2)+ cn
Tower of hanoi  T(n) = 2T(n1) +1
Question 116 
Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
f_{2}, f_{3}, f_{1}  
f_{3}, f_{2}, f_{1}  
f_{2}, f_{1}, f_{3}  
f_{1}, f_{2}, f_{3} 
The asymptotic notation order should be
Constant < logarithmic < linear < polynomial < exponential < factorial
F2 and F3 → Polynomial
F1 → Exponential
By the order of asymptotic notations F1 is definitely larger.
Method1:
Consider n=100
F1 : 100 ^100 ⇒ 1.e+200
F2 : N^log(100) base 2 ⇒ 100 ^ log(100) base 2 ⇒ 100^6.6438561897747 = 1,93,96,00,91,15,564.181300016469223466
F3 : N^Sqrt(n) ====> 100^Sqrt(100) ⇒ 100^10 ⇒ 10,00,00,00,00,00,00,00,00,000
Method2:
We can apply "log" on both sides.
log(F1)=nlog10 (base 2)
log(F2)=(logn)^2 = logn * logn (base 2)
log(F3)=sqrt(n)logn (base 2)
Answer: F2< F3< F1
Question 117 
p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18
Which of the following statements is/are correct about R_{7}?
R_{7is achieved by three different solutions.
}  
R_{7}=18  
R_{7}=19  
R_{7}cannot be achieved by a solution consisting of three pieces. 
There are 3 different possible ways to get the maximum amount.
P[6] + P[1] → 17+1 = 18
P[2] + P[2] + P[3] → 5+5+8 = 18
P[7] → 18 = 18
Question 118 
The number of minimumweight spanning trees of the graph is _______
3 
To find the number of spanning trees using 2 methods:
 If graph is complete, use n^n2 formula
 If graph is not complete, then use kirchhoff theorem.
Steps in Kirchoff’s Approach:
(i) Make an Adjacency matrix.
(ii) Replace all nondiagonal is by – 1.
(iii) Replace all diagonal zero’s by the degree of the corresponding vertex.
(iv) Cofactors of any element will give the number of spanning trees.
Using the Kirchhoff theorem will take lot of time because the number of vertices are 9.
So, we use brute force technique to solve the problem with the help of Kruskal's algorithm.
Question 119 
Which one of the following options is correct?
Question 120 
Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?
Quicksort using the last element as pivot  
Insertion sort  
Selection sort  
Mergesort 
Quick sort(with last element as pivot) → will give the worst case time complexity as O(n^2).
Merge Sort → The merge sort will not depend upon the input order and will give O(nlogn) time complexity.
Insertion Sort → Insertion sort will perform best case time complexity when the input array is in sorted order. If the array is already sorted then the inversion count is 0 and If the array is sorted in reverse order that inversion count is the maximum.
Note: Inversion formal definition is two elements A[i] and A[j] form an inversion if A[i] > A[j] and i < j.
The number of comparisons will not take more than “n” for the given input array.
Selection Sort → Selection sort will not depend upon the input order and will give O(n^2) time complexity.
Question 121 
Let assume n=512
Method1:
Using standard recursive algorithm:
MaxMin is a recursive algorithm that finds the maximum and minimum of the set of elements {a(i), a(i+1), ..., a(j)}. The situation of set sizes one (i=j) and two (i=j1) are handled separately. For sets containing more than two elements, the midpoint is determined ( just as in binary search) and two new subproblems are generated. When the maxima and minima of these subproblems are determined, the two maxima are compared and the two minima are compared to achieve the solution for the entire set.
To find the number of element comparisons needed for Maxmin, T(n) represents this number, then the resulting recurrence relation is
When n is a power of two, n = 2^{k} for some positive integer k, then
T(n)=2T(n/2)+2
=2(2T(n/4)+2)+2
=4T(n/4)+4+2
፧
=2k1T(2)+1ik12i
=2k1+2k2
=3n/22
→ The given example n=512
Apply into 3n/2 2
= (3*512)/2 2
= 7682
= 766
Method2:
Find the minimum and maximum independently, using n1 comparisons for each, for a total of 2n2 comparisons. In fact, at most 3⌊n/2⌋ comparisons are sufficient to find both the minimum and the maximum. The strategy is to maintain the minimum and maximum elements seen thus far. Rather than processing each element of the input by comparing it against the current minimum and maximum, at a cost of 2 comparisons per element, we process elements in pairs. We compare pairs of elements from the input first with each other, and then we compare the smaller to the current minimum and the larger to the current maximum, at a cost of 3 comparisons for every 2 elements.
Setting up initial values for the current minimum and maximum depends on whether n is odd or even. If n is odd, we set both the minimum and maximum to the value of the first element,and then we process the rest of the elements in pairs. If n is even, we perform 1 comparison on the first 2 elements to determine the initial values of the minimum and maximum, and then process the rest of the elements in pairs as in the case for odd n.
Let us analyze the total number of comparisons. If n is odd, then we perform 3⌊n/2⌋ comparisons. If n is even, we perform 1 initial comparison followed by 3(n2)/2 comparisons, for a total of (3n/2)2. Thus, in either case, the total number of comparisons is at most 3⌊n/2⌋.
Given an even number of elements. So, 3n/2 2 comparisons.
= (3*512)/2 2
= 7682
= 766
Method3:
By using Tournament Method:
Step1: To find the minimum element in the array will take n1 comparisons.
We are given 512 elements. So, to find the minimum element in the array will take 5121= 511
Step2: To find the largest element in the array using the tournament method.
 After the first round of Tournament , there will be exactly n/2 numbers =256 that will lose the round.
 The biggest loser (the largest number) should be among these 256 loosers.To find the largest number will take (n/2)−1 comparisons =2561 = 255
Total 511+255= 766
Question 122 
In this question they given three main constraints
 The input array is in sorted order
 Use recursive binary search
 Worst case number of operations
If the array is in sorted order then the worst case time complexity is O(logn)
Ex: 10, 20, 30
The binary search approach is using either recursive or iterative method is
Step1: element = middle, the element is found and return the index.
Step2: element > middle, search for the element in the subarray starting from middle+1 index to n.
Step3: element < middle, search for element in the subarray starting from 0 index to middle 1.
Note: The worst case happens when we want to find the smallest/largest farthest node. So, it will not take more than O(logn) time.
Question 123 
Which one of the following options is correct about the recurrence T(n)?
Question 124 
S_{1}: There exists a minimum weighted edge in G which is present in every minimum spanning tree of G.
S_{2}:If every edge in G has distinct weight, then G has a unique minimum spanning tree.
Which of the following options is correct?
S_{1}is false and S_{2}is true.
 
S_{1}is true and S_{2}is false.  
Both S_{1} and S_{2}are false.  
Both S_{1} and S_{2}are true. 
Statement1: FALSE: The given statement is not valid for all the cases because they are not mentioned, edge weights are in distinct or duplicate. So, we can take any random edge weights for the given statement.
Example:
Statement2: TRUE: Using the kruskal’s (or) prim's algorithm we get a unique MST when there is a unique edge weight.
Example:
Based on the above graph, we get the MST is
Question 125 
The sum of the qualityscores of all the vertices in the graph shown above is _________.
929 
Question 126 
The heap is nothing but a complete binary tree and uses linear search to find the elements.
In min heap, the parent key is less than or equal to (≤) the child keys. The maximum values should present in the farthest leaf node for the worst case time complexity.
To traverse all the elements in a heap will take O(n) time for the worst case because it uses the linear search to find the element.
Question 127 
f ( n ^2 ) ( f ( n ) ^2 ), when f ( n ) is a polynomial  
f ( n ^2 ) o ( f ( n ) ^2 )  
f ( n ^2 ) O ( f ( n ) ^2 ), when f ( n ) is an exponential function  
f(n)=n^c where c is a constant
f(n^2) = (n^2)^c = n^2c
(f(n))^2 = (n^c)^2 = n^2c
f(n^2) = (f(n))^2 is TRUE asymptotically.
OptionB: FALSE: The small omega function indicates the tightest upper bound.
f(n)^2 < o(f(n)^2) is FALSE asymptotically.
OptionC: FALSE: Consider f(n)=logn
f(n^2)=logn^2 = 2*logn
(f(n))^2 = (logn)^2 = logn * logn
f(n^2) <=Ω(f(n))^2 is FALSE asymptotically.
OptionD: FALSE:
Exponential values(Eg: 2^n, 3^n,..,k^n where k is a constant ”
f(n)=3^n
f(n^2)=f(3^(n^2)
(f(n))^2 = (3^n)^2 = 3^2n
f(n^2) >= O(f(n))^2 is FALSE asymptotically.
Question 128 
m/n  
n/m  
2n/m  
n/2m 
How?
For 1st element the probability of key1 ends up in slot 1 is 1/m.
For 2nd element the probability of key2 ends up in slot 2 is 1/m
..
..
For nth element the probability of keyn ends up in slot n is 1/m
Hence expected number of elements in a slot is:
1/m+1/m+... (n times)= n/m
In the given question h1 is for elements at even sequence position and h2 is for odd number of sequence positions. This will not affect the overall probability.
Hence here also it is n/m
Question 129 
509 
Now, the 3^rd largest number will be at location of max3. We can find what can be the probable index values of max1 at different levels. They will be 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023 . . .
∴ 511 is index value of our max1
510 is index value of our max2
509 is index value of our max3
& Hence, Answer is 509
Question 130 
The edge with the second smallest weight is always part of any minimum spanning tree of G .  
One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G .  
G can have multiple minimum spanning trees. 
OptionA: TRUE: As per the above graph, the second minimum edge weight is also part of the MST.
The second smallest weight is always in MST because it will not form a cycle.
OptionB: FALSE: As per the above graph, the third minimum edge weight is not part of the MST.
The third or fourth edge weight may be part of the cycle. So, it may or may not be in MST.
OptionC: TRUE: As per the example graph, it is always correct.
OptionD: FALSE: We will get a unique minimum spanning tree if edge weights are distinct.
Question 131 
Then, which of the following statements is/are TRUE?
f (2^ n 1) 2^ n 1  
f (2 ^n ) 1  
f (5 . 2 ^n ) 2^ n + 1 1  
f (2^ n + 1) 2 ^n + 1 
Based on the “n” value we can get OptionA, B and C are correct.
Question 132 
24 
Graph have 3 elements > We get 2 MSTs
Graph have 4 elements > We get 6 MSTs (3*2*1)
Graph have 5 elements > We get 24 MSTs(4*3*2*1)
Question 133 
Divide and Conquer  
Dynamic Programming  
Greedy Algorithm  
Branch and Bound 
Sum of subset problem:
Given a set of nonnegative integers, and a value sum, determine if there is a subset of the given set with the sum equal to the given sum.
Example:
Array set[ ]= {1,2,3,4,5} and sum=6
Here there are possible subsets (2,4),(1,2,3) and (5,1).
Question 134 
m*n  
maximum of m and n  
minimum of m and n  
m+n–1 
For example: Take 2 subarrays of size 3 such as 1,3,5 and another subarray 2,4,6. Then in this case number of comparisons is 5 which is m+n1 can be taken as O(m+n).
Question 135 
Merge Sort  
Insertion Sort  
Selection Sort  
Quick Sort 
Question 136 
Detailed  
Aggregate  
Qualitative  
None of the above 
Question 137 
Greedy method  
Divideandconquer  
Dynamic Programming  
Backtracking 
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray. Clearly, it is a greedy approach to sort the array.
Question 138 
O(n^{2}), O(n^{2})  
O(n^{2}), O(nlog_{2}n)  
O(n log_{2}n), O(n^{2})  
O(n log_{2}n), O(n log_{2}n) 
Question 139 
O ( log_{2}n )  
O ( n )  
O ( n log_{2}n )  
O ( n_{2} ) 
Question 140 
1, 3, 5, 7, 9, 11, 13  
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55  
0, 1, 3, 4, 7, 11, 18, 29, 47  
0, 1, 3, 7, 15 
with seed values
F0 = 0 and F1 = 1.
The Fibonacci numbers are the numbers in the following integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144..
Question 141 
Then what should be the relation between T(1), T(2) and T(3), so that the order of the algorithm is constant?
T(1) = T(2) = T(3)  
T(1) + T(3) = 2 * T(2)  
T(1) – T(3) = T(2)  
T(1) + T(2) = T(3) 
Solution:
Better way of solving is substitute.
T(1) = 1
T(2) = 2
T(3) = 3
T(4) = T(3) + T(2)  T(1) = 4
T(5) = T(4) + T(3)  T(2) = 5
:
:
T(n) = T(n1) + T(n2)  T(n3) = n1 + n2  n + 3 = n
So order is O(n)
Question 142 
O(n)  
O(n log n)  
O(n^{3/2})  
O(n^{3}) 
→ For example, if X is a set of airports and x R y means "there is a direct flight from airport x to airport y" (for x and y in X), then the transitive closure of R on X is the relation R+ such that x R+ y means "it is possible to fly from x to y in one or more flights". Informally, the transitive closure gives you the set of all places you can get to from any starting place.
→ To find the transitive closure of given relation, we can represent the given relation by the graph such that if x R y then there should be directed edge between x and y in a graph.
→ The time complexity of floyd warshall algorithm is O(V3) where V is the number of vertices in the given graph. Take V as the number of elements is set i.e., N.
→ Therefore time complexity for the given question is O(n3).
Question 143 
Dynamic programming  
Backtracking  
Greedy  
Divide and Conquer 
→ A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices
→ The FloydWarshall algorithm is an example of dynamic programming.
Question 144 
Both NPcomplete  
Both in P  
NPcomplete and in P, respectively  
Undecidable and NPcomplete, respectively 
→ 3SAT problem is NP complete problem
Question 145 
T(n)=2T(n/2)+k , where k is constant  
T(n)=T(n/2) +k, where k is constant  
T(n)=T(n/2)+logn  
T(n)=T(n/2)+n 
The time to search in an array of ‘n’ elements is equal to the time to search in an array of n/2 elements plus k comparison.
T(n)=T(n/2)+k // k is constant
Question 146 
Insertion Sort  
Quick Sort  
Heap Sort  
Selection Sort 
Question 147 
11  
12  
13  
10 
Step2: 8,7,9,22,31,5,13
Step3: 8,7,9,22,5,31,13
Step4: 8,7,9,22,5,13,31
Step5: 7,8,9,22,5,13,31
Step6: 7,8,9,5,22,13,31
Step7: 7,8,9,5,13,22,31
Step8: 7,8,5,9,13,22,31
Step9: 7,5,8,9,13,22,31
Step10: 5,7,8,9,12,22,31
Note:Total 10 swaps are required to sort the array.
Question 148 
Prim’s algorithm  
Dijkstra's algorithm  
BellmanFord’s algorithm  
FloydWarshall’s algorithm 
Dijkstra's algorithm → Single source shortest path for only positive values
Bellman Ford’s algorithm → Single source shortest path for either positive values or negative values but not negative weight cycle.
FloydWarshall’s algorithm→ All pair shortest path problem
Question 149 
O(nlogn)  
O(n^{3/2})  
O(n^{3})  
O(n) 
Question 150 
1  
5  
10  
20 
1st iteration will compare 4 numbers with the 5
2nd iteration will compare 3 numbers with the 4
3rd iteration will compare 2 numbers with the 3
4th iteration i will compare 1 number with the 2
So, the total number of comparisons is 4 + 3 + 2 + 1 = 10
It can be viewed as the sum of the sequence of the first (n1) numbers starting by 1
S = ((1 + (n1) )*(n1) )/2
S = 10
Question 151 
T(n) = 2T(n1), if n>0
= 1, otherwise
Then T(n) is (in big O order)
O(n)  
O(2  
O(1)  
O(log n) 
Question 152 
r, s, p, q  
r, p, s, q  
q, s, p, r  
s, p, q, r 
Insertion sort→ Decrease and Conquer
Gaussian Elimination→ Transform and Conquer
Floyd Shortest path algorithm→ Dynamic programming
Question 153 
You can set the initial height at which the gun fires. As the game progresses, you can reset the height, but only to a lower value. You are given in advance the height at which each spaceship flies. There are N spaceships numbered 1, 2, . . . , N in the order in which they fly across the screen. For 1 ≤ i ≤ N , h[i] denotes the height at which spaceship i flies.
(a) Let V [i] denote the maximum number of spaceships from i, i+1, . . . , N that you can shoot down with a single gun. Write a recurrence for V [i] and describe a strategy to compute V [i] using dynamic programming. What is the space and time complexity of your solution?
(b) Describe an algorithm to compute the minimum number of guns required to shoot down all the spaceships. Each gun can be initialized separately to a firing height and each gun can be separately reset to a lower value.
Descriptive Explanation 
V [N ] = 1
V [i] = 1 + max{V [j]  j > i and h[i] ⩾ h[j]}
The dynamic programming algorithm maintains an array V of size N , to be filled in from V [N ] to V [1]. Computing the value of V [i] takes O(N ) time, since it involves potentially examining all entries from V [i + 1] to V [N ]. Thus the time taken overall is O(N ^{2} ). The space required is O(N ).
(b) The above algorithm can be modified to produce not just the length of the longest descending subsequence, but the subsequence itself. Once we do this, we delete these entries from the h list and find the longest descending subsequence now. We repeat this process till the original h list has been decomposed into disjoint descending subsequences. Since each of these subsequences can be handled by one gun, the minimum number of guns required to shoot down all the spaceships is the number of disjoint subsequences computed above.
Question 154 
n/2  
(n1)/2  
(n+1)/2  
None of these 
= No. of comparisons if element present in 1^{st} position + No. of comparisons if element present in 2^{nd}nd position + ............. + No. of comparisons if element present in n^{th} position
= 1+2+3+ ... + n
= n(n+1)/2
Since there are n elements in the list, so average no. of comparisons
= Total comparisons/Total no. of elements
= (n(n+1)/2)/n
= n+1/2
Question 155 
Dynamic programming  
Backtracking  
Divide and conquer  
Greedy method 
1. Quick sort
2. Merge sort
3. Heap sort
****Binary search also follows the divide and conquer.
Question 156 
T(n) = 2T(√n) + 1
T(1) = 1
Which of the following is true?
T(n)= O(log log n)  
T(n) = O(log n)  
T(n) = O(√n)  
T(n)= O(n) 
Question 157 
Explanation 
Step 1 Sort array A.
Step 2 Traverse through A to find the most frequent element by keeping counters. Since the numbers with same value would appear in consecutive locations in the sorted array A, this can be achieved in one pass. Let maximum frequency is M AX.
Step 3 Traverse through A once more to report all the elements that matches whose frequencies match with M AX.
Since Step 1 needs O(n log n) time, the overall time complexity is O(n log n).
Question 158 
Explanation 
For i ∈ 1, 2, . . . , n, let LAS[i] denote the length of the longest ascending subsequence ending at position i. We can set up the following inductive calculation for LAS[i].
• LAS[1] = 1
• For i ∈ 2, 3, . . . , n, LAS[i] = 1 + max{LAS[j]  1 ≤ j < i, S[j] < S[i]}
We can use this to compute LAS[i] for i ∈ 1, 2, . . . , n in time O(n 2 ) — computing LAS[i] takes time O(i), so the total time is .The final answer is the maximum value among all the LAS[i]’s, which can be found in time O(n).
The computation of LAS can be improved to O(n log n) by maintaining auxiliary intermediate information about the longest ascending sequences computed at each stage. Refer to any standard textbook on algorithms.
Question 159 
L  
L/2  
(L+1)/2  
2L 
A linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list , whether element is found or not
Question 160 
O(n)  
O(n log n)  
O(n^{2})  
O(n^{3}) 
T(n + 1) = 2n + T(n)
By substitution method:
n=1, T(2)=2x1+T(1)=2+10=12
n=2,T(3)=2x2+T(2)=4+12=16
n=3,T(4)=2x3+T(3)=6+16=22
n=4,T(5)=2x4+T(4)=8+22=30
n=5,T(6)=2x5+T(5)=10+30=40
n=6,T(7)=2x6+T(6)=12+40=52
n=7,T(8)=2x7+T(7)=14+52=66
The above T(n) value is always less than n2, Then the function is O(n^{2})
Question 161 
Greedy method  
Backtracking  
Dynamic programming  
Divide and Conquer 
Conceptually, a merge sort works as follows:
1. Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.
Question 162 
Insertion sort, Quick sort  
Quick sort, Quick sort  
Quick sort, Insertion sort  
Insertion sort, Insertion sort 
Question 163 
3.00  
3.46  
2.81  
3.33 
Each level has 2i nodes where i is level number
Level 0 has one node so one comparison(1)
Level 1 has two nodes so for each node two comparisons and total four comparisons (4)
Level 2 has four nodes and total comparisons are 4x3 =12 comparisons
Level3 has total 8 nodes but in the given question we need to process only 11 items and already we covered 7 nodes so remaining nodes 4 nodes at level 3. Total comparisons at level3 are 4*4=16
So, total number of comparisons at each level are = 1+4+12+16= 33
Average comparisons required for 11 items = 33/11 = 3
Question 164 
 Quicksort
 Heapsort
 Mergesort
1 and 2 only  
2 and 3 only  
3 only  
1, 1 and 3 
Question 165 
int module(int n)
{
if (n == 1)
return 1;
else
return (n + module(n1));
}
O(n)  
O(log n)  
O(n^{2})  
O(n!) 
Question 166 
The solution of the recurrence relation T(m) = T(3m/4) + 1 is :
θ(lg m)  
θ(m)  
θ(mlg m)  
θ(lglg m)

a = 1, b = 4/3, k = 0, p = 0
Here, a = b^{k}
So, T(m) = n^{log a/ log b} log^{p+1} n
T(m) = θ(log m)
Question 167 
Which of the following algorithms solves the singlesource shortest paths ?
Prim’s algorithm  
Floyd  Warshall algorithm  
Johnson’s algorithm  
Dijkstra’s algorithm

Question 168 
A text is made up of the characters A, B, C, D, E each occurring with the probability 0.08, 0.40, 0.25, 0.15 and 0.12 respectively. The optimal coding technique will have the average length of :
2.4  
1.87  
3.0  
2.15 
Step 1: Select two characters with smallest probabilities and merge them.
Step 2: Select two characters from Step 1 with smallest probabilities and merge them.
Step 3: Select two characters (from Step 2) with smallest probabilities and merge them.
Step 4: Merge the remaining two probabilities.
A = 1000 (4bits)
E = 1001 (4bits)
D = 101 (3bits)
C = 11 (2bits)
B = 0 (1bit)
Question 169 
A binary search tree in which every nonleaf node has nonempty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves :
cannot have more than 37 nodes  
has exactly 37 nodes
 
has exactly 35 nodes  
cannot have more than 35 nodes 
Where,
L = Number of leaf nodes
n = Nary tree
I = Number of intermediate nodes
Now,
19 = I(2  1) + 1
19 = 2I  I + 1
19 = I + 1
I = 18
Total Number of nodes in a tree = Number of Intermediate nodes + Number of Leaf nodes
Total Number of nodes in a tree = 19 + 18
Total Number of nodes in a tree = 37
Question 170 
Match the following with respect to algorithm paradigms :
ListI ListII (a) The 8Queens problem (i) Dynamic programming (b) SingleSource shortest paths (ii) Divide and conquer (c) STRASSEN’s Matrix multiplication (iii) Greedy approach (d) Optimal binary search trees (iv) Backtracking
(a)(iv), (b)(i), (c)(iii), (d)(ii)  
(a)(iv), (b)(iii), (c)(i), (d)(ii)  
(a)(iii), (b)(iv), (c)(ii), (d)(i)  
(a)(iv), (b)(iii), (c)(ii), (d)(i) 
SingleSource shortest paths use Greedy approach.
STRASSEN’s Matrix multiplication use Divide and conquer technique.
Optimal binary search trees use Dynamic programming.
Question 171 
45  
72  
360  
450 
Octal number having → 5 digits
The octal number system base value = 8
The maximum number of comparison = (number of items) * (radix) * (number of digits)
= 9 * 5 * 8
= 360
Question 172 
A 5ary tree is tree in which every internal node has exactly 5 children. The number of left nodes in such a tree with 8 internal nodes will be :
30  
33  
45  
None of the above 
L = I(n  1) + 1
Where,
L = Number of leaf nodes
n = Nary tree
I = Number of intermediate nodes
Now, L = 8(5  1) + 1
L = 8(4) + 1
L = 33
Total Number of nodes in a tree = Number of Intermediate nodes + Number of Leaf nodes
Total Number of nodes in a tree = 8 + 33
Total Number of nodes in a tree = 41
Question 173 
Consider a Boolean function of ‘n’ variables. The order of an algorithm that determines whether the Boolean function produces a output 1 is :
Logarithmic  
Linear
 
Quadratic  
Exponential 
Set 1 have “n” variables and each variable in set 1 can be mapped with one boolean value in set 2 i.e,. each variable in set 1 have 2 choices and we have “n” such variables in set 1.
→ So, total number of choices we get maximum 2^{n}. It means exponential.
Question 174 
E is the number of edges in the graph and f is maximum flow in the graph. When the capacities are integers, the runtime of FordFulkerson algorithm is bounded by :
O(E∗f)
 
O(E^{2}∗f)
 
O(E∗f^{2})
 
None of the above 
→ The FordFulkerson method or FordFulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network.
→ It is called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times.
→ the runtime of FordFulkerson is bounded by O(E*f), where E is the number of edges in the graph and f is the maximum flow in the graph. This is because each augmenting path can be found in O(E) time and increases the flow by an integer amount of at least 1, with the upper bound f.
→ The variation of the FordFulkerson algorithm with guaranteed termination and a runtime independent of the maximum flow value is the EdmondsKarp algorithm, which runs in O(VE^{2})time.
Question 175 
T(n)=2T(n1), if n>0.
=1, otherwise
O(nlogn)  
O(n^{2})  
O(2^{n})  
O(n) 
= 2 [2T(n  2) + 1] + 1
= 2^{2} T(n  2) + 3
⋮
= 2^{k}T(n  k) + (2^{k}  1)
= 2^{n1}T(1) + (2^{n1}  1)
= 2^{n1}+ 2^{n1}  1
= 2^{n}  1
≅ O( 2^{n} )
Question 176 
O(nlogn)  
O(logn)  
O(n)  
O(n^{2}) 
Question 177 
O(n)  
O(nlogn)  
O(logn) for search and insert, and O(n) for delete  
None of these 
→ In question, they are not mentioned about elements are sorted or unsorted. So, worst case we have to consider unsorted elements.
→ All operations(i.e. Search,update and delete) will take O(n).
Question 178 
Greedy approach  
Dynamic programming  
Backtracking paradigm  
Divide and conquer paradigm 
→ Dijkstra’s algorithm is solving the problem of single source shortest path.
Question 179 
89,19,50,17,12,15,2,5,7,11,6,9,100
Minimum _____ number of interchanges are needed to convert it into a maxheap
3  
4  
5  
6 
2nd swap is: 100 and 50
3rd swap is: 100 and 89
Question 180 
Selection sort  
Bubble sort  
Merge sort  
Quick sort 
Question 181 
12  
10  
6  
5 
Question 182 
Greedy  
Branch and bound  
Dynamic Programming  
Backtracking 
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.
Question 183 
True,True  
False, False  
True,False  
False,False 
Question 184 
Quick sort  
Merge sort  
Shell sort  
Bubble sort 
Question 185 
T(n)=2T(n2)+2  
T(n)=2T(n/2)+1  
T(n)=2T(n2)+n  
T(n)=2T(n1)+1 
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 2 ^{2 }T(n – 2) + 3
⋮
= 2 ^{k} T( n – k) + (2 ^{k} – 1)
n – k = 1
= 2 ^{n1} T(1) + (2^{ n1} – 1)
= 2^{ n1} + 2^{ n1} – 1
= 2 ^{n} – 1
≌ O(2 ^{n} )
Question 186 
O(mn)  
O(m)  
O(m+n)  
O(n) 
Step1: Sorting of edges takes O(ELogE) time.
Step2: After sorting, we iterate through all edges and apply find union algorithm.
The find and union operations can take at most O(1) time if you use Disjoint set . So overall complexity is O(ELogE + E) time.
Given the edges are already sorted, so we need to do only second step i.e.,we iterate through all edges and apply findunion algorithm. The find and union operations can take at most O(1) time. So, the total time complexity will be O(E).
Question 187 
Consider the following terminology and match List 1 and List 2 and choose the correct answer from the code given below
 b = branch factor
d = depth of shallowest solution
M = Maximum depth of the search tree
l = depth limit
List 1 List 2 (a) BFS i) O(bd) (b) DFS ii) O(b^{d}) (c) Depth Limited Search iii) O(bm) (d) Iterative deepening Search iv) O(bl)Code:
(a)(iii), (b)(ii), (c)(iv), (d)(i)
 
(a)(ii), (b)(iii), (c)(iv), (d)(i)
 
(a)(i), (b)(ii), (c)(iv), (d)(iii)
 
(a)(i), (b)(iii), (c)(iv), (d)(ii)

DFS → O(bm) worst case space complexity
Depth  Limited Search → O(bl)
Iterative deepening Search → O(bd)
Note:
Based upon BFS and DFS we can find the solution.
Question 188 
12  
10  
6  
5 
because n^{2} is asymptotically larger than nlogn. Finally, 10nlog _{10} n ≤ 0.0001n ^{2}
Let n = 10^{ k} records. Substitute into 10nlog _{10} n ≤ 0.0001n^{ 2}
10(10^{ k} )log_{ 10} 10^{ }k ≤ 0.0001(10^{ k} )^{ 2}
10^{ k+1} k ≤ 0.0001 × 10^{ 2k}
k ≤ 10
2k−k−1−4
k ≤ 10
k−5
According to the problem value 6 is suitable for K.
Question 189 
O(nlogn),O(nlogn) and O(n^{2})  
O(n^{2}),O(n^{2}) and O(nlogn)  
O(n^{2}),O(nlogn) and O(nlogn)  
O(n^{2}),O(nlogn) and O(n^{2}) 
merge sort → O(nlogn)
quick sort → O(n^{2})
Question 190 
O(logn)  
O(n)  
O(nlogn)  
none of the above, as the tree cannot be be uniquely determined. 
T(n) = T(k) + T(nk1) + logn
In worst case T(n) = O(nlogn), when k=0
But searching for an element in the inorder traversal of given BST can be done in O(1) because we have n elements from 1...n so there is no need to search an element if last element in post order is say 5 we take it as root and since 4 elements are split the post order array into two (first 4 elements), (6th element onward) and solve recursively. Time complexity for this would be
T(n) = T(k) + T(nk1)+O(1)
Which gives T(n) = O(n)
since we know that all elements must be traversed at least once T(n) = θ(n)
Question 191 
O(n)  
O(m)  
O(m+n)  
O(mn) 
Suppose if we are using Adjacency matrix means it takes θ(n ^{2} ).
Question 192 
solves it in linear time using a left to right pass of the array  
solves in linear time using a right to left pass of the array  
solves it using divide and conquer in time O(nlogn)  
solves it in time O(n ^{2} ) 
● Start from the right keeping track of largest element (currentLeader). If a larger element is found, then print it and set currentLeader to the current element.
● We can consider the last element is a leader since there is no element to its right. Solves it in linear time using a right to left pass of the array will takes time complexity is O(n).
Question 193 
Bellman ford algorithm for single source shortest path  
floyd Warshall for all pairs shortest paths  
01 knapsack problem  
Prim’s minimum spanning tree 
Question 194 
Maximum sum subsequence in an array  
Maximum sum subarray in an array  
Maximum product subsequence in an array  
Maximum product subarray in an array 
def max_subarray(A):
max_ending_here = max_so_far = A[0]
for x in A[1:]:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
Question 195 
O(nlogd)  
O(n^{2} logd)  
O(nd)  
O(n^{2}d) 
→ They are asking to find the atmost distance from every element. So, it will take O(n^{2}*d) from every node.
Note: Using heap sort , time complexity will be O(nlogd) and most effective than insertion sort.
Question 196 
Every minimum spanning tree of G must contain e_{min} and e_{max}  
If e_{max} is in a minimum spanning tree, then its removal must disconnect G  
No minimum spanning tree contains e_{max}  
G has a multiple minimum spanning trees 
If they mentioned distinct weights then we will get only one MST. So, OptionC is most appropriate solution.
Question 197 
nlog(n/2)  
nlogn  
(nlogn)/2  
logn 
Question 198 
Match List1 with List2 and choose the correct answer from the code given below
List 1 List 2 (a) Greedy Bestfirst Search (i) Selects a node for expansion if optimal path to that node has been found (b) A* Search (ii) Avoids substantial overhead associated with keeping the sorted queue of nodes (c) Recursive BestFirst Search (iii) Suffers from excessive node generation (d) Iterativedeepening A* Search (iv) Time complexity depends upon the quality of heuristicCode:
(a)(iv), (b)(iii), (c)(ii), (d)(i)  
(a)(i), (b)(iv), (c)(iii), (d)(ii)
 
(a)(iv), (b)(i), (c)(ii), (d)(iii)
 
(a)(i), (b)(ii), (c)(iii), (d)(iv)

→ A* Search: Time complexity depends upon the quality of heuristic.
→ Recursive BestFirst Search: Suffers from excessive node generation. RBFS depends on how widely the promising nodes are separated in the search tree, and is harder to anticipate.
→ Iterativedeepening A* Search: Avoids substantial overhead associated with keeping the sorted queue of nodes.
Question 199 
Insertion sort  
merge sort  
Quick sort  
bubble sort 
Question 200 
O(m*n)  
O(m+n)  
O(m^{2})  
O(m^{n}) 
1. DFS search produces a DFS tree/forest
2. Strongly Connected Components form subtrees of the DFS tree.
3. If we can find head of such subtrees, we can print/store all the nodes in that subtree (including head) and that will be one SCC.
4. There is no back edge from one SCC to another (There can be cross edges, but cross edges will not be used while processing the graph).
Note: Time complexity for Tarjan’s algorithm is O(V+E)
Kosaraju’s algorithm
1) Create an empty stack ‘S’ and do DFS traversal of a graph. In DFS traversal, after calling recursive DFS for adjacent vertices of a vertex, push the vertex to stack. In the above graph, if we start DFS from vertex 0, we get vertices in stack as 1, 2, 4, 3, 0.
2) Reverse directions of all arcs to obtain the transpose graph.
3) One by one pop a vertex from S while S is not empty. Let the popped vertex be ‘v’. Take v as source and do DFS (call DFSUtil(v)). The DFS starting from v prints strongly connected component of v. In the above example, we process vertices in order 0, 3, 4, 2, 1 (One by one popped from stack).
Note: Time complexity for kosaraju’s algorithm is O(V+E)
Question 201 
P  
NP  
Both (A) and (B)  
None of these 
Question 202 
logn  
n  
n ^{2 }  
n^{ n} 
Question 203 
Consider the graph shown below :
Use Kruskal’s algorithm to find the minimum spanning tree of the graph. The weight of this minimum spanning tree is
13  
16  
17  
14 
The weight of this minimum spanning tree is 16.
Question 204 
Match List 1 with List 2 and choose the correct answer from the code given below :
List I List II (Graph Algorithm) (Time Complexity) (a) Dijkstra’s algorithm (i) O(E lg E) (b) Kruskal’s algorithm (ii) Θ(V3) (c) FloydWarshall algorithm (iii) O(V2) (d) Topological sorting (iv) Θ(V + E)
Where V and E are the number of vertices and edges in graph respectively.
Code :(a)(i), (b)(iii), (c)(iv), (d)(ii)
 
(a)(i), (b)(iii), (c)(ii), (d)(iv)
 
(a)(iii), (b)(i), (c)(ii), (d)(iv)
 
(a)(iii), (b)(i), (c)(iv), (d)(ii) 
→ Kruskal's algorithm is a minimumspanningtree algorithm which finds an edge of the least possible weight that connects any two trees in the forest and time complexity is O(E log E).
→ A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v,u comes before v in the ordering Θ(V + E).
→ Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths of shortest paths between all pairs of vertices.
Question 205 
The second smallest of n elements can be found with _______ comparisons in worst case.
n + ceil(lg n)  2
 
n  1  
lg n  
3n/1

This takes n1 comparisons and each element involved is compared at most log n times. Finally, we get the largest element A1’’’. This element which is largest, has won comparison with the second largest element at some point. So, keeping track of items compared with the largest element will give us a list of (log n) elements. In this list we find out largest, which will be the second largest of all.
So, no. of comparisons = (n  1) + log2 (n)  1
Example: 512 elements
In this case no. of comparisons will be, (512  1) + log2(512)  1
= 511 + (9  1)
= 511 + 8
= 519
Question 206 
Place reference to them in and array an sort the array  
place them in a linked list and sort the linked list  
place pointers to them in an array and sort the array  
place them in an array and sort the array 
OptionB is not correct because it will extra time complexity and searching very difficult
OptionD is suitable for small amount of objects/elements
Question 207 
Consider two sequences X and Y :
 X = <0,1,2,1,3,0,1 >
Y = <1,3,2,0,1,0 >
The length of longest common subsequence between X and Y is
4  
2  
3  
5ComputerNetworks 
Possible subsequences are : 130, 1210, 1301 and length of longest common subsequence is 4.
Question 208 
The solution of recurrence relation : T(n) = 2T(sqrt(n)) + lg(n) is
O(lg (n) lg(n))
 
O(lg (n))
 
O(n lg (n))
 
O(lg (n) lg(lg(n)))

Question 209 
If it takes O(n log n) time  
It uses divide and conquer technique  
Relative order of occurrence of nondistinct elements is maintained  
It takes O(n) space 
→ That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.
Question 210 
Optimization  
NP complete  
Linear Solution  
Sorting 
Question 211 
(Bounds given may or may not be asymptotically tight)
q, r, p  
p, q, r  
q, p, r  
r, q, p 
Hash table construction→ O(n^{2})
AVL tree construction → O(logn)
Question 212 
A. 1, 2, 3……n
B. n, n1, n2 …… 1
Let C1 and C2 be the number of comparisons made for A and B respectively. Then
C1>C2  
C1=C2  
C1  
Cannot say anything for arbitrary n 
→ Elements are already sorted order it gives worst case complexity O(n^{2})
→ If all elements are having same weight, it performs worst case complexity.
Question 213 
No. of inputs  
Arrangement of elements in an array  
Size of elements  
Pivot element 
Question 214 
Processor and Memory  
Complexity and Capacity  
Time and Space  
Data and Space 
Time complexity is a function describing the amount of time an algorithm takes in terms of the amount of input to the algorithm. "Time" can mean the number of memory accesses performed, the number of comparisons between integers, the number of times some inner loop is executed, or some other natural unit related to the amount of real time the algorithm will take. We try to keep this idea of time separate from "wall clock" time, since many factors unrelated to the algorithm itself can affect the real time (like the language used, type of computing hardware, proficiency of the programmer, optimization in the compiler, etc.). It turns out that, if we chose the units wisely, all of the other stuff doesn't matter and we can get an independent measure of the efficiency of the algorithm.
Space complexity is a function describing the amount of memory (space) an algorithm takes in terms of the amount of input to the algorithm. We often speak of "extra" memory needed, not counting the memory needed to store the input itself. Again, we use natural (but fixedlength) units to measure this. We can use bytes, but it's easier to use, say, number of integers used, number of fixedsized structures, etc. Space complexity is sometimes ignored because the space used is minimal and/or obvious, but sometimes it becomes as important an issue as time.
Question 215 
O(log n)  
O(n)  
O(n logn)  
None of these 
a=1,b=2,k=1,p=0
=ak
=O(n)
Question 216 
It can be used to decide the best algorithm that solves a given problem  
It is the lower bound of the growth rate of algorithm  
It determines the maximum size of a problem that can be solved in a given amount of time  
Both (A) and (B) 
● The letter O is used because the growth rate of a function is also referred to as the order of the function.
● A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.
Question 217 
50.2 sec  
6.7 sec  
72.7 sec  
11.2 sec 
The Worst case time complexity is O(n^{2})
Average and best case time complexity is O(n logn)
Step1: Time taken to sort 1000 names by quicksort
100= c*nlogn
= c*1000log1000
= 100
c=1/10log1000
Now, time taken to sort 100 names by quicksort,
=c*nlogn
= (1/10log1000)*100*log100
= 6.7
Question 218 
F3, F4, F1, F5, F6, F2  
F2, F6, F5, F1, F4, F3  
F1, F2, F3, F4, F5, F6  
Ordering is immaterial as all files are accessed with the same frequency. 
→ Final order is F3, F4, F1, F5, F6, F2
Question 219 
int recursive (int n)
{
if(n == 1)
return (1);
else
return (recursive (n1) + recursive (n1));
}
O(n)  
O(n log n)  
O(n^{2})  
O(2^{n}) 
= 2 [2T(n  2) + 1] + 1
= 2^{2} T(n  2) + 3
⋮
= 2^{k}T(n  k) + (2^{k}  1)
= 2^{n1}T(1) + (2^{n1}  1)
= 2^{n1} + 2^{n1}  1
= 2^{n}  1
≅ O( 2^{n} )
Question 220 
2^{5}  
7^{5}  
3^{5}  
2^{2×5} 
Here, there are 7 nodes.
=7^{72}
=7^{5}
=16,807
Question 221 
20, 47, 15, 8, 9, 4, 40, 30, 12, 17
then the order of these elements after second pass of the algorithm is:
8, 9, 15, 20, 47, 4, 12, 17, 30, 40  
8, 15, 20, 47, 4, 9, 30, 40, 12, 17  
15, 20, 47, 4, 8, 9, 12, 30, 40, 17  
4, 8, 9, 15, 20, 47, 12, 17, 30, 40 
Question 222 
19  
18  
17  
20 
→ According to above Profit/weight ratio, the item1 having maximum profit. So, pick item1.
→ Now M=7, Pick item2 because it has more profit.
→ Now M=5, Now according to profit/weight ration we can pick item3 or item5 but item5 having more weight, so it exceeds capacity. If we are selecting item3 means we are wasting 1 slot. So, here, profit/weight ration fails. So, follow brute force technique in this position. We can pick item4 because it has weight 5.
→ Now, M=0 and Profit=19. [item1 + item2 + item4]
Question 223 
What is the total number of spanning trees of a complete graph of 4 vertices (K_{4})?
16  
8  
4  
15 
n^{n2} = 4^{2} = 16
Question 224 
void Function(int n)
{
int i=1;
int s=1;
while(s<=n)
{
i++;
s=s+i;
}
}
O(n)  
O(n^{ 2} )  
O(1)  
O(√n) 
i= 1, 2, 3, 4, 5, 6…..
Here, ‘S’ is nothing but sum of ‘n’ natural numbers
Assume the n=21, then corresponding k value 6. "k^2" is nothing but 36 which is greater than "n"
For any given K value , the S value is k(k+1)/2, So, 6(6+1)/2=21
the loop will terminate whenever k(k+1)/2 >n
k=O(√n)
Question 225 
T(n)=8T(n/2)+qn, if n>1
=p, if n=1
Where p,q are constants. The order of this algorithm is
n^{2}  
n^{n}  
n^{3}  
N 
a=8,b=2,k=0,p=0;
So, according to masters theorem, a>b ^{k}
=O(n^log _{2}^{ 8} )
=O(n^{ 3} )
Question 226 
Which of the following data structures is most suitable for radix sort?
Stack
 
Binary search tree
 
Tree
 
Linked list

→ This concept of a circularly linked trie structure is similar to the concept of a threaded binary tree. This structure will be called a circularly threaded trie.
Question 227 
Ω(logn)  
Ω(nlogn)  
Ω(n)  
Ω(n^{2}) 
Question 228 
f(int Y[10], int x)
{
int u,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k]
else
j=k;
}
while((Y[k]!=x) && (i
printf("x is in the array");
else
printf("x is not in the array");
}
On which of the following contents of 'Y' and 'x' does the program fail?
Y is [1 2 3 4 5 6 7 8 9 10] and x<10  
Y is [1 3 5 7 9 11 13 15 17 19] and x<1  
Y is [ 2 2 2 2 2 2 2 2 2 2] and x>2  
Y is [ 2 4 6 8 10 12 14 16 18 20] and 2 
First iteration:
I=0,j=9
K=(0+9)/2=4
Elements with duplicate values of “2” the condition if(Y[k]
I=0, j=k=4
K= (0+4)/2=2.
Third iteration:
I=0, j=k=2
K= (0+2)/2=1
Fourth iteration:
I=0, j=k=1
K= (0+1)/2=0
The while condition is Y[k] != x && i < j is true
● The above program doesn’t work for the cases where element to be searched is the last element of Y[ ] or greater than the last element (or maximum element) in Y[ ].
● For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j.
● So while condition never becomes false.
Question 229 
max(f(n),g(n))  
min(f(n),g(n))  
f(n)+g(n)  
f(n) * g(n) 
f(n) is order of M1
g(n) is order of M2.
In order to find the order of the algorithm, there are three possible cases with f(n) and g(n)
Case1 : if f(n) > g(n)
In this case we take O(f(n)) the complexity of the algorithm as g(n) is a lower order term, we can ignore this one .
Case2 : f(n) < g(n)
In this case we take O(g(n)) the complexity of the algorithm as f(n) is a lower order term, we can ignore this one.
Case3: f(n) = g(n)
Time Complexity can be either O(g(n)) or O(f(n)) (which is equal asymptotically). So the order of the algorithm is max(f(n), g(n)).
Question 230 
Which of the following greedy strategies gives the optimal solution for the following 01 knapsack problem?
w=30, w1=10, p1=11, w2=15, p2=12, w3=20, p3=24, w4=25, p4=25
Largest profit per unit weight first
 
Largest profit first
 
Lightest item first
 
Heaviest item first

Note: Even though they are asking 0/1 knapsack. We are always takes first profit/weight first.
→ W=30, we can exceed weight and we can’t take fractions of weight.
→ According to profit/weight, W3 having more profit. And W1 having more profit.
→ 0/1 knapsack optimal solution = 24+11 = 35
Question 231 
Which of the following is the time complexity to find the determinant of an upper triangular matrix of order n*n?
Θ(n^{2.5})  
Θ(n)  
Θ(n^{2})
 
Θ(n) 
Question 232 
Greedy  
Dynamic  
Divide and conquer  
Backtracking 
→ Dijkstra’s algorithm is best example for greedy
→ Floyd warshall is best example for dynamic programming.
→ Quicksort is best example for divide and conquer.
Question 233 
Divide and conquer  
Backtracking  
Heuristic approach  
Greedy approach 
→ The solutions to the subproblems are then combined to give a solution to the original problem.
→ So Merge Sort first divides the array into equal halves and then combines them in a sorted manner.
Question 234 
m*n  
minimum of m,n  
Maximum of m,n  
M+n1 
→ Since we need to merge 2 at a time, the optimal strategy would be to take smallest size lists first.
→ The reason for picking smallest two items is to carry minimum items for repetition in merging.
Question 235 
Bubble sort and Insertion sort  
Bubble sort and Quicksort  
Bubble sort and merge sort  
Quicksort and merge sort 
The quick sort and merge sort algorithms are based on the divide and conquer algorithm which works in the quite similar way.
In the both algorithm, the larger problem is divided into smaller one until you find the solution later we will combine all smaller solutions into final solution.
Question 236 
int IsPrime(n)
{
int i,n;
for(i=2;i<= √n;i++)
if(n%i == 0)
{
printf(“Not Prime\n”);
return 0;
}
return 1;
}
Let T(n) denotes the number of times the for loop is executed by the program on input n.
Which of the following is TRUE?
T(n) = O( √n) and T(n) = Ω ( √n)  
T(n) = O( √n) and T(n) = Ω (1)  
T(n) = O(n) and T(n) = Ω ( √n)  
None of the above 
Question 237 
A) Dijkstra's algorithm
B) Floyd's algorithm
C) prim's algorithm
D) Warshall's algorithm
Both A and B  
Both A and C  
Both C and D  
Both B and D 
Question 238 
max(f(n),g(n))  
min(f(n),g(n))  
f(n)+g(n)  
f(n) * g(n) 
So, we will prefer max(f(n),g(n)).
Question 239 
T(n)=8T(n/2)+qn, if n>1
=p, if n=1
Where p,q are constants. The order of this algorithm is
n^{ 2}  
n^{ n}  
n ^{3}  
N 
Case1: a>b^{k}
Here, a=8,b=2,k=1,p=0
O(n(log _{2} 8))=O(n(log _{2} 2 ^{3} ))=O(n ^{3} (log_{ 2} 2)) [ log_{ 2} 2=1]
=O(n ^{3} )
Question 240 
Consider an array with n elements. Which of the following options gives the maximum number of swap(a_{j}, a_{j+1}) operations to sort the array elements using efficient bubble sort algorithm?
n^{2} /2  
n(n1)/2  
n^{2}
 
n(n+1)/2 
→ This means that in the first iteration it would have to look at n elements, then after that it would look n  1 elements (since the biggest integer is at the end) and so on and so forth till 1 comparison occurs.
→ For n number of numbers, total number of comparisons done will be (n1)+ ... + 2 + 1.
= (n*(n1))/2
= O(n^{2})
Question 241 
f(int Y[10], int x)
{
int u,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k]
else
j=k;
}while((Y[k]!=x) && (i
printf("x is in the array");
else
printf("x is not in the array");
}
On which of the following contents of 'Y' and 'x' does the program fail?
Y is [1 2 3 4 5 6 7 8 9 10] and x<10  
Y is [1 3 5 7 9 11 13 15 17 19] and x<1  
Y is [ 2 2 2 2 2 2 2 2 2 2] and x>2  
Y is [ 2 4 6 8 10 12 14 16 18 20] and 2 
First iteration:
I=0,j=9
K=(0+9)/2=4
Elements with duplicate values of “2” the condition if(Y[k]
I=0, j=k=4
K= (0+4)/2=2.
Third iteration:
I=0, j=k=2
K= (0+2)/2=1
Fourth iteration:
I=0, j=k=1
K= (0+1)/2=0
The while condition is Y[k] != x && i < j is true
→ The above program doesn’t work for the cases where element to be searched is the last element of Y[ ] or greater than the last element (or maximum element) in Y[ ].
→ For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j.
So, while condition never becomes false.
Question 242 
Linear search  
Hash search  
Binary search  
All of these 
→ Binary search in which elements should be in sorting order and every time we will search in the half the elements based upon the mid value.
Question 243 
A process of rearranging a given set of objects in a specific order  
To facilitate the later search for members of the sorted set  
Is a relevant and essential activity, particularly in data processing  
All of these 
● ordering: arranging items in a sequence ordered by some criterion;
● categorizing: grouping items with similar properties.
The most common uses of sorted sequences are:
● making lookup or search efficient;
● making merging of sequences efficient.
● enable processing of data in a defined order.
Question 244 
Bubble  
Shake  
Tree  
Insertion 
Question 245 
Knight's tour  
Eight Queens problem  
Kings problem  
Rooks problem 
● The eight queens puzzle is an example of the more general n queens problem of placing n nonattacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n=2 and n=3
Question 246 
Insertion sort  
Heap sort  
Merge sort  
Bubble sort 
1. Mergesort
2. Quicksort.
Question 247 
For the recurrence relation T(n) = 2 + T(n  1), where T(0)=2, T(n)=?
n^{2}
 
2n+2  
log(n)  
2^{n} 
T(0) = 1
T(n1) = T(n11)+1
T(n) = [T(n2)+1] +1 = T(n2)+ 2
T(n2) = T(n21)+1
T(n) = [T(n3)+1]+1
= T(n3)+3
= T(n) = T(nk)+ k
Note: Let k = n
Then T(n) = T(0) + n = 1 + n
∴ O(n)
Question 248 
Travelling salesperson problem belongs to which category of problems?
Satisfiable
 
Non Solvable
 
Decision  
Optimization

Question 249 
O(nlogn)  
O(n)  
O(logn)  
O(n*n) 
→ So, it takes time complexity O(n)
Question 250 
2  
10  
8  
5 
Sep2: The maximum number of comparisons for a particular record among 32 sorted recorder through binary search method will be O(log _{2} 32)=5
Question 251 
floor ((i+1)/2)  
ceiling ((i+1)/2)  
floor (i/2)  
ceiling (i/2) 
Left Child is at index: 2i
Right child is at index: 2*i+1
Question 252 
3  
4  
5  
6 
Height of the binary search tree = 3
Question 253 
Every minimum spanning tree of G must contain E_{ min}.  
If E _{max} is in minimum spanning tree, then its removal must disconnect G.  
No minimum spanning tree contains E_{ max}.  
G has a unique minimum spanning tree. 
Minimum Spanning Tree:
Question 254 
O(n log n)  
O(n ^{2} log n)  
O(n ^{2} + log n)  
O(n ^{3} ) 
2.The length of the string is n, the time taken is to be O(n) for each comparison.
3. For level 1(bottomup order): Every element has to be compared with other element the number of comparisons is O(n/2).
4. For level 1(bottomup order): Total time taken by one level is O(n ^{2} ).
5. For copying level to level the time taken by O(n ^{2} ).
So, For level 1= O(n^{ 2} )+ O(n^{ 2} )
6. Second level O(n ^{2} )+ O(n ^{2} ).
;
;
;
Final n level (logn)*O(n ^{2} ) = O(n ^{2} logn)
Question 255 
Stage (i) 12,3,40,2
Stage (ii) 12,3,2,40
Stage (iii) 3,12,2,40
Stage (iv) 3,2,12,40
Stage (v) 2,3,12,40
The array has been sorted using
Insertion sort  
Selection sort  
Quick sort  
Bubble sort 
→The above stages Bubble sort First Pass/ iteration steps.
→In the bubble sort, after completion the largest element gets last position.
Question 256 
2*log_{2} n  
log_{2} 2n  
log_{2} (2n+1)  
2*log_{2} n+1 
Question 257 
3, 4, 5, 7, 9, 14, 20, 18, 17, 16, 15  
20, 18, 17, 16, 15, 14, 3, 4, 5, 7, 9
 
20, 18, 17, 16, 15, 14, 9, 7, 5, 4, 3  
3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20 
Question 258 
↔~∧pq∨ ~ ~ pq, pq∧~p~q~∨↔  
↔~∧pq∨ ~ p~q, pq∧~p~q~∨↔  
↔~∧pq∨ ~ ~ pq, pq∧~p~~q∨↔  
↔~∧pq∨ ~ p~ q, pq∧~p~ ~q∨↔ 
(~(p ∧ q))↔(~ p ∨ ~ q)
It is clearly specifying that
↔ is a root
(~(p ∧ q)) is left subtree
(~p ∨ ~q) is right subtree.
Step2: Finally the tree is looks like
Step3: Prefix operation traverse through Root,left and Right ↔~∧pq∨ ~ p~q Step4: Postfix operation traverse through Left,Right and Root.
pq∧~p~q~∨↔
Question 259 
O(lg n)  
O(n lg n)  
O(n)  
O(n ^{2} ) 
→ Traversing all the nodes of a binary search tree with n nodes and printing them in order using inorder traversal.
→ Inorder traversal will print all elements in sorted order. It takes worst case time complexity is O(n).
Possibility2:
Without sorted elements chance to form either left skewed or right skewed tree. It takes worst case time complexity is O(n).
Question 260 
Both time and space complexities are better in recursive than in nonrecursive program.  
Both time and space complexities are better in nonrecursive than in recursive program  
Time complexity is better in recursive version but space complexity is better in nonrecursive version of the program.  
Space complexity is better in recursive version but time complexity is better in nonrecursive version of the program. 
→ Recursion uses more memory, but is sometimes clearer and more readable. Using loops increases the performance, but recursion can sometimes be better for the programmer (and his performance). Depends on what we you want to implement, and what's more important for you (readability, performance...)
Example: Factorial of a number.
Question 261 
It shows which of the following depth first forest?
{a, b, e} {c, d, f, g, h}  
{a, b, e} {c, d, h} {f, g}  
{a, b, e} {f, g} {c, d} {h}  
{a, b, c, d} {e, f, g} {h} 
Based on definition of DFS forest, optionA is correct.
Question 262 
O (log _{2} n)  
O (n log _{2} n)  
O (1)  
O (n) 
1. Stable: Equal keys aren't reordered.
2. Operates in place, requiring O(1) extra space.
3. Worst case O(nlog(n)) key comparisons.
4. Worst case O(n) swaps.
5. Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys.
Question 263 
According to kruskal’s algorithm, first we have sort an elements.
Elements are: 10,12,14,16,18,22,24,25,28
Question 264 
The item to be searched is in somewhere middle of the array  
The item to be searched is not in the array  
The item to be searched is in the last of the array  
The item to be searched is either in the last or not in the array 
→ A linear search runs in at worst linear time and makes at most n comparisons, where ‘n’ is the length of the list. If each element is equally likely to be searched, then linear search has an average case of n/2 comparisons, but the average case can be affected if the search probabilities for each element vary. → Linear search is rarely practical because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching for all but short lists.
Question 265 
Counting microseconds  
Counting number of key operations  
Counting number of statements  
Counting kilobytes of algorithm 
Question 266 
Selection sort  
Bubble sort  
Radix sort  
Insertion sort 
Phase 1:
1. We use n bins, one for each of the integers 0,1,.., n1. We place each integer i on the list to be sorted into the bin numbered (i mod n) each bin will then contain a list of integers leaving the same remainder when divided by n.
At the end, we concatenate the bins in order to obtain a list L.
Phase 2:
1. The integers on the list L are redistributed into bins, but using the bin selection
function: ⌊i/n⌋
2. Now append integers to the ends of lists. Finally, concatenate the lists to get the final sorted sequence.
Question 267 
O(1)  
O(Log n)  
O(n)  
O(n ^{2} ) 
→ The heapify function does not take O(logn) space, it will take O(logn) time in worst case. Here we don't do heapify through any recursion call. We will do through iterative method and we don't require any auxiliary space in this sorting. We use only input array.
So, we do heap sort in O(1) space complexity.
Question 268 
Binary search  
Maximum of n number  
Quick sort  
Fibonacci search 
Question 269 
Bubble sort  
Selection sort  
Quick sort  
Insertion sort 
So, we can eliminate optionB and OptionC because it gives worst complexity(O(n 2 )) when array is already sorted.
Bubble sort and insertion sort will give best case complexity(O(n)) but here they given small constraint is “there are few random elements”. So, insertion sort is more appropriate answer.
Question 270 
b= branch factor
d= depth of shallowest solution
M= Maximum depth of the search tree
I= depth limit
(a)(iii), (b)(ii), (c)(iv), (d)(i)  
(a)(ii), (b)(iii), (c)(iv), (d)(i)  
(a)(i), (b)(ii), (c)(iv), (d)(iii)  
(a)(i), (b)(iii), (c)(iv), (d)(ii) 
DFS → O(bm) worst case space complexity
Depth Limited Search → O(bl)
Iterative deepening Search → O(bd)
Note: Based upon BFS and DFS we can find the solution.
Question 271 
(a)(iv), (b)(iii), (c) (ii), (d)(i)  
(a)(i), (b)(iv), (c) (iii), (d)(ii)  
(a)(iv), (b)(i), (c) (ii), (d)(iii)  
(a)(i), (b)(ii), (c) (iii), (d)(iv) 
→ A* Search: Time complexity depends upon the quality of heuristic.
→ Recursive BestFirst Search: Suffers from excessive node generation. RBFS depends on how widely the promising nodes are separated in the search tree, and is harder to anticipate.
→ Iterativedeepening A* Search: Avoids substantial overhead associated with keeping the sorted queue of nodes
Question 272 
11  
12  
10  
9 
Number of leaf nodes = Sum of degrees of all internal nodes  number of internal nodes +1
= (4*1 + 3*2 + 3*3 )10 +1
= 19 10 +1=10
Formula : ndn +1 where n is number of nodes and d is degree of the tree.
Question 273 
Use Kruskal’s algorithm to find the minimum spanning tree of the graph. The weight of this minimum spanning tree is
13  
16  
17  
14 
The weight of this minimum spanning tree is 16.
Question 274 
O(n!) and O(n log n)  
O(n^{n}) and O(n log n)  
O(n!) and O(log n!)  
O(n^{n}) and O(log n!) 
→ Given logarithm of the factorial function log n!.
= log n! (or)
= log n^{n} (or)
= nlogn
When we are writing into asymptotic order also the value remains same O(nlogn).
Question 275 
n + ceil(lg n) 2  
n1  
lg n  
3n/1 
This takes n1 comparisons and each element involved is compared at most log n times. Finally, we get the largest element A1’’’ . This element which is largest, has won comparison with the second largest element at some point. So, keeping track of items compared with the largest element will give us a list of (log n) elements. In this list we find out largest, which will be the second largest of all.
So, no. of comparisons =(n1)+log _{2} (n)1
Example: 512 elements
In this case no. of comparisons will be, (5121)+log _{2} (512) 1
=511+(91)
=511+8
=519
Question 276 
X = <0,1,2,1,3,0,1 >
Y = <1,3,2,0,1,0 >
The length of longest common subsequence between X and Y is
4  
2  
3  
5 
Possible subsequences are :130, 1210, 1301 and length of longest common subsequence is 4.
Question 277 
(1) Input (x _{1} ,y_{ 1} ) and (x_{ 2} ,y_{ 2} )
(2) y=y_{ 1}
(3) d=f(x _{1} +1, y _{1} +1⁄2) // f is the implicit form of a line
(4) for x=x_{ 1} to x_{ 2}
(5) do
(6) plot(x,y)
(7) if(d<0)
(8) then
(9) y=y+1
(10) d=d+(y_{ 1}  y _{2} ) + (x_{ 2}  x_{ 1} )
(11) else
(12) d=d+(y_{ 1}  y_{ 2} )
(13) end
(14) end
Which statements are true ?
P: For a line with slope m>1, we should change the outer loop in line (4) to be over y.
Q: Lines (10) and (12) update the decision variable d through an incremental evaluation of the line equation f.
R: The algorithm fails if d is ever 0.
Q and R only  
P only  