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 __________.
A  225 
B  226 
C  227 
D  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)
A  19 
B  39 
C  29 
D  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 _____.
A  0.08 
B  0.01 
C  1 
D  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
A  O(n) 
B  O(n log n) 
C  Ω(n^{2} log n) 
D  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 
I. G has a unique minimum spanning tree, if no two edges of G have the same weight.
II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimumweight edge crossing the cut.
Which of the above statements is/are TRUE?
A  I only 
B  II only 
C  Both I and II 
D  Neither I nor II 
I. TRUE: G Graph is unique, no two edges of the graph is same.
Step1: Using Kruskal’s algorithm, arrange each weights in ascending order.
17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Step2:
Step3: 17 + 18 + 20 + 21 + 22 + 23 + 26 = 147
Step4: Here, all the elements are distinct. So, the possible MCST is 1.
II. TRUE: As per the above graph, if we are cut the edge, that should the be the minimum edge.
Because we are already given, all minimum edge weights if graph is distinct.
Question 6 
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 _________.
A  4 
B  5 
C  6 
D  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 7 
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 ______ .
A  16 
B  17 
C  18 
D  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 8 
Consider the following functions from positives integers to real numbers
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
A  
B  
C  
D 
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 9 
Consider the following table
Match the algorithm to design paradigms they are based on:
A  (P)↔(ii), Q↔(iii), (R)↔(i) 
B  (P)↔(iii), Q↔(i), (R)↔(ii) 
C  (P)↔(ii), Q↔(i), (R)↔(iii) 
D  (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 10 
(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?
A  (I) only 
B  (II) only 
C  both (I) and (II) 
D  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 11 
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 _________.
A  5 
B  6 
C  7 
D  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 12 
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)
A  P→(iii), Q→(iv), R→(i), S→(ii) 
B  P→(iv), Q→(iii), R→(i), S→(ii) 
C  P→(iii), Q→(iv), R→(ii), S→(i) 
D  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 13 
Consider the recurrence function
Then T(n) in terms of Θ notation is
A  Θ(loglogn) 
B  Θ(logn) 
C  Θ(√n) 
D  Θ(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 14 
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
A  Θ(n√n) 
B  Θ(n^{2}) 
C  Θ(n logn) 
D  Θ(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 15 
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
A  Θ(nlogn), Θ(nlogn), and Θ(n^{2}) 
B  Θ(n^{2} ), Θ(n^{2} ), and Θ(nlogn) 
C  Θ(n^{2}), Θ(nlogn), and Θ(nlogn) 
D  Θ(n^{2}), Θ(nlogn), and Θ(n^{2}) 
Question 16 
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 __________.
A  7 
B  8 
C  9 
D  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 17 
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
A  I only 
B  II only 
C  both I and II 
D  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 18 
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
A  I and II only 
B  I and III only 
C  II and IV only 
D  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 19 
The FloydWarshall algorithm for allpair shortest paths computation is based on
A  Greedy paradigm. 
B  DivideandConquer paradigm. 
C  Dynamic Programming paradigm. 
D  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 20 
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 _________.
A  1500 
B  1501 
C  1502 
D  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 21 
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 _________.
A  2.3219280 
B  2.3219281 
C  2.3219282 
D  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 22 
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.
A  T(n) = 2T(n/2) + cn 
B  T(n) = T(n – 1) + T(1) + cn 
C  T(n) = 2T(n – 1) + cn 
D  T(n) = T(n/2) + cn

Hence recurrence relation T(n) = T(n – 1) + T(1) + cn.
Question 23 
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
A  Piii, Qii, Riv, Si 
B  Pi, Qii, Riv, Siii 
C  Pii, Qiii, Riv, Si 
D  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 24 
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?
A  Unsorted array 
B  Minheap 
C  Sorted array 
D  Sorted doubly linked list 
Question 25 
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 ______________.
A  69 
B  70 
C  71 
D  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 26 
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:
A  1i, 2iii, 3i, 4v. 
B  1iii, 2iii, 3i, 4v. 
C  1iii, 2ii, 3i, 4iv. 
D  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 27 
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  (a, left_end, k) and (a + left_end + 1, n – left_end – 1, k – left_end – 1)

B  (a, left_end, k) and (a, n – left_end – 1, k – left_end – 1) 
C  (a + left_end + 1, n – left_end – 1, k – left_end – 1) and (a, left_end, k) 
D  (a, n – left_end – 1, k – left_end – 1) and (a, left_end, k) 
Question 28 
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 _____________.
A  6 
B  6.1 
C  6.2 
D  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 29 
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?
A  256 
B  512 
C  1024 
D  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 30 
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 __________.
A  995 
B  996 
C  997 
D  998 
Question 31 
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 _______.
A  12 
B  13 
C  14 
D  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 32 
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)?
A  
B  
C  
D 
Question 33 
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is __________.
A  148 
B  149 
C  150 
D  151 
(∵ T(n) = T(floor(n/2))+T(ceil(n/2))+2)
Question 34 
Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?
T(n) = 2T(n/2) + Logn
A  Θ(n) 
B  Θ(nlog n) 
C  Θ(n^{2}) 
D  Θ(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 35 
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 = _________.
A  34 
B  35 
C  36 
D  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 36 
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 ______.
A  358 
B  359 
C  360 
D  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 37 
The number of distinct minimum spanning trees for the weighted graph below is _______.
A  6 
B  7 
C  8 
D  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 38 
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
A  SQPTRWUV 
B  SQPTUWRV 
C  SQPTWUVR 
D  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 39 
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 _________.
A  19 
B  20 
C  21 
D  22 
Note: We should not consider backtrack edges, it reduces recursion depth in stack.
So the maximum possible recursive depth will be 19.
Question 40 
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
A  O(n^{2}) 
B  O(n log n) 
C  Θ(n logn) 
D  O(n^{3}) 
Question 41 
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 ____.
A  110 
B  111 
C  112 
D  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 42 
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?
A  (97×97×97)/100^{3} 
B  (99×98×97)/100^{3} 
C  (97×96×95)/100^{3} 
D  (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 43 
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
A  number of internal nodes in the tree. 
B  height of the tree. 
C  number of nodes without a right sibling in the tree. 
D  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 44 
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?
A  It will run into an infinite loop when x is not in listA. 
B  It is an implementation of binary search. 
C  It will always find the maximum element in listA. 
D  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 45 
Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
A  O(log n) 
B  O(n) 
C  O(n log n) 
D  O(n^{2}) 
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 46 
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?
A  O(1) 
B  O(log n) 
C  O(n) 
D  O(n log n) 
Question 47 
Consider the languages L_{1} = ϕ and L_{2 }= {a}. Which one of the following represents L_{1}L_{2}* ∪ L_{1}*?
A  {є} 
B  ϕ 
C  a* 
D  {є,a} 
Rϕ = ϕR = ϕ
So L_{1} L_{2} * = ϕ
and L_{1} * = {ϕ}* = {ϵ}
So L_{1}L_{2}* ∪ L_{1}* = {ϵ}
Question 48 
What is the time complexity of BellmanFord singlesource shortest path algorithm on a complete graph of n vertices?
A  Θ(n^{2}) 
B  Θ(n^{2} log n) 
C  Θ(n^{3}) 
D  Θ(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 49 
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?
A  1/8 
B  1 
C  7 
D  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 50 
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.
A  P only 
B  Q only 
C  Both P and Q 
D  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.