Algorithms
Question 1 |
4 | |
5 | |
6 | |
7 |
Question 1 Explanation:
Here, X=5 because it is having maximum number of spanning trees. 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
If r = 2
If r = 3
If r = 4
If r = 5
Question 2 |
16 | |
17 | |
18 | |
19 |
Question 2 Explanation:
First sort value/weight in descending order as per the question:
Vopt is clearly = 60
For Vgreedy 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 Vgreedy = 44
∴ Vopt –Vgreedy = 60 – 44 = 16
Vopt is clearly = 60
For Vgreedy 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 Vgreedy = 44
∴ Vopt –Vgreedy = 60 – 44 = 16
Question 3 |
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 |
Question 3 Explanation:
→ If we apply binary search to find the first occurrence of 1 in the list, it will give us the smallest index i where 1 is stored.
→ 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(log2 31) = 4.954196310386876 ⇒ here we are using ceiling so it becomes 5
→ 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(log2 31) = 4.954196310386876 ⇒ here we are using ceiling so it becomes 5
Question 4 |
 | |
 | |
 | |
 |
Question 4 Explanation:
In this problem, they are expecting to find us “increasing order of asymptotic complexity”.
Step-1: Take n=2048 or 211 (Always take n is very big number)
Step-2: Divide functions into 2 ways
1. Polynomial functions
2. Exponential functions
Step-3: 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
→ log2 2048 =11
→ √n = 45.25483399593904156165403917471
→ n = 2048
So, Option B is correct
Step-1: Take n=2048 or 211 (Always take n is very big number)
Step-2: Divide functions into 2 ways
1. Polynomial functions
2. Exponential functions
Step-3: 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
→ log2 2048 =11
→ √n = 45.25483399593904156165403917471
→ n = 2048
So, Option B is correct
Question 5 |
(P)↔(ii), Q↔(iii), (R)↔(i) | |
(P)↔(iii), Q↔(i), (R)↔(ii) | |
(P)↔(ii), Q↔(i), (R)↔(iii) | |
(P)↔(i), Q↔(ii), (R)↔(iii) |
Question 5 Explanation:
(P) Kruskal’s and Prim’s algorithms for finding Minimum Spanning Tree(MST). To find MST we are using greedy technique.
(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..,
(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 6 |
(I) only | |
(II) only | |
both (I) and (II) | |
neither (I) nor (II) |
Question 6 Explanation:
If the graph has all positive and distinct (unique values no duplicates) then Statement -I definitely correct because if we are using either prim’s or kruskal’s algorithm it gives the unique spanning tree. 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.
Statement-II: 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.
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.
Statement-II: 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 7 |
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) |
Question 7 Explanation:
In this problem, we have to find Average case of different algorithms
→ Tower of Hanoi with n disks takes θ(2n) 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 2n-1, where n is the number of disks.
→ Binary Search given n sorted numbers takes Ɵ(log2 n)
→ Heap sort given n numbers of the worst case takes Ɵ(n log n)
→ Addition of two n×n matrices takes Ɵ(n2)
→ Tower of Hanoi with n disks takes θ(2n) 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 2n-1, where n is the number of disks.
→ Binary Search given n sorted numbers takes Ɵ(log2 n)
→ Heap sort given n numbers of the worst case takes Ɵ(n log n)
→ Addition of two n×n matrices takes Ɵ(n2)
Question 8 |
Θ(loglogn) | |
Θ(logn) | |
Θ(√n) | |
Θ(n) |
Question 8 Explanation:
T(n)=2T(√n)+1
(or)
T(n)=2T(n(1⁄2) )+1
Here Assume n=2k
T(2k )=2T(2k )(1⁄2)+1
T(2k )=2T(2(k/2) )+1
Assume T(2k )=S(k)
S(k)=2S(k/2)+1
Apply Master’s theorem Case-1
a=2,b=2
S(k)=k(log22 )
S(k)=θ(k')
but S(k)=T(2k)
T(2k)=θ(k')
but n=2k
k=logn
T(n)=θ(logn)
(or)
T(n)=2T(n(1⁄2) )+1
Here Assume n=2k
T(2k )=2T(2k )(1⁄2)+1
T(2k )=2T(2(k/2) )+1
Assume T(2k )=S(k)
S(k)=2S(k/2)+1
Apply Master’s theorem Case-1
a=2,b=2
S(k)=k(log22 )
S(k)=θ(k')
but S(k)=T(2k)
T(2k)=θ(k')
but n=2k
k=logn
T(n)=θ(logn)
Question 9 |
Θ(n√n) | |
Θ(n2 ) | |
Θ(n logn) | |
Θ(n2 logn) |
Question 9 Explanation:
We can solve iterative programs time complexity with the help of rollback method.
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.
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 10 |
225 | |
226 | |
227 | |
228 |
Question 10 Explanation:
General procedure to solve Huffman coding problem
Step-1: Arrange into either descending/ ascending order according to that profits.
Step-2: Apply optimal merge pattern procedure.
Step-3: Make left sub-tree value either 0 or 1, for right sub-tree, vice-versa.
=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 11 |
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
Θ(nlogn),Θ(nlogn),and Θ(n2) | |
Θ(n2 ),Θ(n2 ),and Θ(nlogn) | |
Θ(n2),Θ(nlogn),and Θ(nlogn) | |
Θ(n2),Θ(nlogn),and Θ(n2) |
Question 11 Explanation:
Question 12 |
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 |
Question 12 Explanation:
Let G be a complete undirected graph with 4 vertices & 6 edges so according to graph theory, if we use Prim’s / Kruskal’s algorithm, the graph looks like
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.
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 13 |
I only | |
II only | |
both I and II | |
neither I nor II |
Question 13 Explanation:
Statement-1: False
The MSTs of G may or may not include the lightest edge. Take rectangular graph labelled with P,Q,R,S. Connect with P-Q=5, Q-R=6, R-S=8, S-P=9, P-R=7. When we are forming a cycle R-S-P-R. P-R is the lightest edge of the cycle. The MST abcd with cost 11 P-Q + Q-R + R-S does not include it.
Statement-2: 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
The MSTs of G may or may not include the lightest edge. Take rectangular graph labelled with P,Q,R,S. Connect with P-Q=5, Q-R=6, R-S=8, S-P=9, P-R=7. When we are forming a cycle R-S-P-R. P-R is the lightest edge of the cycle. The MST abcd with cost 11 P-Q + Q-R + R-S does not include it.
Statement-2: 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 14 |
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
Greedy paradigm. | |
Divide-and-Conquer paradigm. | |
Dynamic Programming paradigm. | |
Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm. |
Question 14 Explanation:
→ All Pair shortest path algorithm is using Dynamic Programming technique. 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.
→ 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 15 |
I and II only | |
I and III only | |
II and IV only | |
I and IV only |
Question 15 Explanation:
If input sequence is already sorted then the time complexity of Quick sort will take O(n2) and Bubble sort will take O(n) and Merge sort will takes O(nlogn) and insertion sort will takes O(n).
→ The recurrence relation for Quicksort, if elements are already sorted, T(n) = T(n-1)+O(n) with the help of substitution method it will take O(n2).
→ 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.
→ The recurrence relation for Quicksort, if elements are already sorted, T(n) = T(n-1)+O(n) with the help of substitution method it will take O(n2).
→ 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 16 |
Let A1, A2, A3 and A4 be four matrices of dimensions 10 × 5, 5 × 20, 20 × 10, and 10 × 5, respectively. The minimum number of scalar multiplications required to find the product A1 A2 A3 A4 using the basic matrix multiplication method is _________.
1500 | |
1501 | |
1502 | |
1503 |
Question 16 Explanation:
→ The minimum number of scalar multiplications required is 1500. The optimal parenthesized sequence is A1((A2A3)A4) out of many possibilities, the possibilities are
1. ((A1A2)A3)A4
2. ((A1(A2A3))A4)
3. (A1A2)(A3A4)
4. A1((A2A3)A4)
5. A1(A2(A3A4)).
→ A1((A2A3)A4) = (5 x 20 x 10) + (5 x 10 x 5) + (10 x 5 x 5) = 1000 + 250 + 250 = 1500
1. ((A1A2)A3)A4
2. ((A1(A2A3))A4)
3. (A1A2)(A3A4)
4. A1((A2A3)A4)
5. A1(A2(A3A4)).
→ A1((A2A3)A4) = (5 x 20 x 10) + (5 x 10 x 5) + (10 x 5 x 5) = 1000 + 250 + 250 = 1500
Question 17 |
2.3219280 | |
2.3219281 | |
2.3219282 | |
2.3219283 |
Question 17 Explanation:
This type of problem, we have to consider worst case time complexity, it mean that all possibilities. 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>bk case
A(n)=n(logba )=n(log25 )=n2.3219280
∴α=2.3219280
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>bk case
A(n)=n(logba )=n(log25 )=n2.3219280
∴α=2.3219280
Question 18 |
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 – 2) + cn
| |
T(n) = T(n/2) + cn
|
Question 18 Explanation:
When the pivot is the smallest (or largest) element at partitioning on a block of size n the result yields one empty sub-block, one element (pivot) in the correct place and sub block of size n-1. Hence recurrence relation T(n) = T(n-1)+T(1) + cn.
Question 19 |
P-iii, Q-ii, R-iv, S-i
| |
P-i, Q-ii, R-iv, S-iii
| |
P-ii, Q-iii, R-iv, S-i | |
P-ii, Q-i, R-iii, S-iv |
Question 19 Explanation:
Prim’s algorithm always select minimum distance between two of its sets which is nothing but greedy method.
Floyd-warshall 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.
Floyd-warshall 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 20 |
An algorithm performs (log N)1/2 find operations, N insert operations, (log N)1/2 delete operations, and (log N)1/2 decrease-key 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 decrease-key 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 | |
Min-heap | |
Sorted array | |
Sorted doubly linked list |
Question 20 Explanation:
Question 21 |
69 | |
70 | |
71 | |
72 |
Question 21 Explanation:
⇒ Total sum = 10 + 9 + 2 + 15 + 7 + 16 + 4 + 6 = 69
Question 22 |
1-i, 2-iii, 3-i, 4-v. | |
1-iii, 2-iii, 3-i, 4-v. | |
1-iii, 2-ii, 3-i, 4-iv. | |
1-iii, 2-ii, 3-i, 4-v. |
Question 22 Explanation:
(1) Dijkstra’s Shortest Path using to find single source shortest path. It is purely based on Greedy technique because it always selects shortest path among all.
(2) → All Pair shortest path algorithm is using Dynamic Programming technique. 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.
(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 Depth-first search
(2) → All Pair shortest path algorithm is using Dynamic Programming technique. 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.
(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 Depth-first search
Question 23 |
(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 24 |
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 512-byte sector of the disk is _____________.
6 | |
6.1 | |
6.2 | |
6.3 |
Question 24 Explanation:
15000 rotations → 60 sec
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 × 106B ------- 1s
512 B ------- 512B/ 50×106B/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
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 × 106B ------- 1s
512 B ------- 512B/ 50×106B/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 25 |
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 |
Question 25 Explanation:
Time complexity of merge sort = O(n log n) = an log n
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 = 29 × 9
So for n = 29, it satisfies.
So, n = 29 = 512
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 = 29 × 9
So for n = 29, it satisfies.
So, n = 29 = 512
Question 26 |
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 26 Explanation:
G has 100 vertices ⇒ spanning tree contain 99 edges given, weight of a minimum spanning tree of G is 500 since, each edge of G is increased by five.
∴ Weight of a minimum spanning tree becomes 500 + 5 ⨯ 99= 995
Question 27 |
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 |
Question 27 Explanation:
Bags: 1 2 3 4 5
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
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 28 |
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 28 Explanation:
The most important open question in complexity theory is whether the P = NP, which asks whether polynomial time algorithms actually exist for NP-complete and all NP problems (since a problem “C” is in NP-complete, iff C is in NP and every problem in NP is reducible to C in polynomial time). In the given question it is given that some polynomial time algorithm exists which computes the largest clique problem in the given graph which is known NP-complete problem. Hence P=NP=NP-Complete.
Question 29 |
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.
148 | |
149 | |
150 | |
151 |
Question 29 Explanation:
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is 3n/2 – 2 = 148. (∵ T(n) = T(floor(n/2))+T(ceil(n/2))+2)
Question 30 |
Θ(n) | |
Θ(nlog n) | |
Θ(n2) | |
Θ(logn) |
Question 30 Explanation:
T(n)=2T(n/2)+logn
Apply Master’s theorem,
a=2,b=2,k=0,p=1
According to Master’s theorem, we can apply Case-I
(I) If a>bk, then T(n)=θ(n(logba ) ) =θ(n(log22 ) )= θ (n)
Apply Master’s theorem,
a=2,b=2,k=0,p=1
According to Master’s theorem, we can apply Case-I
(I) If a>bk, then T(n)=θ(n(logba ) ) =θ(n(log22 ) )= θ (n)
Question 31 |
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 |
Question 31 Explanation:
Given is
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
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 32 |
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 |
Question 32 Explanation:
The implementation of optimal algorithm for merging sequences is as follows.
In the above implementation, total number of comparisons is
(44-1) + (94-1) + (65-1) + (159-1) = 358
Hint: The number of comparisons for merging two sorted sequences of length m and n is m+n-1.
In the above implementation, total number of comparisons is
(44-1) + (94-1) + (65-1) + (159-1) = 358
Hint: The number of comparisons for merging two sorted sequences of length m and n is m+n-1.
Question 33 |
6 | |
7 | |
8 | |
9 |
Question 33 Explanation:
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 34 |
SQPTRWUV | |
SQPTUWRV | |
SQPTWUVR | |
SQPTRUWV |
Question 34 Explanation:
Inorder Traversal: Left, Root, Middle, Right.
Question 35 |
19 | |
20 | |
21 | |
22 |
Question 35 Explanation:
Note: We should not consider backtrack edges, it reduces recursion depth in stack.
So the maximum possible recursive depth will be 19.
Question 36 |
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(n2) | |
O(n log n) | |
Θ(n logn) | |
O(n3) |
Question 36 Explanation:
The Worst case time complexity of quick sort is O (n2). This will happen when the elements of the input array are already in order (ascending or descending), irrespective of position of pivot element in array.
Question 37 |
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(nalogbn + mclogdn), the value of a + 10b + 100c + 1000d is ____.
110 | |
111 | |
112 | |
113 |
Question 37 Explanation:
It takes (log n) time to determine numbers n1 and n2 in balanced binary search tree T such that
1. n1 is the smallest number greater than or equal to L and there is no predecessor n1' of >n1 such that n1' is equal to n1.
2. n22' of n2 such that is equal to n2.
Since there are m elements between n1 and n2, it takes ‘m’ time to add all elements between n1 and n2.
So time complexity is O(log n+m)
So the given expression becomes O(n0log'n+m'log0n)
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
1. n1 is the smallest number greater than or equal to L and there is no predecessor n1' of >n1 such that n1' is equal to n1.
2. n22' of n2 such that is equal to n2.
Since there are m elements between n1 and n2, it takes ‘m’ time to add all elements between n1 and n2.
So time complexity is O(log n+m)
So the given expression becomes O(n0log'n+m'log0n)
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 38 |
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)/1003 | |
(99×98×97)/1003 | |
(97×96×95)/1003 | |
(97×96×95)/(3!×1003) |
Question 38 Explanation:
Given Hash table consists of 100 slots.
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))⁄1003
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))⁄1003
Question 39 |
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. |
Question 39 Explanation:
The key to solving such questions is to understand or detect where/by what condition the value (or the counter) is getting incremented each time.
Here, that condition is if (tree → leftMostchild = = Null)
⇒ Which means if there is no left most child of the tree (or the sub-tree 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.
Here, that condition is if (tree → leftMostchild = = Null)
⇒ Which means if there is no left most child of the tree (or the sub-tree 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 40 |
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. |
Question 40 Explanation:
From the above code, we can identify
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.
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 41 |
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(n2) |
Question 41 Explanation:
Best, Average and worst case will take maximum O(n) swaps.
Selection sort time complexity O(n2) in terms of number of comparisons. Each of these scans requires one swap for n-1 elements (the final element is already in place).
Selection sort time complexity O(n2) in terms of number of comparisons. Each of these scans requires one swap for n-1 elements (the final element is already in place).
Question 42 |
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 42 Explanation:
For skewed binary search tree on n nodes, the tightest upper bound to insert a node is O(n).
Question 43 |
Consider the languages L1 = ϕ and L2 = {a}. Which one of the following represents L1L2* ∪ L1*?
{є} | |
ϕ | |
a* | |
{є,a} |
Question 43 Explanation:
As we know, for any regular expression R,
Rϕ = ϕR=ϕ
So L1 L2 * = ϕ
and L1 * = {ϕ}* = {ϵ}
So L1L2* ∪ L1* = {ϵ}
Rϕ = ϕR=ϕ
So L1 L2 * = ϕ
and L1 * = {ϕ}* = {ϵ}
So L1L2* ∪ L1* = {ϵ}
Question 44 |
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
Θ(n2) | |
Θ(n2 log n) | |
Θ(n3) | |
Θ(n3 log n) |
Question 44 Explanation:
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is capable of handling graphs in which some of the edge weights are negative numbers.
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(n-1)/2=(n3)
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(n-1)/2=(n3)
Question 45 |
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 |
Question 45 Explanation:
Among available ‘8’ vertices, we need to identify the cycles of length ‘3’.
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 = 8C3 = 56
Total number of cycles of length ‘3’ out of 8 vertices = 56 × 1/8 = 7
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 = 8C3 = 56
Total number of cycles of length ‘3’ out of 8 vertices = 56 × 1/8 = 7
Question 46 |
P only | |
Q only | |
Both P and Q | |
Neither P nor Q |
Question 46 Explanation:
Euler’s Theorem 3:
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.
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 47 |
The number of elements that can be sorted in Θ(log n) time using heap sort is
Θ(1) | |
Θ(√logn) | |
Θ (logn/loglogn) | |
Θ(log n) |
Question 47 Explanation:
Using heap sort to n elements it will take O(n log n) time. Assume there are log n/ log log n elements in the heap.
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.
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 48 |
3024 | |
6561 | |
55440 | |
161051 |
Question 48 Explanation:
Since it is f(p,p)
f(5,5)→f(x,4)*x
f(x,3)*x*x
f(x,2)*x*x*x
⇒x*x*x*x=x4
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=94=6561
f(5,5)→f(x,4)*x
f(x,3)*x*x
f(x,2)*x*x*x
⇒x*x*x*x=x4
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=94=6561
Question 49 |
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 |
Question 49 Explanation:
From the data,
The Postorder traversal sequence is:
→ 15, 10, 23, 25, 20, 35, 42, 39, 30.
Question 50 |
P only | |
P and R only | |
R only | |
P, Q and S only |
Question 50 Explanation:
P) True. Because every edge in cycle graph will become a vertex in new graph L(G) and every vertex of cycle graph will become an edge in new graph.
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| ≤ 3|v| - 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.
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| ≤ 3|v| - 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 |
Θ(n) | |
Θ(n + k) | |
Θ(nk) | |
Θ(n2) |
Question 51 Explanation:
Initially the queue is empty and we have to perform n operations.
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 k-Enqueues, 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).
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 k-Enqueues, 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 52 |
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)) |
Question 52 Explanation:
The average case time can be lesser than or even equal to the worst case.
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)) .
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 53 |
Assuming P ≠ NP, which of the following is TRUE?
NP-complete = NP | |
NP-complete ∩ P = ∅ | |
NP-hard = NP | |
P = NP-complete |
Question 53 Explanation:
Note: Out of syllabus.
The definition of NP-complete is,
A decision problem p is NP-complete 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 NP-complete ∩ P = ∅ .
This is due to the fact that, if NP-complete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NP-complete also, then it means that P1 (NP-complete 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 NP-complete 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.
The definition of NP-complete is,
A decision problem p is NP-complete 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 NP-complete ∩ P = ∅ .
This is due to the fact that, if NP-complete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NP-complete also, then it means that P1 (NP-complete 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 NP-complete 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 54 |
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth 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
|
Question 54 Explanation:
For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot. If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced.
Question 55 |
Q solves the subset-sum problem in polynomial time when the input is encoded in unary
| |
Q solves the subset-sum 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 NP-hard
|
Question 55 Explanation:
Suppose the input is encoded in binary format. If W is an exponential in terms of the input length of W and O(nW) also becomes exponential in terms of the input lengths. Q is not a polynomial time algorithm.
Note: As per Present GATE syllabus , the above concept is not required.
Note: As per Present GATE syllabus , the above concept is not required.
Question 56 |
only vertex a | |
only vertices a, e, f, g, h
| |
only vertices a, b, c, d
| |
all the vertices |
Question 56 Explanation:
The single source shortest path algorithm(Dijkstra’s) is not work correctly for negative edge weights and negative weight cycle. But as per the above graph it works correct. It gives from shortest path between ‘a’ vertex to all other vertex. The Dijkstra’s algorithm will follow greedy strategy.
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
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 57 |
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 |
Question 57 Explanation:
Total element = n
RST contains elements = p
Root contains = 1 element
1st contains = n - (p + 1) element
Root contains the value is n - p.
RST contains elements = p
Root contains = 1 element
1st contains = n - (p + 1) element
Root contains the value is n - p.
Question 58 |
In a depth-first 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 |
Question 58 Explanation:
In a graph G with n vertices and p component then G has n - p edges(k).
In this question, we are going to applying the depth first search traversal on each component of graph where G is conected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n - k
In this question, we are going to applying the depth first search traversal on each component of graph where G is conected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n - k
Question 59 |
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 |
Question 59 Explanation:
Bellman-ford algorithm → O(nm)
Krushkal's algorithm → O(m log n)
Floyd-Warshall algorithm → O(n3)
Topological sorting → O(n+m)
Krushkal's algorithm → O(m log n)
Floyd-Warshall algorithm → O(n3)
Topological sorting → O(n+m)
Question 60 |
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 |
Question 60 Explanation:
43%10 = 3 [occupy 3]
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]
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 61 |
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:
2h-1 | |
2h-1 + 1 | |
2h - 1 | |
2h |
Question 61 Explanation:
Let's take an example,
Above tree satisfies the property given in the question. Hence, only option (B) satisfies it.
Above tree satisfies the property given in the question. Hence, only option (B) satisfies it.
Question 62 |
Merge sort uses
Divide and conquer strategy | |
Backtracking approach | |
Heuristic search | |
Heuristic search |
Question 62 Explanation:
Merge sort uses the divide and conquer strategy.
Question 63 |
For merging two sorted lists of sizes m and n into a sorted list of size m+n, we required comparisons of
O(m) | |
O(n) | |
O(m+n) | |
O(logm+logn) |
Question 63 Explanation:
In best case, no. of comparisons is Min(m,n).
In worst case, no. of comparisons is m+n-1.
Then we require O(m+n) comparisons to merging two sorted lists.
In worst case, no. of comparisons is m+n-1.
Then we require O(m+n) comparisons to merging two sorted lists.
Question 64 |
AB + CD + *F/D + E* | |
ABCD + *F/DE*++
| |
A *B + CD/F *DE++ | |
A + *BCD/F* DE++ | |
None of the above |
Question 64 Explanation:
The postfix expression will be,
A B C D + * F / + D E * +
A B C D + * F / + D E * +
Question 65 |
I and II | |
II and III | |
I and IV | |
I and III |
Question 65 Explanation:
Binary search using linked list is not efficient as it will not give O(log n), because we will not be able to find the mid in constant time. Fnding mid in linked list takes O(n) time.
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 ietrative one in terms of performance.
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 ietrative one in terms of performance.
Question 66 |
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 |
Question 66 Explanation:
FORTRAN implementation do not permit recursion because they use the static allocation for variables.
→ Recursion requires dynamic allocation of data.
→ Recursion requires dynamic allocation of data.
Question 67 |
The recurrence relation that arises in relation with the complexity of binary search is:
 | |
 | |
 | |
 |
Question 67 Explanation:
In primary search, search for the half of the list and constant time for comparing. So,
∴
∴
Question 68 |
Which of the following algorithm design techniques is used in the quicksort algorithm?
Dynamic programming | |
Backtracking | |
Divide and conquer | |
Greedy method |
Question 68 Explanation:
In quick sort, we use divide and conquer technique.
Question 69 |
In which one of the following cases is it possible to obtain different results for call-by reference and call-by-name 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
|
Question 69 Explanation:
Passing an array element as a parameter then it gives different output values for the call-by-reference and call-by-name parameters.
{ ........
a[ ] = {1, 2, 3, 4}
i = 0
fun(a[i]);
print a[0];
}
fun(int x)
{
int i = 1;
x = 8;
}
O/p:
Call-by-reference = 8
Call-by-value = 1
{ ........
a[ ] = {1, 2, 3, 4}
i = 0
fun(a[i]);
print a[0];
}
fun(int x)
{
int i = 1;
x = 8;
}
O/p:
Call-by-reference = 8
Call-by-value = 1
Question 70 |
Which one of the following statements is false?
Optimal binary search tree construction can be performed efficiently using dynamic programming. | |
Breadth-first search cannot be used to find converted components of a graph. | |
Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed. | |
Depth-first search can be used to find connected components of a graph. |
Question 70 Explanation:
In BFS algorithm, we can randomly select a source vertex and then run, after that whether we need to check distance to each and every vertex from source is still infinite (or) not. If we find any vertex having infinite distance then the graph is not connected.
Question 71 |
g1(n) is O(g2(n)) | |
g1 (n) is O(3) | |
g2 (n) is O(g1 (n)) | |
g2 (n) is O(n) | |
Both A and B |
Question 71 Explanation:
In asymptotic complexity, we assume sufficiently large n. So, g1(n) = n2 and g2(n) = n3.
Growth rate of g1 is less than that of g2 i.e., g1(n) = O(g2(n)) = O(n).
Growth rate of g1 is less than that of g2 i.e., g1(n) = O(g2(n)) = O(n).
Question 72 |
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 72 Explanation:
Root directory can points to the various user directories. Then they will be stored in a way that user can't be easily modify them. Then they should be at fixed location on the disk.
Question 73 |
Consider a simple connected graph G with n vertices and n-edges (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. |
Question 73 Explanation:
If a graph have n vertices and n edges (n>2) then it is to be cyclic graph. Then it have atleast one cycle and if we remove two edges then it is not connected.
For example let us consider, n=3
For example let us consider, n=3
Question 74 |
O(n) | |
O(n2) | |
O(n3) | |
O(3n2) | |
O(1.5n2) | |
B, C, D and E |
Question 74 Explanation:
⇒ In this 'n' is constant. So, n is added to n times itself which is O(n2).
Hence, (a) is wrong. And rest (B), (C), (D), (E) are correct.
Question 75 |
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 75 Explanation:
Though the edges are to be sorted still due to union find operation complexity is O(m log n).
Question 76 |
Following algorithm(s) can be used to sort n integers in the range [1...n3] in O(n) time
Heapsort | |
Quicksort | |
Mergesort | |
Radixsort |
Question 76 Explanation:
As no comparison based sort can ever do any better than nlogn. So option (A), (B), (C) are eliminated. O(nlogn) is lower bound for comparison based sorting.
As Radix sort is not comparison based sort (it is counting sort), so can be done in linear time.
As Radix sort is not comparison based sort (it is counting sort), so can be done in linear time.
Question 77 |
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 |
Question 77 Explanation:
For n distinct elements the algorithm will take maximum time when:
→ The array is already sorted in ascending order.
→ The array is already sorted in descending order.
→ The array is already sorted in ascending order.
→ The array is already sorted in descending order.
Question 78 |
The minimum number of comparisons required to sort 5 elements is _____
7 |
Question 78 Explanation:
Minimum no. of comparisons
= ⌈log(n!)⌉
= ⌈log(5!)⌉
= ⌈log(120)⌉
= 7
= ⌈log(n!)⌉
= ⌈log(5!)⌉
= ⌈log(120)⌉
= 7
Question 80 |
4, 1, 6, 7, 3, 2, 5, 8 |
Question 80 Explanation:
Inorder traversal is
(Left, Root, Right)
So, the order will be
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 82 |
O(n2) | |
O(mn) | |
O(m+n) | |
O(m logn) | |
O(m2) | |
B, D and E |
Question 82 Explanation:
Though the edges are sorted still due to finding union operation complexity is O(m log n).
→ Where m is no. of edges and n is number of vertices then n = O(m2)
→ O(m logn) < O(mn)
→ Where m is no. of edges and n is number of vertices then n = O(m2)
→ O(m logn) < O(mn)
Question 83 |
20, 10, 20, 10, 20 | |
20, 20, 10, 10, 20 | |
10, 20, 20, 10, 20 | |
20, 20, 10, 20, 10 |
Question 83 Explanation:
PUSH(10), PUSH(20), POP = 20 (i)
→ 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
→ 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
There are 83 questions to complete.