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
       Algorithms       Huffman-Coding       GATE 2017 [Set-2]
Question 1 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 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
       Algorithms       Dynamic-Programming       GATE 2019
Question 2 Explanation: 
First understand the subsequence is an array is
Ex:
{A, B, C, D}
{A, AB, AC, AD, ABC, ABD, ACD, B, BC, BD, BCD, C, CD, D }
Step-1: Array of elements A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0 ]
Step-2: As per the given question, if they want to find maximum subsequence means
{6,3,13,4,4,12}
= 42
Step-3: But according to given recurrence relation, the sequence should be continuous. {6,3,13,4,4,12}.
This is not continuous subsequence.
Step-4: 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
       Algorithms       Sorting       GATE 2019
Question 3 Explanation: 
Step-1: Given, 25 distinct elements are to be sorted using quicksort.
Step-2: Pivot element = uniformly random.
Step-3: Worst case position in the pivot element is either first (or) last.
Step-4: So total 2 possibilities among 25 distinct elements
= 2/25
= 0.08
Question 4

There are n unsorted arrays: A1, A2, ..., An. Assume that n is odd. Each of A1, A2, ..., An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A1, A2, ..., An is

A
O(n)
B
O(n log n)
C
Ω(n2 log n)
D
O(n2)
       Algorithms       Sorting       GATE 2019
Question 4 Explanation: 
Finding the median in an unsorted array is O(n).
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(n2)
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 _________.

A
4
B
5
C
6
D
7
       Algorithms       Minimum-Spanning-Tree       GATE 2018
Question 5 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

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 Vopt. A greedy algorithm sorts the items by their value-to-weight 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 Vgreedy.

The value of Vopt − Vgreedy is ______ .

A
16
B
17
C
18
D
19
       Algorithms       0/1-Knapsack-and-fractional-knapsack       GATE 2018
Question 6 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
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:

A
B
C
D
       Algorithms       Asymptotic-Complexity       GATE 2017 [Set-1]
Question 7 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
Question 8

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)
       Algorithms       GATE 2017 [Set-1]
Question 8 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.
Question 9

Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:

    (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)
       Algorithms       Minimum-Spanning-Tree       GATE 2017 [Set-1]
Question 9 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.
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 _________.

A
5
B
6
C
7
D
8
       Algorithms       Searching       GATE 2017 [Set-1]
Question 10 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
Question 11

Match the algorithms with their time complexities:

      Algorithm                                     Time complexity
(P) Towers of Hanoi with n disks                       (i) Θ(n2)
(Q) Binary search given n stored numbers              (ii) Θ(n log⁡ n)
(R) Heap sort given n numbers at the worst case      (iii) Θ(2n)
(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)
       Algorithms       Match-the-Following       GATE 2017 [Set-2]
Question 11 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)
Question 12

Consider the recurrence function

Then T(n) in terms of Θ notation is

A
Θ(log⁡log⁡n)
B
Θ(log⁡n)
C
Θ(√n)
D
Θ(n)
       Algorithms       Time-Complexity       GATE 2017 [Set-2]
Question 12 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 = log⁡n
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

A
Θ(n√n)
B
Θ(n2)
C
Θ(n log⁡n)
D
Θ(n2 logn)
       Algorithms       Time-Complexity       GATE 2017 [Set-2]
Question 13 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 log⁡n) times.
Question 14

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

A
Θ(nlogn), Θ(nlogn), and Θ(n2)
B
Θ(n2 ), Θ(n2 ), and Θ(nlogn)
C
Θ(n2), Θ(nlogn), and Θ(nlogn)
D
Θ(n2), Θ(nlogn), and Θ(n2)
       Algorithms       Sorting       GATE 2016 [Set-1]
Question 14 Explanation: 
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 __________.

A
7
B
8
C
9
D
10
       Algorithms       Minimum-Spanning-Tree       GATE 2016 [Set-1]
Question 15 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.
Question 16

G = (V,E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?

    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
       Algorithms       Minimum-Spanning-Tree       GATE 2016 [Set-1]
Question 16 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.
Question 17

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

    I. Quicksort runs in Θ(n2) time
    II. Bubblesort runs in Θ(n2) 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
       Algorithms       Sorting       GATE 2016 [Set-2]
Question 17 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.
Question 18

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

A
Greedy paradigm.
B
Divide-and-Conquer paradigm.
C
Dynamic Programming paradigm.
D
Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.
       Algorithms       Floyd-Warshall-Algorithm       GATE 2016 [Set-2]
Question 18 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.
Question 19

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 A1A2A3A4 using the basic matrix multiplication method is _________.

A
1500
B
1501
C
1502
D
1503
       Algorithms       Matrix-Chain-Multiplication       GATE 2016 [Set-2]
Question 19 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
Question 20

The given diagram shows the flowchart 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
       Algorithms       Time-Complexity       GATE 2016 [Set-2]
Question 20 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
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.

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
       Algorithms       Quick-Sort       GATE 2015 [Set-1]
Question 21 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 22

Match the following:

(P) Prim's algorithm for minimum spanning tree               (i) Backtracking
(Q) Floyd-Warshall algorithm for all pairs shortest paths   (ii) Greedy method
(R) Mergesort                                              (iii) Dynamic programming
(S) Hamiltonian circuit                                     (iv) Divide and conquer
A
P-iii, Q-ii, R-iv, S-i
B
P-i, Q-ii, R-iv, S-iii
C
P-ii, Q-iii, R-iv, S-i
D
P-ii, Q-i, R-iii, S-iv
       Algorithms       Algorithms       GATE 2015 [Set-1]
Question 22 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.
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 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?

A
Unsorted array
B
Min-heap
C
Sorted array
D
Sorted doubly linked list
       Algorithms       Time-Complexity       GATE 2015 [Set-1]
Question 23 Explanation: 
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 ______________.

A
69
B
70
C
71
D
72
       Algorithms       Minimum-Spanning-Tree       GATE 2015 [Set-1]
Question 24 Explanation: 

⇒ Total sum = 10 + 9 + 2 + 15 + 7 + 16 + 4 + 6 = 69

--> First we compare A-C and A-B we find 9 at A-C it means A-B must greater than A-C and for minimum possible greater value than 9 will be 10
-> Second we compare B-E and C-D in which we select B-E is 15 which C-D possible weight 16.
-> Third, we compare E-D and F-D in which we select F-D 6 means E-D must be greater than 6 so possible value greater than 6 is 7 .
Note: Add First+Second+Third=(A-B=10)+(C-D=16)+(E-D=7)
Question 25

Given below are some algorithms, and some algorithm design paradigms

A. Dijkstra’s Shortest Path                     1. Divide and Conquer
B. Floyd-Warshall 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. Depth-first search
                                                5. Breadth-first search

Match the above algorithms on the left to the corresponding design paradigm they follow Codes:

A
1-i, 2-iii, 3-i, 4-v.
B
1-iii, 2-iii, 3-i, 4-v.
C
1-iii, 2-ii, 3-i, 4-iv.
D
1-iii, 2-ii, 3-i, 4-v.
       Algorithms       Algorithm-Paradigms       GATE 2015 [Set-2]
Question 25 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
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
(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)
       Algorithms       Partitioning-Algorithm       GATE 2015 [Set-2]
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 512-byte sector of the disk is _____________.  

A
6
B
6.1
C
6.2
D
6.3
       Algorithms       Secondary-Storage       GATE 2015 [Set-2]
Question 27 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
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?  

A
256
B
512
C
1024
D
2048
       Algorithms       Merge-Sort       GATE 2015 [Set-3]
Question 28 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
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 __________.

A
995
B
996
C
997
D
998
       Algorithms       Minimum-Spanning-Tree       GATE 2015 [Set-3]
Question 29 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 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 _______.

A
12
B
13
C
14
D
15
       Algorithms       General       GATE 2014 [Set-1]
Question 30 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
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)?

A
B
C
D
       Algorithms       P-NP       GATE 2014 [Set-1]
Question 31 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 32

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
       Algorithms       General       GATE 2014 [Set-1]
Question 32 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 33

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
Θ(n2)
D
Θ(log⁡n)
       Algorithms       Time-Complexity       GATE 2014 [Set-2]
Question 33 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)
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 = _________.

A
34
B
35
C
36
D
37
       Algorithms       Dynamic-Programming       GATE 2014 [Set-2]
Question 34 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
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 ______.

A
358
B
359
C
360
D
361
       Algorithms       Greedy-Algorithm       GATE 2014 [Set-2]
Question 35 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.
Question 36

The number of distinct minimum spanning trees for the weighted graph below is _______.

A
6
B
7
C
8
D
9
       Algorithms       Minimum-Spanning-Tree       GATE 2014 [Set-2]
Question 36 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 37

Consider the following rooted tree with the vertex labeled P as t he root:

The order in which the nodes are visited during in-order traversal is

A
SQPTRWUV
B
SQPTUWRV
C
SQPTWUVR
D
SQPTRUWV
       Algorithms       Tree Traversal       GATE 2014 [Set-3]
Question 37 Explanation: 
The tree can be redrawn as

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 _________.

A
19
B
20
C
21
D
22
       Algorithms       Graphs       GATE 2014 [Set-3]
Question 38 Explanation: 

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

A
O(n2)
B
O(n log n)
C
Θ(n log⁡n)
D
O(n3)
       Algorithms       Sorting       GATE 2014 [Set-3]
Question 39 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 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(nalogbn + mclogdn), the value of a + 10b + 100c + 1000d is ____.

A
110
B
111
C
112
D
113
       Algorithms       Binary-Search-Tree       GATE 2014 [Set-3]
Question 40 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
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?

A
(97×97×97)/1003
B
(99×98×97)/1003
C
(97×96×95)/1003
D
(97×96×95)/(3!×1003)
       Algorithms       Hashing       GATE 2014 [Set-3]
Question 41 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
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 leftMostChild-rightSibling 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.
       Algorithms       ree Traversals       GATE 2014 [Set-3]
Question 42 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.
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 = n-1;
    do
    {
        k = (i+j)/2;
        if (x <= listA[k])
            j = k-1;
        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.
       Algorithms       Searching       GATE 2014 [Set-3]
Question 43 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.
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?

A
O(log n)
B
O(n)
C
O(n log n)
D
O(n2)
       Algorithms       Sorting       GATE 2013
Question 44 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).
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?

A
O(1)
B
O(log n)
C
O(n)
D
O(n log n)
       Algorithms       Sorting       GATE 2013
Question 45 Explanation: 
For skewed binary search tree on n nodes, the tightest upper bound to insert a node is O(n).
Question 46

Consider the languages L1 = ϕ and L= {a}. Which one of the following represents L1L2* ∪ L1*?

A
{є}
B
ϕ
C
a*
D
{є,a}
       Algorithms       Regular languages and Finite automata       GATE 2013
Question 46 Explanation: 
As we know, for any regular expression R,
Rϕ = ϕR = ϕ
So L1 L2 * = ϕ
and L1 * = {ϕ}* = {ϵ}
So L1L2* ∪ L1* = {ϵ}
Question 47

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

A
Θ(n2)
B
Θ(n2 log n)
C
Θ(n3)
D
Θ(n3 log n)
       Algorithms       Sorting       GATE 2013
Question 47 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 = O(n2)
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?

A
1/8
B
1
C
7
D
8
       Algorithms       Graph-Theory       GATE 2013
Question 48 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
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.
A
P only
B
Q only
C
Both P and Q
D
Neither P nor Q
       Algorithms       Graph-Theory       GATE 2013
Question 49 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.
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.
A
P only
B
P and R only
C
R only
D
P, Q and S only
       Algorithms       Graph-Theory       GATE 2013
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.
Question 51

The number of elements that can be sorted in Θ(log n) time using heap sort is

A
Θ(1)
B
Θ(√log⁡n)
C
Θ (log⁡n/log⁡log⁡n)
D
Θ(log n)
       Algorithms       Sorting       GATE 2013
Question 51 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.
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;
}
A
3024
B
6561
C
55440
D
161051
       Algorithms       Pass-by-value       GATE 2013
Question 52 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
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?

A
10, 20, 15, 23, 25, 35, 42, 39, 30
B
15, 10, 25, 23, 20, 42, 35, 39, 30
C
15, 20, 10, 23, 25, 42, 35, 39, 30
D
15, 10, 23, 25, 20, 35, 42, 39, 30
       Algorithms       Tree Traversals       GATE 2013
Question 53 Explanation: 

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?

A
Θ(n)
B
Θ(n + k)
C
Θ(nk)
D
Θ(n2)
       Algorithms       Time-Complexity       GATE 2013
Question 54 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).
Question 55

Assuming P ≠ NP, which of the following is TRUE?

A
NP-complete = NP
B
NP-complete ∩ P = ∅
C
NP-hard = NP
D
P = NP-complete
       Algorithms       P-NP       GATE 2012
Question 55 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.
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
A(n) = Ω (W(n))
B
A(n) = Θ (W(n))
C
A(n) = O (W(n))
D
A(n) = o (W(n))
       Algorithms       Time-Complexity       GATE 2012
Question 56 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)) .
Question 57

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

A
T(n) ≤ 2T(n/5) + n
B
T(n) ≤ T(n/5) + T(4n/5) + n
C
T(n) ≤ 2T(4n/5) + n
D
T(n) ≤ 2T(n/2) + n
       Algorithms       Sorting       GATE 2008
Question 57 Explanation: 
Consider the case where one subset of set of n elements contains n/5 elements and another subset of set contains 4n/5 elements.
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 subset-sum 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?

A
Q solves the subset-sum problem in polynomial time when the input is encoded in unary
B
Q solves the subset-sum problem in polynomial time when the input is encoded in binary
C
The subset sum problem belongs to the class NP
D
The subset sum problem is NP-hard
       Algorithms       P-NP       GATE 2008
Question 58 Explanation: 
Note: Out of syllabus.
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

A
only vertex a
B
only vertices a, e, f, g, h
C
only vertices a, b, c, d
D
all the vertices
       Algorithms       Shortest-Path       GATE 2008
Question 59 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
Question 60

Merge sort uses

A
Divide and conquer strategy
B
Backtracking approach
C
Heuristic search
D
Greedy approach
       Algorithms       Sorting       GATE 1995
Question 60 Explanation: 
Merge sort uses the divide and conquer strategy.
Question 61

The postfix expression for the infix expression
A + B*(C + D)/F + D*E is:

A
AB + CD + *F/D + E*
B
ABCD + *F/DE*++
C
A *B + CD/F *DE++
D
A + *BCD/F* DE++
E
None of the above
       Algorithms       Post-fix-and-Prefix       GATE 1995
Question 61 Explanation: 
The postfix expression will be,
A B C D + * F / + D E * +
Question 62

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(n2)
A
I and II
B
II and III
C
I and IV
D
I and III
       Algorithms       General       GATE 1995
Question 62 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. Finding 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 iterative one in terms of performance.
Question 63

FORTRAN implementation do not permit recursion because

A
they use static allocation for variables
B
they use dynamic allocation for variables
C
stacks are not available on all machines
D
it is not possible to implement recursion on all machines
       Algorithms       Recursions       GATE 1994
Question 63 Explanation: 
FORTRAN implementation do not permit recursion because they use the static allocation for variables.
→ Recursion requires dynamic allocation of data.
Question 64

The recurrence relation that arises in relation with the complexity of binary search is:

A
T(n) = T(n/2) + k, k a constant
B
T(n) = 2T(n/2) + k, k a constant
C
T(n) = T(n/2) + log n
D
T(n) = T(n/2) + n
       Algorithms       Time-Complexity       GATE 1994
Question 64 Explanation: 
In binary search, search for the half of the list and constant time for comparing. So,
∴ T(n) = 2T(n/2) + k, k a constant
Question 65

Which of the following algorithm design techniques is used in the quicksort algorithm?

A
Dynamic programming
B
Backtracking
C
Divide and conquer
D
Greedy method
       Algorithms       Quick-Sort       GATE 1994
Question 65 Explanation: 
In quick sort, we use divide and conquer technique.
Question 66

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?

A
Passing a constant value as a parameter
B
Passing the address of an array as a parameter
C
Passing an array element as a parameter
D
Passing an array following statements is true
       Algorithms       Call-by-reference-and-Call-by-value       GATE 1994
Question 66 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
Question 67

Which one of the following statements is false?

A
Optimal binary search tree construction can be performed efficiently using dynamic programming.
B
Breadth-first search cannot be used to find converted components of a graph.
C
Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.
D
Depth-first search can be used to find connected components of a graph.
       Algorithms       Searching       GATE 1994
Question 67 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 68

Consider the following two functions:

Which of the following is true?

A
g1(n) is O(g2(n))
B
g1 (n) is O(3)
C
g2 (n) is O(g1 (n))
D
g2 (n) is O(n)
E
Both A and B
       Algorithms       Asymptotic-Notations       GATE 1994
Question 68 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).
Question 69

For parameters a and b, both of which are ω(1), T(n) = T(n1/a)+1, and T(b)=1.

Then T(n) is

A
θ(loga logb n)
B
θ(logb loga n)
C
θ(log2 log2 n)
D
θ(logab n)
       Algorithms       Recurrences       GATE 2020
Question 69 Explanation: 
T(n) = T(n1/a+1, T(b) = 1
T(n) = [T(n1/a2)+1] + 1
= [T(n1/a3)+1] + 2
= [T(n1/a3)] + 3
= [T(n1/ak)] + b
= logb n = ak
= log logb n = k log a
= k= loga logb n
T(n)=1+loga logb n
T(n)=O(loga logb n)
Question 70

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

A
θ(|E|+|V|)
B
θ(|E| log|V|)
C
θ(|E||V|)
D
θ(|V|)
       Algorithms       Minimum-Spanning-Tree       GATE 2020
Question 70 Explanation: 
Method-1:
• 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).
Method-2:
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: Method-1 is the most appropriate answer for giving a question.
Question 71

Consider a graph G = (V, E), where V = {v1, v2, …, v100}, E = {(vi, vj) | 1 ≤ i < j ≤ 100}, and weight of the edge (vi, vj) is |i - j|. The weight of the minimum spanning tree of G is ______.

A
99
       Algorithms       Minimum-Spanning-Tree       GATE 2020
Question 71 Explanation: 
• If there are n vertices in the graph, then each spanning tree has n − 1 edges.
• N =100
• Edge weight is |i-j| 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 72

The root directory of a disk should be placed

A
at a fixed address in main memory
B
at a fixed location on the disk
C
anywhere on the disk
D
at a fixed location on the system disk
E
anywhere on the system disk
       Algorithms       GATE 1993
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?

A
G has no cycles.
B
The graph obtained by removing any edge from G is not connected.
C
G has at least one cycle.
D
The graph obtained by removing any two edges from G is not connected.
E
Both C and D.
       Algorithms       Graphs       GATE 1993
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.
Question 74

where O(n) stands for order n is:

A
O(n)
B
O(n2)
C
O(n3)
D
O(3n2)
E
O(1.5n2)
F
B, C, D and E
       Algorithms       Time-Complexity       GATE 1993
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 __________

A
O(m log n)
       Algorithms       Krushkal\'s-Algorithm       GATE 1992
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

A
Heapsort
B
Quicksort
C
Mergesort
D
Radixsort
       Algorithms       Sorting       GATE 1992
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.
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.

A
n
       Algorithms       Quick-Sort       GATE 1992
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.
Question 78

The minimum number of comparisons required to sort 5 elements is _____

A
7
       Algorithms       Sorting       GATE 1991
Question 78 Explanation: 
Minimum no. of comparisons
= ⌈log(n!)⌉
= ⌈log(5!)⌉
= ⌈log(120)⌉
= 7
Question 79
 

The weighted external path length of the binary tree in figure is _____

A
144
       Algorithms       Binary-Trees       GATE 1991
Question 79 Explanation: 
Question 80

If the binary tree in figure is traversed in inorder, then the order in which the nodes will be visited is ______

A
4, 1, 6, 7, 3, 2, 5, 8
       Algorithms       Tree Traversals       GATE 1991
Question 80 Explanation: 
Inorder traversal is
(Left, Root, Right)
So, the order will be
4, 1, 6, 7, 3, 2, 5, 8
Question 81

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.
A
A-S, B-R, C-P, D-Q
       Algorithms       General       GATE 1991
Question 82

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:

A
O(n2)
B
O(mn)
C
O(m+n)
D
O(m log n)
E
O(m2
F
B, D and E
       Algorithms       Time-Complexity       GATE 1991
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)
Question 83

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), POP
The sequence of values popped out is:
A
20, 10, 20, 10, 20
B
20, 20, 10, 10, 20
C
10, 20, 20, 10, 20
D
20, 20, 10, 20, 10
       Algorithms       Stacks       GATE 1991
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
Question 84

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
(a) - (r), (b) - (p), (c) - (s), (d) - (q)
       Algorithms       Match-the-Following       GATE 1990
Question 84 Explanation: 
Strassen's matrix multiplication algorithm - Divide and Conquer
Kruskal's minimum spanning tree algorithm - Greedy method
Biconnected components algorithm - Depth first search
Floyd's shortest path algorithm - Dynamic programming
Question 85

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

A
p
B
p + 1
C
n - p
D
n - p + 1Total element = n
RST contains elements = p
Root contains = 1 element
1st contains = n - (p + 1) element

Root contains the value is n - p.
       Algorithms       Tree Traversals       GATE 2005-IT
Question 85 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.
Question 86

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

A
k
B
k + 1
C
n - k - 1
D
n - k
       Algorithms       Graph-Traversal       GATE 2005-IT
Question 86 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 connected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n - k
Question 87

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. Bellman-Ford algorithm       A: O ( m log n)   
2. Kruskal’s algorithm          B: O (n3) 
3. Floyd-Warshall algorithm     C: O (nm)
4. Topological sorting	        D: O (n + m) 
A
1→ C, 2 → A, 3 → B, 4 → D
B
1→ B, 2 → D, 3 → C, 4 → A
C
1→ C, 2 → D, 3 → A, 4 → B
D
1→ B, 2 → A, 3 → C, 4 → D
       Algorithms       General       GATE 2005-IT
Question 87 Explanation: 
Bellman-ford algorithm → O(nm)
Krushkal's algorithm → O(m log n)
Floyd-Warshall algorithm → O(n3)
Topological sorting → O(n+m)
Question 88

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?

A
2
B
3
C
4
D
6
       Algorithms       Sorting-and-Searching       GATE 2005-IT
Question 88 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]
Question 89

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:

A
2h-1
B
2h-1 + 1
C
2h - 1
D
2h
       Algorithms       Tree Traversals       GATE 2005-IT
Question 89 Explanation: 
Let's take an example,

Above tree satisfies the property given in the question. Hence, only option (B) satisfies it.
Question 90

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?

A
T(n) = θ(log n)
B
T(n) = θ(√n)
C
T(n) = θ(n)
D
T(n) = θ(n log n)
       Algorithms       Recursion       GATE 2005-IT
Question 90 Explanation: 
Apply Master's theorem.
Question 91

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?

A
There exists a cutset in G having all edges of maximum weight
B
There exists a cycle in G having all edges of maximum weight
C
Edge e cannot be contained in a cycle
D
All edges in G have the same weight
       Algorithms       Graph-Theory       GATE 2005-IT
Question 91 Explanation: 
(A) True, because if there is heaviest edge in MST, then there exist a cut with all edges with weight equal to heaviest edge.

(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 92

A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order 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 post-order, the sequence obtained would be

A
8, 7, 6, 5, 4, 3, 2, 1
B
1, 2, 3, 4, 8, 7, 6, 5
C
2, 1, 4, 3, 6, 7, 8, 5
D
2, 1, 4, 3, 7, 8, 6, 5
       Algorithms       Tree Traversals       GATE 2005-IT
Question 92 Explanation: 
Pre-order is given as
5, 3, 1, 2, 4, 6, 8, 7
In-order 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 93

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

A
4
B
7
C
23
D
99
       Algorithms       Graph-Theory       GATE 2005-IT
Question 93 Explanation: 
Edge set consists of edges from i to j, using either
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 94

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

A
5
B
4
C
3
D
2
       Algorithms       Cyclomatic-Complexity       GATE 2005-IT
Question 94 Explanation: 
Note: Out of syllabus.
Question 95

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

A
O(log n)
B
O(n)
C
O(n log log n)
D
O(n log n)
       Algorithms       Binary-Trees       GATE 2004-IT
Question 95 Explanation: 
The above statement is actually algorithm for building a heap of an input array A.
And we know that time complexity for building the heap is O(n).
Question 96

Which one of the following binary trees has its inorder and preorder traversals as BCAD  and ABCD, respectively?

A
B
C
D
       Algorithms       Tree Traversals       GATE 2004-IT
Question 96 Explanation: 
Inorder traversal is,
Left root right.
Preorder traversal is,
Root left right.
Question 97

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?

A
f(n) + g(n) = O(h(n)) + h(n))
B
f(n) = O(h(n))
C
fh(n) ≠ O(f(n))
D
f(n)h(n) ≠ O(g(n)h(n))
       Algorithms       Time-Complexity       GATE 2004-IT
Question 97 Explanation: 
f(n) = O(h(n)) [Using transitivity]
So, f(n)g(n) = O(g(n)h(n)) is True.
Hence, (D) is false.
Question 98

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?

A
(E, G), (C, F), (F, G), (A, D), (A, B), (A, C)
B
(A, D), (A, B), (A, C), (C, F), (G, E), (F, G)
C
(A, B), (A, D), (D, F), (F, G), (G, E), (F, C)
D
(A, D), (A, B), (D, F), (F, C), (F, G), (G, E)
       Algorithms       Greedy-Method       GATE 2004-IT
Question 98 Explanation: 
(A) and (B) produce disconnected components with the given order in options which is never allowed by Prim's algorithm.
(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 99

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(n-k) + T(k) + cn
 Q. Merge sort	             II. T(n) = 2T(n-1) + 1
 R. Quick sort	            III. T(n) = 2T(n/2) + cn
 S. Tower of Hanoi	     IV. T(n) = T(n/2) + 1 
A
P-II, Q-III, R-IV, S-I
B
P-IV, Q-III, R-I, S-II
C
P-III, Q-II, R-IV, S-I
D
P-IV, Q-II, R-I, S-III
       Algorithms       General       GATE 2004-IT
Question 99 Explanation: 
Quick sort - T(n) = T(n-k) + T(k) + cn
Binary search - T(n/2) + 1
Merge sort - T(n) = 2T(n/2)+ cn
Tower of hanoi - T(n) = 2T(n-1) +1
Question 100
The following paradigm can be used to find the solution of the problem in minimum time: Given a set of non-negative integer, and a value K, determine if there is a subset of the given set with the sum equal to K:
A
Divide and Conquer
B
Dynamic Programming
C
Greedy Algorithm
D
Branch and Bound
       Algorithms       Dynamic-Programming       ISRO-2018
Question 100 Explanation: 
The above problem clearly specifies that sum of subset problem. The sum of the subset problem using recursion will give exponential time. Using dynamic programming we can get pseudo-polynomial time.
Sum of subset problem:
Given a set of non-negative 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 101
Given two sorted list of size m and n respectively. The number of comparisons needed the worst case by the merge sort algorithm will be
A
m*n
B
maximum of m and n
C
minimum of m and n
D
m+n–1
       Algorithms       Sorting       ISRO-2018
Question 101 Explanation: 
Here the maximum number of comparisons is m+n-1.
For example: Take 2 sub-arrays 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+n-1 can be taken as O(m+n).
Question 102
Of the following sorting algorithms, which has a running time that is least dependent on the initial ordering of the input?
A
Merge Sort
B
Insertion Sort
C
Selection Sort
D
Quick Sort
       Algorithms       Sorting       ISRO-2018
Question 102 Explanation: 
Question 103
The level of aggregation of information required for operational control is
A
Detailed
B
Aggregate
C
Qualitative
D
None of the above
       Algorithms       Aggregation       ISRO-2007
Question 103 Explanation: 
Question 104
Selection sort algorithm design technique is an example of
A
Greedy method
B
Divide-and-conquer
C
Dynamic Programming
D
Backtracking
       Algorithms       Sorting       ISRO-2007
Question 104 Explanation: 
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
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 105
The average case and worst case complexities for Merge sort algorithm are
A
O(n2), O(n2)
B
O(n2), O(nlog2n)
C
O(n log2n), O(n2)
D
O(n log2n), O(n log2n)
       Algorithms       Sorting       ISRO-2007
Question 105 Explanation: 
The best case, average case and worst case complexities for Merge sort algorithm are O( nlog2n ).
Question 106
The time taken by binary search algorithm to search a key in a sorted array of n elements is
A
O ( log2n )
B
O ( n )
C
O ( n log2n )
D
O ( n2 )
       Algorithms       Searching       ISRO-2007
Question 106 Explanation: 
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. It takes a maximum of log(n) searches to search an element from the sorted array.
Question 107
The Fibonacci sequence is the sequence of integers
A
1, 3, 5, 7, 9, 11, 13
B
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
C
0, 1, 3, 4, 7, 11, 18, 29, 47
D
0, 1, 3, 7, 15
       Algorithms       Fibbonacci-Series       ISRO-2007
Question 107 Explanation: 
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation Fn = Fn-1 + Fn-2
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 108
The running time of an algorithm is given by Then what should be the relation between T(1), T(2) and T(3), so that the order of the algorithm is constant?
A
T(1) = T(2) = T(3)
B
T(1) + T(3) = 2 * T(2)
C
T(1) – T(3) = T(2)
D
T(1) + T(2) = T(3)
       Algorithms       Time-Complexity       ISRO-2018
Question 108 Explanation: 
T(n)= T(n-1) + T(n-2) – T(n-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(n-1) + T(n-2) - T(n-3) = n-1 + n-2 - n + 3 = n
So order is O(n)
Question 109
The time complexity of computing the transitive closure of binary relation on a set of n elements is known to be
A
O(n)
B
O(n log n)
C
O(n3/2)
D
O(n3)
       Algorithms       Time-Complexity       ISRO-2018
Question 109 Explanation: 
→ In mathematics the transitive closure of a binary relation R on a set X is defined as the smallest relation on X that contains R and is transitive. More formally, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal.
→ 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 110
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?
A
Dynamic programming
B
Backtracking
C
Greedy
D
Divide and Conquer
       Algorithms       Algorithm-Paradigms       ISRO CS 2008
Question 110 Explanation: 
→ 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 shortest paths between all pairs of vertices
→ The Floyd-Warshall algorithm is an example of dynamic programming.
Question 111
The problems 3-SAT and 2-SAT are
A
Both NP-complete
B
Both in P
C
NP-complete and in P, respectively
D
Undecidable and NP-complete, respectively
       Algorithms       NP complete       ISRO-2017 May
Question 111 Explanation: 
→ 2-SAT is the first non polynomial problem is solved in polynomial time.
→ 3-SAT problem is NP- complete problem
Question 112
The recurrence relation that arises in relation with the complexity of binary search is:
A
T(n)=2T(n/2)+k , where k is constant
B
T(n)=T(n/2) +k, where k is constant
C
T(n)=T(n/2)+logn
D
T(n)=T(n/2)+n
       Algorithms       Searching       ISRO-2017 May
Question 112 Explanation: 
Binary search in a sorted array
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 113
Which one of the following in-place sorting algorithms needs the minimum number of swaps?
A
Insertion Sort
B
Quick Sort
C
Heap Sort
D
Selection Sort
       Algorithms       Sorting       ISRO-2017 May
Question 113 Explanation: 
Selection sort requires minimum number of swaps i.e O(n)

Question 114
The number of swappings needed to sort the numbers 8, 22, 7, 9, 31, 5, 13 in ascending order, using bubble sort is
A
11
B
12
C
13
D
10
       Algorithms       Sorting       ISRO-2017 May
Question 114 Explanation: 
Step-1: 8,7,22,9,31,5,13
Step-2: 8,7,9,22,31,5,13
Step-3: 8,7,9,22,5,31,13
Step-4: 8,7,9,22,5,13,31
Step-5: 7,8,9,22,5,13,31
Step-6: 7,8,9,5,22,13,31
Step-7: 7,8,9,5,13,22,31
Step-8: 7,8,5,9,13,22,31
Step-9: 7,5,8,9,13,22,31
Step-10: 5,7,8,9,12,22,31
Note:Total 10 swaps are required to sort the array.
Question 115
Which of the following algorithm solves the all-pairs shortest path problem?
A
Prim’s algorithm
B
Dijkstra's algorithm
C
Bellman-Ford’s algorithm
D
Floyd-Warshall’s algorithm
       Algorithms       Dynamic-Programming       ISRO-2017 May
Question 115 Explanation: 
Prim's → Minimum Spanning tree
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.
Floyd-Warshall’s algorithm→ All pair shortest path problem
Question 116
The time complexity of computing the transitive closure of binary relation on a set of n elements is known to be
A
O(nlogn)
B
O(n3/2)
C
O(n3)
D
O(n)
       Algorithms       Time-Complexity       ISRO-2017 May
Question 116 Explanation: 
Transitive closure generally uses Floyd-Warshall Algorithm which gives a time complexity of O(n3)
Question 117
How many comparisons are needed to sort an array of length 5 if a straight selection sort is used and array is already in the opposite order?
A
1
B
5
C
10
D
20
       Algorithms       Sorting       ISRO CS 2008
Question 117 Explanation: 
Consider the array: 5 4 3 2 1
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 (n-1) numbers starting by 1
S = ((1 + (n-1) )*(n-1) )/2
S = 10
Question 118
Consider the recurrence equation
T(n) = 2T(n-1), if n>0
= 1, otherwise
Then T(n) is (in big O order)
A
O(n)
B
O(2n)
C
O(1)
D
O(log n)
       Algorithms       Time-Complexity       ISRO-2017 December
Question 118 Explanation: 
Question 119
Match the following and choose the correct Solution for the order A, B, C, D
A
r, s, p, q
B
r, p, s, q
C
q, s, p, r
D
s, p, q, r
       Algorithms       Dynamic-Programming-and-Sorting       ISRO-2017 December
Question 119 Explanation: 
Strassen matrix multiplication→ Divide and conquer
Insertion sort→ Decrease and Conquer
Gaussian Elimination→ Transform and Conquer
Floyd Shortest path algorithm→ Dynamic programming
Question 120
The average number of key comparisons required for a successful search for sequential search on items is
A
n/2
B
(n-1)/2
C
(n+1)/2
D
None of these
       Algorithms       Searching       ISRO-2016
Question 120 Explanation: 
Total comparisons required
= No. of comparisons if element present in 1st position + No. of comparisons if element present in 2ndnd position + ............. + No. of comparisons if element present in nth 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 121
Algorithm design technique used in quicksort algorithm is?
A
Dynamic programming
B
Backtracking
C
Divide and conquer
D
Greedy method
       Algorithms       Sorting       ISRO-2016
Question 121 Explanation: 
Divide and conquer sorting algorithms:
1. Quick sort
2. Merge sort
3. Heap sort
****Binary search also follows the divide and conquer.
Question 122
Consider the following recurrence:
T(n) = 2T(√n) + 1
T(1) = 1
Which of the following is true?
A
T(n)= O(log log n)
B
T(n) = O(log n)
C
T(n) = O(√n)
D
T(n)= O(n)
       Algorithms       Time-Complexity       ISRO-2016
Question 122 Explanation: 
Question 123
The frequency of a number in an array is the number of times it appears in the array. Describe an algorithm that finds the most frequent number in an array of n numbers. If there are multiple numbers with highest frequency then list them all. Analyze the complexity of your algorithm.
A
Explanation
       Algorithms       Time-Complexity       CHENNAI MATHEMATICAL INSTITUTE - M.Sc. / Ph.D. Programme in Computer Science ( 15 May 2014 )
Question 123 Explanation: 
Let A be the array containing n numbers.
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 124
At the end of its fifth successful season, the Siruseri Premier League is planning to give an award to the Most Improved Batsman over the five years. For this, an Improvement Index will be computed for each batsman. This is defined as the longest sequence of increasing scores by the batsman among all his scores over the five seasons. For example, if the scores for a batsman over the five seasons are (20, 23, 6, 34, 22, 52, 42, 67, 89, 5, 100), his Improvement Index is 7 based on the sequence (20, 23, 34, 52, 67, 89, 100). Describe an efficient algorithm based on dynamic programming to compute the Improvement Index for a batsman with an overall sequence of n scores. Analyze the complexity of your algorithm.
A
Explanation
       Algorithms       Dynamic-Programming       CHENNAI MATHEMATICAL INSTITUTE - M.Sc. / Ph.D. Programme in Computer Science ( 15 May 2014 )
Question 124 Explanation: 
The goal is to find the longest ascending subsequence in a given sequence of numbers. Let the original sequence S be of length n and let S[i], i ∈ 1, 2, . . . , n, denote the value at position i.
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 125
Number of comparisons required for an unsuccessful search of an element in a sequential search, organized, fixed length, symbol table of length L is
A
L
B
L/2
C
(L+1)/2
D
2L
       Algorithms       Searching       ISRO CS 2011
Question 125 Explanation: 
A linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched
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 126
Let T(n) be defined by T(1) = 10 and T(n + 1) = 2n + T(n) and for all integers n ≥ 1 . Which of the following represents the order of growth of T(n) as a function of
A
O(n)
B
O(n log n)
C
O(n2)
D
O(n3)
       Algorithms       Recursion       ISRO CS 2011
Question 126 Explanation: 
Given T(1) is 10 and substitute “n” from 1 in the following equation
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(n2)
Question 127
Which of the following algorithm design technique is used in merge sort?
A
Greedy method
B
Backtracking
C
Dynamic programming
D
Divide and Conquer
       Algorithms       Sorting       ISRO CS 2011
Question 127 Explanation: 
Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.
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 128
Which of the following sorting algorithms has the minimum running time complexity in the best and average case?
A
Insertion sort, Quick sort
B
Quick sort, Quick sort
C
Quick sort, Insertion sort
D
Insertion sort, Insertion sort
       Algorithms       Sorting       ISRO CS 2013
Question 128 Explanation: 
Question 129
Suppose there are 11 items in sorted order in an array. How many searches are required on the average, if binary search is employed and all searches are successful in finding the item?
A
3.00
B
3.46
C
2.81
D
3.33
       Algorithms       Searching       ISRO CS 2014
Question 129 Explanation: 
We can arrange 11 items in the four levels(level-0,1,2,3).
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
Level-3 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 level-3 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 130
Consider the following sorting algorithms.
  1. Quicksort
  2. Heapsort
  3. Mergesort
Which of them perform in least time in the worst case?
A
1 and 2 only
B
2 and 3 only
C
3 only
D
1, 1 and 3
       Algorithms       Sorting       ISRO CS 2014
Question 130 Explanation: 
Question 131
What is the time complexity for the following C module? Assume that n>0 .
int module(int n)
{
if (n == 1)
return 1;
else
return (n + module(n-1));
}
A
O(n)
B
O(log n)
C
O(n2)
D
O(n!)
       Algorithms       Time-Complexity       ISRO CS 2014
Question 131 Explanation: 
Question 132

The solution of the recurrence relation T(m) = T(3m/4) + 1 is :

A
θ(lg m)
B
θ(m)
C
θ(mlg m)
D
θ(lglg m)
       Algorithms       Recurrences       UGC-NET CS 2018 JUNE Paper-2
Question 132 Explanation: 
Using Masters Method:
a = 1, b = 4/3, k = 0, p = 0
Here, a = bk
So, T(m) = nlog a/ log b logp+1 n
T(m) = θ(log m)
Question 133

Which of the following algorithms solves the single-source shortest paths ?

A
Prim’s algorithm
B
Floyd - Warshall algorithm
C
Johnson’s algorithm
D
Dijkstra’s algorithm
       Algorithms       Greedy-approach       UGC-NET CS 2018 JUNE Paper-2
Question 133 Explanation: 
Dijkstra’s algorithm is a Single source shortest path algorithm used to find the shortest path using Greedy approach.
Question 134

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 :

A
2.4
B
1.87
C
3.0
D
2.15
       Algorithms       Algorithm-Paradigms       UGC-NET CS 2018 JUNE Paper-2
Question 134 Explanation: 

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 (4-bits)
E = 1001 (4-bits)
D = 101 (3-bits)
C = 11 (2-bits)
B = 0 (1-bit)
Question 135

A binary search tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves :

A
cannot have more than 37 nodes
B
has exactly 37 nodes
C
has exactly 35 nodes
D
cannot have more than 35 nodes
       Algorithms       Binary-search-tree       UGC-NET CS 2018 JUNE Paper-2
Question 135 Explanation: 
L = I(n - 1)+ 1
Where,
L = Number of leaf nodes
n = N-ary 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 136

Match the following with respect to algorithm paradigms :

          List-I                        List-II 
(a) The 8-Queens problem               (i) Dynamic programming 
(b) Single-Source shortest paths      (ii) Divide and conquer
(c) STRASSEN’s Matrix multiplication (iii) Greedy approach 
(d) Optimal binary search trees       (iv) Backtracking

A
(a)-(iv), (b)-(i), (c)-(iii), (d)-(ii)
B
(a)-(iv), (b)-(iii), (c)-(i), (d)-(ii)
C
(a)-(iii), (b)-(iv), (c)-(ii), (d)-(i)
D
(a)-(iv), (b)-(iii), (c)-(ii), (d)-(i)
       Algorithms       Algorithm-Paradigms       UGC-NET CS 2018 JUNE Paper-2
Question 136 Explanation: 
8-Queens problem use Backtracking.
Single-Source shortest paths use Greedy approach.
STRASSEN’s Matrix multiplication use Divide and conquer technique.
Optimal binary search trees use Dynamic programming.
Question 137
The maximum number of comparisons needed to sort 9 items using radix sort is (assume each item is 5 digit octal number) :
A
45
B
72
C
360
D
450
       Algorithms       Sorting       UGC-NET CS 2018 JUNE Paper-2
Question 137 Explanation: 
Total sort items = 9
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 138

A 5-ary 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 :

A
30
B
33
C
45
D
None of the above
       Algorithms       Binary-search-tree       UGC-NET CS 2018 JUNE Paper-2
Question 138 Explanation: 
**They excluded for Evaluation** . We given how to approach this problem.
L = I(n - 1) + 1
Where,
L = Number of leaf nodes
n = N-ary 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 139

Consider a Boolean function of ‘n’ variables. The order of an algorithm that determines whether the Boolean function produces a output 1 is :

A
Logarithmic
B
Linear
C
Quadratic
D
Exponential
       Algorithms       Boolean-functions       UGC-NET CS 2018 JUNE Paper-2
Question 139 Explanation: 

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 2n. It means exponential.
Question 140

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 Ford-Fulkerson algorithm is bounded by :

A
O(E∗f)
B
O(E2∗f)
C
O(E∗f2)
D
None of the above
       Algorithms       Greedy-approach       UGC-NET CS 2018 JUNE Paper-2
Question 140 Explanation: 
****Excluded for evaluation***
→ The Ford-Fulkerson method or Ford-Fulkerson 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 Ford-Fulkerson 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 Ford-Fulkerson algorithm with guaranteed termination and a runtime independent of the maximum flow value is the Edmonds-Karp algorithm, which runs in O(VE2)time.
Question 141
For the given recurrence equation
T(n)=2T(n-1), if n>0.
=1, otherwise
A
O(nlogn)
B
O(n2)
C
O(2n)
D
O(n)
       Algorithms       Nielit Scentist-B [02-12-2018]
Question 141 Explanation: 
T(n) = 2T (n - 1) + 1
= 2 [2T(n - 2) + 1] + 1
= 22 T(n - 2) + 3

= 2kT(n - k) + (2k - 1)
= 2n-1T(1) + (2n-1 - 1)
= 2n-1+ 2n-1 - 1
= 2n - 1
≅ O( 2n )
Question 142
The smallest element that can be found in time___ in a binary max heap
A
O(nlogn)
B
O(logn)
C
O(n)
D
O(n2)
       Algorithms       Nielit Scentist-B [02-12-2018]
Question 142 Explanation: 
We need to traverse all nodes in order to identify smallest element because it is not following binary search tree properties. Searching time for ‘n’ elements will take O(n) in worst case.
Question 143
___ is the worst case time complexity for all operations(i.e. Search,update and delete) in a general binary search tree
A
O(n)
B
O(nlogn)
C
O(logn) for search and insert, and O(n) for delete
D
None of these
       Algorithms       Nielit Scentist-B [02-12-2018]
Question 143 Explanation: 
→ Suppose the elements are not in sorted order, it will take O(n) time for worst case time complexity.
→ 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 144
Dijkstra’s algorithm is based on:
A
Greedy approach
B
Dynamic programming
C
Backtracking paradigm
D
Divide and conquer paradigm
       Algorithms       Nielit Scentist-B [02-12-2018]
Question 144 Explanation: 
→ Dijkstra's algorithm is following greedy approach. It always selects shortest path among all possibilities.
→ Dijkstra’s algorithm is solving the problem of single source shortest path.
Question 145
For the given nodes:
89,19,50,17,12,15,2,5,7,11,6,9,100
Minimum _____ number of interchanges are needed to convert it into a max-heap
A
3
B
4
C
5
D
6
       Algorithms       Nielit Scentist-B [02-12-2018]
Question 145 Explanation: 
1st swap is: 100 and 15
2nd swap is: 100 and 50
3rd swap is: 100 and 89
Question 146
_____sorting algorithms has the lowest worst case complexity
A
Selection sort
B
Bubble sort
C
Merge sort
D
Quick sort
       Algorithms       Nielit Scentist-B [02-12-2018]
Question 146 Explanation: 
The Worst case time complexity of Selection,Bubble and Quick sort is O(n2) where as Merge sort is O(nlog(n)). So Merger sort has lowest worst case time complexity
Question 147
Two alternative packages A and B are available for processing a database having 10k records. Package A requires 0.0001n​2​ time units and package B requires 10nlog​10​n time units​ ​ to process n records. What is the smallest value of k for which package B will be preferred over A?
A
12
B
10
C
6
D
5
       Algorithms       Asymptotic-Complexity       Nielit Scientist-B IT 4-12-2016
Question 147 Explanation: 
As per given information Package B 10nlog​ 10​ n is lesser than or equals to Package A 0.0001n​ 2​ 0
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 148
What is the type of the algorithm used in solving the 4 Queens problem?
A
Greedy
B
Branch and bound
C
Dynamic Programming
D
Backtracking
       Algorithms       Algorithm-Paradigms       Nielit Scientist-B IT 4-12-2016
Question 148 Explanation: 
N-Queen problem:​ an arrangement of N queens on a chess board, such that no queen can attack any other queens on the board.The chess queens can attack in any direction as horizontal, vertical, horizontal and diagonal way. A binary matrix is used to display the positions of N Queens, where no queens can attack other queens.
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 149
selection sort,quick sort is a stable sorting method
A
True,True
B
False, False
C
True,False
D
False,False
       Algorithms       Sorting       Nielit Scientist-B IT 4-12-2016
Question 149 Explanation: 

Question 150
Which of the following sorting procedures is the slowest?
A
Quick sort
B
Merge sort
C
Shell sort
D
Bubble sort
       Algorithms       Sorting       Nielit Scientist-B IT 4-12-2016
Question 150 Explanation: 
Bubble sort will execute O(n​ 2​ ) time worst case and also it takes n-1 comparisons. So, bubble sort procedure is the slowest one among all.
Question 151
The recurrence relation capturing the optimal execution time of the towers of Hanoi problem with n discs is:
A
T(n)=2T(n-2)+2
B
T(n)=2T(n/2)+1
C
T(n)=2T(n-2)+n
D
T(n)=2T(n-1)+1
       Algorithms       Recurrences       Nielit Scientist-B IT 4-12-2016
Question 151 Explanation: 
The recurrence equation for given recurrence function is
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​ n-1​ T(1) + (2​ n-1​ – 1)
= 2​ n-1​ + 2​ n-1​ – 1
= 2​ n​ – 1
≌ O(2​ n​ )
Question 152
Complexity of kruskal's algorithm for finding minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted is:
A
O(mn)
B
O(m)
C
O(m+n)
D
O(n)
       Algorithms       Asymptotic-Complexity       Nielit Scientist-B IT 4-12-2016
Question 152 Explanation: 
Implementation of Kruskal's algorithm should be implemented in 2 steps:
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 find-union algorithm. The find and union operations can take at most O(1) time. So, the total time complexity will be O(E).
Question 153

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(bd)
(c) Depth- Limited Search      iii) O(bm)
(d) Iterative deepening Search  iv) O(bl)
Code:
A
(a)-(iii), (b)-(ii), (c)-(iv), (d)-(i)
B
(a)-(ii), (b)-(iii), (c)-(iv), (d)-(i)
C
(a)-(i), (b)-(ii), (c)-(iv), (d)-(iii)
D
(a)-(i), (b)-(iii), (c)-(iv), (d)-(ii)
       Algorithms       Greedy-approach       UGC-NET CS 2018 DEC Paper-2
Question 153 Explanation: 
BFS → O(bd) worst case space complexity
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 154
Two alternative package A and B are available for processing a database having 10​ k records. Package A requires 0.00012n​​ time units and package B requires 10nlog​​10 n time units to process n records. What is the smallest value of k for which package B will be preferred over A?
A
12
B
10
C
6
D
5
       Algorithms       Time-Complexity       Nielit Scientist-C 2016 march
Question 154 Explanation: 
As per given information Package B 10nlog​ 10​ n is lesser than or equals to Package A 0.0001n​ 2​0
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​ 10k​ ≤ 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 155
The worst case running times of insertion sort, merge sort and quick sort respectively are
A
O(nlogn),O(nlogn) and O(n2)
B
O(n2),O(n2) and O(nlogn)
C
O(n2),O(nlogn) and O(nlogn)
D
O(n2),O(nlogn) and O(n2)
       Algorithms       Sorting       Nielit Scientist-B CS 22-07-2017
Question 155 Explanation: 
→ worst case running times of insertion sort → O(n2)
merge sort → O(nlogn)
quick sort → O(n2)
Question 156
You are given the postorder traversal,p, of a binary search tree on the n elements 1,2,..,n. You have to determine the unique binary search tree has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?
A
O(logn)
B
O(n)
C
O(nlogn)
D
none of the above, as the tree cannot be ​ be uniquely determined.
       Algorithms       Asymptotic-Complexity       Nielit Scientist-C 2016 march
Question 156 Explanation: 
Last element in post order is the root of tree- find this element in inorder-log n time. Now as in quick sort consider this as pivot and split the post order array into 2. All elements smaller than pivot goes to left and all elements larger than pivot goes to right and suppose we have k elements smaller than pivot, these elements will be same in both in-order as well as post order. Now, we already got the root, now left child is the left split and right child is the right split.
T(n) = T(k) + T(n-k-1) + logn
In worst case T(n) = O(nlogn), when k=0
But searching for an element in the in-order 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(n-k-1)+O(1)
Which gives T(n) = O(n)
since we know that all elements must be traversed at least once T(n) = θ(n)
Question 157
The most efficient algorithm for finding the number of connected components in a n undirected graph on n vertices and m edges has time complexity
A
O(n)
B
O(m)
C
O(m+n)
D
O(mn)
       Algorithms       Asymptotic-Complexity       Nielit Scientist-C 2016 march
Question 157 Explanation: 
To find the number of connected components using either BFS or DFS time complexity is θ(m+n).
Suppose if we are using Adjacency matrix means it takes θ(n​ 2​ ).
Question 158
An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array
A
solves it in linear time using a left to right pass of the array
B
solves in linear time using a right to left pass of the array
C
solves it using divide and conquer in time O(nlogn)
D
solves it in time O(n​ 2​ )
       Algorithms       Time-Complexity       Nielit Scientist-C 2016 march
Question 158 Explanation: 
Algorithm to solve the problem :
● 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 159
Which of the following standard algorithms is not Dynamic Programming based?
A
Bellman ford algorithm for single source shortest path
B
floyd Warshall for all pairs shortest paths
C
0-1 knapsack problem
D
Prim’s minimum spanning tree
       Algorithms       Dynamic-Programming       Nielit Scientist-B CS 22-07-2017
Question 159 Explanation: 
Prim’s minimum spanning tree is following greedy technique.
Question 160
Kadane algorithm is used to find
A
Maximum sum subsequence in an array
B
Maximum sum subarray in an array
C
Maximum product subsequence in an array
D
Maximum product subarray in an array
       Algorithms       Dynamic-Programming       Nielit Scientist-B CS 22-07-2017
Question 160 Explanation: 
Kadane algorithm is used to find the maximum sum subarray in an array. It runs in O(n) time complexity Implementation in python:
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 161
Given an random unsorted array ‘A’ in which every element is at most ‘d’ distance from is position in sorted array where d<Size(A). If we applied the insertion sort over this array, then the time complexity of algorithm is:
A
O(nlogd)
B
O(n2 logd)
C
O(nd)
D
O(n2d)
       Algorithms       Nielit STA [02-12-2018]
Question 161 Explanation: 
→ Using insertion sort worst case time complexity is O(n2).
→ They are asking to find the atmost distance from every element. So, it will take O(n2*d) from every node.
Note: Using heap sort , time complexity will be O(nlogd) and most effective than insertion sort.
Question 162
If G be an undirected connected graphs with distinct edge weight such that maximum weight and minimum weight of edge is given by emax and emin respectively. Then, Which of the following statements is TRUE?
A
Every minimum spanning tree of G must contain emin and emax
B
If emax is in a minimum spanning tree, then its removal must disconnect G
C
No minimum spanning tree contains emax
D
G has a multiple minimum spanning trees
       Algorithms       Nielit STA [02-12-2018]
Question 162 Explanation: 

If they mentioned distinct weights then we will get only one MST. So, Option-C is most appropriate solution.
Question 163
Consider bottom up merge sort working on ‘n’ elements such that n=2i. The minimum number of comparisons in order to get sorted list is:
A
nlog(n/2)
B
nlogn
C
(nlogn)/2
D
logn
       Algorithms       Nielit STA [02-12-2018]
Question 163 Explanation: 
Minimum comparison is only possible when first and last element of either array are smaller then first element of another. so in such as case at each level we will have n/2 comparisons In general= n/2 * number of levels = (nlogn)/2
Question 164

Match List-1 with List-2 and choose the correct answer from the code given below

           List 1					   List 2
(a) Greedy Best-first 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 Best-First Search        (iii) Suffers from excessive node generation
(d) Iterative-deepening A* Search   	(iv) Time complexity depends upon the quality of 
                                             heuristic
Code:
A
(a)-(iv), (b)-(iii), (c)-(ii), (d)-(i)
B
(a)-(i), (b)-(iv), (c)-(iii), (d)-(ii)
C
(a)-(iv), (b)-(i), (c)-(ii), (d)-(iii)
D
(a)-(i), (b)-(ii), (c)-(iii), (d)-(iv)
       Algorithms       Match-the-following       UGC-NET CS 2018 DEC Paper-2
Question 164 Explanation: 
Greedy Best-first Search: Selects a node for expansion if optimal path to that node has been found. Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule. Best-first search as estimating the promise of node n by a "heuristic evaluation function f(n) which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain."
A* Search: Time complexity depends upon the quality of heuristic.
Recursive Best-First 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.
Iterative-deepening A* Search: Avoids substantial overhead associated with keeping the sorted queue of nodes.
Question 165
which of the following sorting algorithms does not have a worst case running time of O(n​ 2​ )  
A
Insertion sort
B
merge sort
C
Quick sort
D
bubble sort
       Algorithms       Sorting       Nielit Scientist-B CS 2016 march
Question 165 Explanation: 
Question 166
The time complexity of the Tarjan’s algorithm for finding the strongly connected components of a graph having m vertices and n edges is:
A
O(m*n)
B
O(m+n)
C
O(m2)
D
O(mn)
       Algorithms       Nielit STA [02-12-2018]
Question 166 Explanation: 
Tarjan Algorithm
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 167
If there is in NP-Complete language L whose complement is in NP, then complement of any language in NP is in
A
P
B
NP
C
Both (A) and (B)
D
None of these
       Algorithms       NP complete       Nielit Scientist-B CS 2016 march
Question 167 Explanation: 
If there is in NP-Complete language L whose complement is in NP, then complement of any language in NP is in NP
Question 168
Time complexity of an algorithm T(n), where n is the input size is given by T(n)=T(n-1)+1/n, if n>1 =1, otherwise The order of this algorithm is
A
logn
B
n
C
n​ 2
D
n​ n
       Algorithms       Recurrences       Nielit Scientist-B CS 2016 march
Question 168 Explanation: 
T (n) = T (n − 1 ) + 1/n
Question 169

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

A
13
B
16
C
17
D
14
       Algorithms       Minimum-spanning-Tree       UGC-NET CS 2018 DEC Paper-2
Question 169 Explanation: 

The weight of this minimum spanning tree is 16.
Question 170

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) Floyd-Warshall 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
(a)-(i), (b)-(iii), (c)-(iv), (d)-(ii)
B
(a)-(i), (b)-(iii), (c)-(ii), (d)-(iv)
C
(a)-(iii), (b)-(i), (c)-(ii), (d)-(iv)
D
(a)-(iii), (b)-(i), (c)-(iv), (d)-(ii)
       Algorithms       Time-Complexity       UGC-NET CS 2018 DEC Paper-2
Question 170 Explanation: 
→ Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph and time complexity is O(V2).
→ Kruskal's algorithm is a minimum-spanning-tree 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 171

The second smallest of n elements can be found with _______ comparisons in worst case.

A
n + ceil(lg n) - 2
B
n - 1
C
lg n
D
3n/1
       Algorithms       Time-Complexity       UGC-NET CS 2018 DEC Paper-2
Question 171 Explanation: 

This takes n-1 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 172
To sort many large object or structures, it would be most efficient to
A
Place reference to them in and array an sort the array
B
place them in a linked list and sort the linked list
C
place pointers to them in an array and sort the array
D
place them in an array and sort the array
       Algorithms       Sorting       NieLit STA 2016 March 2016
Question 172 Explanation: 
Option-A is suitable for small amount of objects but not large
Option-B is not correct because it will extra time complexity and searching very difficult
Option-D is suitable for small amount of objects/elements
Question 173

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

A
4
B
2
C
3
D
5Computer-Networks
       Algorithms       Longest-common-subsequesnce       UGC-NET CS 2018 DEC Paper-2
Question 173 Explanation: 

Possible subsequences are : 130, 1210, 1301 and length of longest common subsequence is 4.
Question 174

The solution of recurrence relation : T(n) = 2T(sqrt(n)) + lg(n) is

A
O(lg (n) lg(n))
B
O(lg (n))
C
O(n lg (n))
D
O(lg (n) lg(lg(n)))
       Algorithms       Recurrence-Relations       UGC-NET CS 2018 DEC Paper-2
Question 174 Explanation: 
Question 175
The Knapsack problem belongs to which domain of problems?
A
Optimization
B
NP complete
C
Linear Solution
D
Sorting
       Algorithms       0/1-Knapsack-and-fractional-knapsack       Nielit Scientist-B CS 4-12-2016
Question 175 Explanation: 
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible
Question 176
The running time of quick sort algorithm depends heavily on the selection of:
A
No. of inputs
B
Arrangement of elements in an array
C
Size of elements
D
Pivot element
       Algorithms       Sorting       Nielit Scientist-B CS 4-12-2016
Question 176 Explanation: 
The running time of Quicksort will depend on how balanced the partitions are. If you are unlucky and select the greatest or the smallest element as the pivot, then each partition will separate only one element at a time, so the running time will be similar to Insertion Sort.However, Quicksort will usually pick a pivot that is mid-range, and it will partition the array into two parts.
Question 177
Two main measures for the efficiency of an algorithm are:
A
Processor and Memory
B
Complexity and Capacity
C
Time and Space
D
Data and Space
       Algorithms       Asymptotic-Complexity       Nielit Scientist-B CS 4-12-2016
Question 177 Explanation: 
The complexity of an algorithm is a function describing the efficiency of the algorithm in terms of the amount of data the algorithm must process. Usually there are natural units for the domain and range of this function. There are two main complexity measures of the efficiency of an algorithm:
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 fixed-length) units to measure this. We can use bytes, but it's easier to use, say, number of integers used, number of fixed-sized 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 178
What is the solution to the recurrence T(n)=T(n/2)+n?
A
O(log n)
B
O(n)
C
O(n logn)
D
None of these
       Algorithms       Asymptotic-Complexity       Nielit Scientist-B CS 4-12-2016
Question 178 Explanation: 
The above recurrence is in the form of masters theorem.
a=1,b=2,k=1,p=0
=ak
=O(n)
Question 179
The concept of order Big O is important because:
A
It can be used to decide the best algorithm that solves a given problem
B
It is the lower bound of the growth rate of algorithm
C
It determines the maximum size of a problem that can be solved in a given amount of time
D
Both (A) and (B)
       Algorithms       Asymptotic-Complexity       Nielit Scientist-B CS 4-12-2016
Question 179 Explanation: 
● Big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.
● 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 180
A machine needs a minimum of 100 sec to sort 1000 names by quick sort. The minimum time needed to sort 100 names will be approximately
A
50.2 sec
B
6.7 sec
C
72.7 sec
D
11.2 sec
       Algorithms       Sorting       ISRO CS 2015
Question 180 Explanation: 
We need to find the minimum time to sort the names by using quick sort.
The Worst case time complexity is O(n2)
Average and best case time complexity is O(n logn)
Step-1: 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 181
Six files F1, F2, F3, F4, F5 and F6 have 100, 200, 50, 80, 120, 150 records respectively. In what order should they be stored so as to optimize act. Assume each file is accessed with the same frequency
A
F3, F4, F1, F5, F6, F2
B
F2, F6, F5, F1, F4, F3
C
F1, F2, F3, F4, F5, F6
D
Ordering is immaterial as all files are accessed with the same frequency.
       Algorithms       Greedy-approach       ISRO CS 2015
Question 181 Explanation: 
Optimal merge pattern will give the optimal result after performing sorted order. Every time it will take least frequency elements and performing merging.
→ Final order is F3, F4, F1, F5, F6, F2
Question 182
The time complexity of the following C function is (assume n > 0)
int recursive (int n)
{
if(n == 1)
return (1);
else
return (recursive (n-1) + recursive (n-1));
}
A
O(n)
B
O(n log n)
C
O(n2)
D
O(2n)
       Algorithms       Time-Complexity       ISRO CS 2015
Question 182 Explanation: 
T(n) = 2T (n - 1) + 1
= 2 [2T(n - 2) + 1] + 1
= 22 T(n - 2) + 3

= 2kT(n - k) + (2k - 1)
= 2n-1T(1) + (2n-1 - 1)
= 2n-1 + 2n-1 - 1
= 2n - 1
≅ O( 2n )
Question 183
The number of spanning tree for a complete graph with 7 vertices are:
A
25
B
75
C
35
D
22×5
       Algorithms       Greedy-approach       ISRO CS 2015
Question 183 Explanation: 
To find number of spanning trees of a complete graph is nn-2.
Here, there are 7 nodes.
=77-2
=75
=16,807
Question 184
If one uses straight two-way merge sort algorithm to sort the following elements in ascending order:
20, 47, 15, 8, 9, 4, 40, 30, 12, 17
then the order of these elements after second pass of the algorithm is:
A
8, 9, 15, 20, 47, 4, 12, 17, 30, 40
B
8, 15, 20, 47, 4, 9, 30, 40, 12, 17
C
15, 20, 47, 4, 8, 9, 12, 30, 40, 17
D
4, 8, 9, 15, 20, 47, 12, 17, 30, 40
       Algorithms       Sorting       ISRO CS 2015
Question 184 Explanation: 
Explanation:
Question 185
0/1-Knapsack is a well known problem where, it is desired to get the maximum total profit by placing n items(each item is having some weight and associated profit) into a knapsack of capacity W. The table given below shows the weights and associated profits for 5 items, where one unit of each item is available to you. It is also given that the knapsack capacity W is 8. If the given 0/1 knapsack problem is solved using Dynamic Programming, which one of the following will be maximum earned profit by placing the items into the knapsack of capacity 8.
A
19
B
18
C
17
D
20
       Algorithms       0/1-Knapsack-and-fractional-knapsack       Nielit Scientist-B IT 22-07-2017
Question 185 Explanation: 
Here, we can get the first item using profit per weight even we are using 0/1 knapsack.

→ According to above Profit/weight ratio, the item-1 having maximum profit. So, pick item-1.
→ Now M=7, Pick item-2 because it has more profit.
→ Now M=5, Now according to profit/weight ration we can pick item-3 or item-5 but item-5 having more weight, so it exceeds capacity. If we are selecting item-3 means we are wasting 1 slot. So, here, profit/weight ration fails. So, follow brute force technique in this position. We can pick item-4 because it has weight 5.
→ Now, M=0 and Profit=19. [item1 + item2 + item4]
Question 186

What is the total number of spanning trees of a complete graph of 4 vertices (K4)?

A
16
B
8
C
4
D
15
       Algorithms       Greedy-approach       JT(IT) 2018 PART-B Computer Science
Question 186 Explanation: 
To find total number of spanning trees for complete graph using standard formula
nn-2 = 42 = 16
Question 187
What is the running time of the following function(specified as a function of the input value)?
void Function(int n)
{
int i=1;
int s=1;
while(s<=n)
{
i++;
s=s+i;
}
}
A
O(n)
B
O(n​ 2​ )
C
O(1)
D
O(​√n)
       Algorithms       Asymptotic-Complexity       Nielit Scientist-B IT 22-07-2017
Question 187 Explanation: 
S= 1, 3, 6, 10, 15 21….(>n) stopping condition.
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 188
The running time of an algorithm T(n),where 'n' is the input size, is given by
T(n)=8T(n/2)+qn, if n>1
=p, if n=1
Where p,q are constants. The order of this algorithm is
A
n2
B
nn
C
n3
D
N
       Algorithms       Recurrences       Nielit Scientific Assistance IT 15-10-2017
Question 188 Explanation: 
Apply master theorem.
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 189

Which of the following data structures is most suitable for radix sort?

A
Stack
B
Binary search tree
C
Tree
D
Linked list
       Algorithms       Sorting       JT(IT) 2018 PART-B Computer Science
Question 189 Explanation: 
→ Forming the circularly linked list requires more memory but allows the keys to be visited more directly in either ascending or descending order via a linear traversal of the linked list rather than a depth-first traversal of the entire trie.
→ 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 190
Consider a complete binary tree where the left and the right subtrees of the root are max heaps. The lower bound for the number of operations to convert the tree to a heap is:
A
Ω(logn)
B
Ω(nlogn)
C
Ω(n)
D
Ω(n2)
       Algorithms       Nielit Scientist-B 17-12-2017
Question 190 Explanation: 
→ We can apply Heapify (node) which take log n time. The lower bound for the number of operations to convert the tree to a heap is log n.
Question 191
The question is based on the following program fragment.
f(int Y[10], int x)
{
int u,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k] i=k;
else
j=k;
}
while((Y[k]!=x) && (i if(Y[k] ==x)
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?
A
Y is [1 2 3 4 5 6 7 8 9 10] and x<10
B
Y is [1 3 5 7 9 11 13 15 17 19] and x<1
C
Y is [ 2 2 2 2 2 2 2 2 2 2] and x>2
D
Y is [ 2 4 6 8 10 12 14 16 18 20] and 2
       Algorithms       Searching       Nielit Scientific Assistance IT 15-10-2017
Question 191 Explanation: 
This above code is similar to binary search
First iteration:
I=0,j=9
K=(0+9)/2=4
Elements with duplicate values of “2” the condition if(Y[k] Second iteration :
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 192
An algorithm is made up of two modules M1 and M2. If order of M1 is f(n) and M2 is g(n) then the order of algorithm is
A
max(f(n),g(n))
B
min(f(n),g(n))
C
f(n)+g(n)
D
f(n) * g(n)
       Algorithms       Asymptotic-Complexity       Nielit Scientific Assistance IT 15-10-2017
Question 192 Explanation: 
From the given statement, algorithm consists of two modules M1 and M2.
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)
Case-1 : 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 .
Case-2 : 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.
Case-3: 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 193

Which of the following greedy strategies gives the optimal solution for the following 0-1 knapsack problem?

w=30, w1=10, p1=11, w2=15, p2=12, w3=20, p3=24, w4=25, p4=25

A
Largest profit per unit weight first
B
Largest profit first
C
Lightest item first
D
Heaviest item first
       Algorithms       0/1-Knapsack-and-fractional-knapsack       JT(IT) 2018 PART-B Computer Science
Question 193 Explanation: 

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 194

Which of the following is the time complexity to find the determinant of an upper triangular matrix of order n*n?

A
Θ(n2.5)
B
Θ(n)
C
Θ(n2)
D
Θ(n)
       Algorithms       Time-Complexity       JT(IT) 2018 PART-B Computer Science
Question 194 Explanation: 
According to Cayley-Hamilton method, the determinant of a triangular matrix can indeed be computed in O(n) time, if multiplication of two numbers is assumed to be doable in constant time.
Question 195
Which type of algorithm is used to solve the "8 Queens" problem?
A
Greedy
B
Dynamic
C
Divide and conquer
D
Backtracking
       Algorithms       Backtracking       Nielit STA 17-12-2017
Question 195 Explanation: 
→ 8 queens problem is based backtracking method.
→ 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 196
Merge sort uses:
A
Divide and conquer
B
Backtracking
C
Heuristic approach
D
Greedy approach
       Algorithms       Nielit STA 17-12-2017
Question 196 Explanation: 
→ Merge Sort is a divide and conquer algorithm. It works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
→ The solutions to the sub-problems 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 197
Given two sorted list of size 'm' and 'n' respectively. he number of comparisons needed in the worst case by the merge sort algorithm will be:
A
m*n
B
minimum of m,n
C
Maximum of m,n
D
M+n-1
       Algorithms       Nielit STA 17-12-2017
Question 197 Explanation: 
→ To merge two lists of size m and n, we need to do m+n-1 comparisons in worst case.
→ 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 198
Which of the following algorithms use recursion for sorting an array of integers?
A
Bubble sort and Insertion sort
B
Bubble sort and Quicksort
C
Bubble sort and merge sort
D
Quicksort and merge sort
       Algorithms       Sorting       KVS 22-12-2018 Part-B
Question 198 Explanation: 
Recursion is used in 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 199
Consider the following C code segment:
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?
A
T(n) = O(​ √n) and T(n) = Ω​ ( √n)
B
T(n) = O(​ √n) and T(n) = ​ Ω ​(1)
C
T(n) = O(n) and T(n) = ​ Ω ​ ( ​ √n)
D
None of the above
       Algorithms       Asymptotic-Complexity       Nielit Scientific Assistance CS 15-10-2017
Question 199 Explanation: 
Then the time complexity is Best Case : Ω(1) & Worst Case: O(√n)
Question 200
Which of the following algorithm solve the all pair shortest path problem?
A) Dijkstra's algorithm
B) Floyd's algorithm
C) prim's algorithm
D) Warshall's algorithm
A
Both A and B
B
Both A and C
C
Both C and D
D
Both B and D
       Algorithms       Dynamic-Programming       Nielit Scientific Assistance CS 15-10-2017
Question 200 Explanation: 
The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem. The problem is to find shortest distances between every pair of vertices in edge weighted directed Graph.
Question 201
An algorithm is made up of two modules M1 and M2. If order of M1 is f(n) and M2 is g(n) then the order of algorithm is
A
max(f(n),g(n))
B
min(f(n),g(n))
C
f(n)+g(n)
D
f(n) * g(n)
       Algorithms       Asymptotic-Complexity       Nielit Scientific Assistance CS 15-10-2017
Question 201 Explanation: 
In this problem, we have to check all possibilities.


So, we will prefer max(f(n),g(n)).
Question 202
The running time of an algorithm T(n),where 'n' is the input size, is given by
T(n)=8T(n/2)+qn, if n>1
=p, if n=1
Where p,q are constants. The order of this algorithm is
A
n​ 2
B
n​ n
C
n​ 3
D
N
       Algorithms       Recurrences       Nielit Scientific Assistance CS 15-10-2017
Question 202 Explanation: 
The above recurrence is in the form of masters theorem.
Case-1: a>bk
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 203

Consider an array with n elements. Which of the following options gives the maximum number of swap(aj, aj+1) operations to sort the array elements using efficient bubble sort algorithm?

A
n2 /2
B
n(n-1)/2
C
n2
D
n(n+1)/2
       Algorithms       Sorting       JT(IT) 2018 PART-B Computer Science
Question 203 Explanation: 
→ The worst case is if the array is already sorted but in descending order.
→ 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 (n-1)+ ... + 2 + 1.
= (n*(n-1))/2
= O(n2)
Question 204
The question is based on the following program fragment.
f(int Y[10], int x)
{
int u,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k] i=k;
else
j=k;
}while((Y[k]!=x) && (i if(Y[k] ==x)
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?
A
Y is [1 2 3 4 5 6 7 8 9 10] and x<10
B
Y is [1 3 5 7 9 11 13 15 17 19] and x<1
C
Y is [ 2 2 2 2 2 2 2 2 2 2] and x>2
D
Y is [ 2 4 6 8 10 12 14 16 18 20] and 2
       Algorithms       Searching       Nielit Scientific Assistance CS 15-10-2017
Question 204 Explanation: 
This above code is similar to binary search
First iteration:
I=0,j=9
K=(0+9)/2=4
Elements with duplicate values of “2” the condition if(Y[k] Second iteration :
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 205
Which of the following search algorithm requires a sorted array?
A
Linear search
B
Hash search
C
Binary search
D
All of these
       Algorithms       Sorting       KVS DEC-2013
Question 205 Explanation: 
→ Linear search , in which elements are searched element by element.
→ 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 206
Sorting is
A
A process of rearranging a given set of objects in a specific order
B
To facilitate the later search for members of the sorted set
C
Is a relevant and essential activity, particularly in data processing
D
All of these
       Algorithms       Sorting       KVS DEC-2013
Question 206 Explanation: 
Sorting is any process of arranging items systematically, and has two common, yet distinct meanings:
● 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 207
The figure below represent a ____ sort
A
Bubble
B
Shake
C
Tree
D
Insertion
       Algorithms       Sorting       KVS DEC-2013
Question 207 Explanation: 
Bubble sorting is a simple sorting algorithm that repeatedly steps through the list, compares adjacent pairs and swaps them if they are in the wrong order.
Question 208
He diagram below represents a solution to the
A
Knight's tour
B
Eight Queens problem
C
Kings problem
D
Rooks problem
       Algorithms       Back-Tracking       KVS DEC-2013
Question 208 Explanation: 
● The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal.
● The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking 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 209
Which of the following sorting algorithms uses recursion?
A
Insertion sort
B
Heap sort
C
Merge sort
D
Bubble sort
       Algorithms       Sorting       KVS DEC-2017
Question 209 Explanation: 
Recursion uses two sorting algorithms for reducing time complexity.
1. Mergesort
2. Quicksort.
Question 210

For the recurrence relation T(n) = 2 + T(n - 1), where T(0)=2, T(n)=?

A
n2
B
2n+2
C
log(n)
D
2n
       Algorithms       Recurrences       JT(IT) 2016 PART-B Computer Science
Question 210 Explanation: 
T(n) = T(n-1)+ 1
T(0) = 1
T(n-1) = T(n-1-1)+1
T(n) = [T(n-2)+1] +1 = T(n-2)+ 2
T(n-2) = T(n-2-1)+1
T(n) = [T(n-3)+1]+1
= T(n-3)+3
= T(n) = T(n-k)+ k
Note: Let k = n
Then T(n) = T(0) + n = 1 + n
∴ O(n)
Question 211

Travelling salesperson problem belongs to which category of problems?

A
Satisfiable
B
Non Solvable
C
Decision
D
Optimization
       Algorithms       Dynamic-Programming       JT(IT) 2016 PART-B Computer Science
Question 211 Explanation: 
It uses dynamic programming. So, Travelling salesperson problem belongs to optimization category.
Question 212
The complexity of linear search algorithm is
A
O(nlogn)
B
O(n)
C
O(logn)
D
O(n*n)
       Algorithms       Searching       KVS DEC-2017
Question 212 Explanation: 
→ Linear search algorithm will traverse all nodes with increment by one element in linear fashion(order).
→ So, it takes time complexity O(n)
Question 213
The maximum number of comparisons for a particular record among 32 sorted recorder through binary search method will be
A
2
B
10
C
8
D
5
       Algorithms       Searching       KVS DEC-2017
Question 213 Explanation: 
Step-1: Binary search we are using formula O(log​ 2​ n)
Sep-2: 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 214
Consider an array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i<=n), the index of the parent is:
A
floor ((i+1)/2)
B
ceiling ((i+1)/2)
C
floor (i/2)
D
ceiling (i/2)
       Algorithms       Sorting       UGC NET CS 2017 Nov- paper-2
Question 214 Explanation: 
Parent Node is at index: ⌊i/2⌋
Left Child is at index: 2i
Right child is at index: 2*i+1
Question 215
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16 What is the height of the binary search tree ?
A
3
B
4
C
5
D
6
       Algorithms       Searching       UGC NET CS 2017 Nov- paper-2
Question 215 Explanation: 

Height of the binary search tree = 3
Question 216
Let G be an undirected connected graph with distinct edge weight. Let Emax be the edge with maximum weight and E​ min​ the edge with minimum weight. Which of the following statements is false?
A
Every minimum spanning tree of G must contain E​ min.
B
If E​ max​ is in minimum spanning tree, then its removal must disconnect G.
C
No minimum spanning tree contains E​ max.
D
G has a unique minimum spanning tree.
       Algorithms       Minimum-Spanning-Tree       UGC NET CS 2017 Nov- paper-2
Question 216 Explanation: 

Minimum Spanning Tree:
Question 217
A list of n strings, each of length n, is sorted into lexicographic order using merge – sort algorithm. The worst case running time of this computation is :
A
O(n log n)
B
O(n​ 2​ log n)
C
O(n​ 2​ + log n)
D
O(n​ 3​ )
       Algorithms       Sorting       UGC NET CS 2017 Nov- paper-2
Question 217 Explanation: 
1.The comparison is strictly follow the Dictionary based order.
2.The length of the string is n, the time taken is to be O(n) for each comparison.
3. For level -1(bottom-up order): Every element has to be compared with other element the number of comparisons is O(n/2).
4. For level -1(bottom-up 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 218
Given the array: 12,40,3,2 and intermediate states of the array while sorting
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
A
Insertion sort
B
Selection sort
C
Quick sort
D
Bubble sort
       Algorithms       Sorting       KVS 30-12-2018 Part B
Question 218 Explanation: 
→In the bubble sort, We will compare the two adjacent elements and swap the elements if first element is large.
→The above stages Bubble sort First Pass/ iteration steps.
→In the bubble sort, after completion the largest element gets last position.
Question 219
A and B are two sorted lists of integers such that A[n]<B[1]. An element is to be searched in both lists. Maximum number of comparisons using binary search is
A
2*log2 n
B
log2 2n
C
log2 (2n+1)
D
2*log2 n+1
       Algorithms       Searching       KVS 30-12-2018 Part B
Question 219 Explanation: 
In general, if N is the size of the list to be searched and C is the number of comparisons to do so in the worst case, C = log2N. In the question two sorted list of elements with the condition A[n]22N
Question 220
Postorder traversal of a given binary search tree T produces following sequence of keys:3, 5, 7, 9, 4, 17, 16, 20, 18, 15, 14 Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?
A
3, 4, 5, 7, 9, 14, 20, 18, 17, 16, 15
B
20, 18, 17, 16, 15, 14, 3, 4, 5, 7, 9
C
20, 18, 17, 16, 15, 14, 9, 7, 5, 4, 3
D
3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20
       Algorithms       Searching       UGC NET CS 2017 Nov- paper-2
Question 220 Explanation: 
We can easily find solutions based on given options because option D given all numbers in ascending order. In Order will print ascending order only.
Question 221
Let us assume that you construct ordered tree to represent the compound ​ proposition (~ (p ∧ q)) ↔ (~ p ∨ ~ q) Then, the prefix expression and post-fix​ expression determined using this ordered tree are given as ____ and _____ respectively.
A
↔~∧pq∨ ~ ~ pq, pq∧~p~q~∨↔
B
↔~∧pq∨ ~ p~q, pq∧~p~q~∨↔
C
↔~∧pq∨ ~ ~ pq, pq∧~p~~q∨↔
D
↔~∧pq∨ ~ p~ q, pq∧~p~ ~q∨↔
       Algorithms       Trees       UGC NET CS 2016 Aug- paper-2
Question 221 Explanation: 
Step-1: Given compound proposition is
(~(p ∧ q))↔(~ p ∨ ~ q)
It is clearly specifying that
↔ is a root
(~(p ∧ q)) is left subtree
(~p ∨ ~q) is right subtree.
Step-2: Finally the tree is looks like

Step-3: Prefix operation traverse through Root,left and Right ↔~∧pq∨ ~ p~q Step-4: Postfix operation traverse through Left,Right and Root.
pq∧~p~q~∨↔
Question 222
The runtime for traversing all the nodes of a binary search tree with n nodes and printing them in an order is:
A
O(lg n)
B
O(n lg n)
C
O(n)
D
O(n​ 2​ )
       Algorithms       Searching       UGC NET CS 2016 Aug- paper-2
Question 222 Explanation: 
Possibility-1:
→ 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).
Possibility-2:
Without sorted elements chance to form either left skewed or right skewed tree. It takes worst case time complexity is O(n).
Question 223
In general, in a recursive and non-recursive implementation of a problem (program) :
A
Both time and space complexities are better in recursive than in non-recursive program.
B
Both time and space complexities are better in non-recursive than in recursive program
C
Time complexity is better in recursive version but space complexity is better in non-recursive version of the program.
D
Space complexity is better in recursive version but time complexity is better in non-recursive version of the program.
       Algorithms       Time-Complexity       UGC NET CS 2015 Dec- paper-2
Question 223 Explanation: 
Both time and space complexities are better in non-recursive than in recursive program. We can also call non-recursive programs are iterative programs. Iterative programs time and space complexity is better than recursive 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 224
In the following graph, discovery time stamps and finishing time stamps of Depth First Search (DFS) are shown as x/y, where x is discovery time stamp and y is finishing time stamp.

It shows which of the following depth first forest?
A
{a, b, e} {c, d, f, g, h}
B
{a, b, e} {c, d, h} {f, g}
C
{a, b, e} {f, g} {c, d} {h}
D
{a, b, c, d} {e, f, g} {h}
       Algorithms       Depth-first-search       UGC NET CS 2015 Dec- paper-2
Question 224 Explanation: 
A DFS starting at some vertex ‘v’ explores the graph by building up a tree that contains all vertices that are reachable from ‘v’ and all edges that are used to reach these vertices. We call this tree a DFS tree. A complete DFS exploring the full graph (and not only the part reachable from a given vertex ‘v’) builds up a collection of trees, or forest, called a DFS forest.
Based on definition of DFS forest, option-A is correct.
Question 225
An ideal sort is an in-place-sort whose additional space requirement is __________.
A
O (log​ 2​ n)
B
O (n log​ 2​ n)
C
O (1)
D
O (n)
       Algorithms       Sorting       UGC NET CS 2015 Dec- paper-2
Question 225 Explanation: 
The ideal sorting algorithm would have the following properties:
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 226
A
B
C
D
       Algorithms       Minimum-Spanning-Tree       UGC NET CS 2015 Jun- paper-2
Question 226 Explanation: 
To find minimum cost spanning tree, we are using either prim’s algorithm (or) kruskal’s algorithm.
According to kruskal’s algorithm, first we have sort an elements.
Elements are: 10,12,14,16,18,22,24,25,28
Question 227
The average case occurs in the linear search algorithm when:
A
The item to be searched is in somewhere middle of the array
B
The item to be searched is not in the array
C
The item to be searched is in the last of the array
D
The item to be searched is either in the last or not in the array
       Algorithms       Searching       UGC NET CS 2015 Jun- paper-2
Question 227 Explanation: 
→ A linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.
→ 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 228
To determine the efficiency of an algorithm the time factor is measured by:
A
Counting microseconds
B
Counting number of key operations
C
Counting number of statements
D
Counting kilobytes of algorithm
       Algorithms       Time-Complexity       UGC NET CS 2015 Jun- paper-2
Question 228 Explanation: 
To determine the efficiency of an algorithm the time factor is measured by counting number of key operations.
Question 229
Which of the following algorithms sort n integers, having the range 0 to (n​ 2​ - 1), in ascending order in O(n) time ?
A
Selection sort
B
Bubble sort
C
Radix sort
D
Insertion sort
       Algorithms       Sorting       UGC NET CS 2015 Jun- paper-2
Question 229 Explanation: 
Consider sorting n integers in the range 0 to n​ 2​ - 1. We do it in two phases.
Phase 1:
1. We use n bins, one for each of the integers 0,1,.., n-1. 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 230
How much extra space is used by heapsort ?
A
O(1)
B
O(Log n)
C
O(n)
D
O(n​ 2​ )
       Algorithms       Sorting       UGC NET CS 2004 Dec-Paper-2
Question 230 Explanation: 
→ Heap sort uses Max-Heapify function which calls itself but it can be made using a simple while loop and thus making it an iterative function which intern takes no space. So, the space complexity of Heap Sort can be reduced to O(1)
→ 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 231
Which algorithm has same average, worst case and best case time ?
A
Binary search
B
Maximum of n number
C
Quick sort
D
Fibonacci search
       Algorithms       Time-Complexity       UGC NET CS 2006 Dec-paper-2
Question 231 Explanation: 
Question 232
You have to sort a list L, consisting of a sorted list followed by a few ‘random’ elements. Which of the following sorting method would be most suitable for such a task ?
A
Bubble sort
B
Selection sort
C
Quick sort
D
Insertion sort
       Algorithms       Sorting       UGC NET CS 2014 Dec-Paper-2
Question 232 Explanation: 
Here, they given sorted list followed by a few ‘random’ elements.
So, we can eliminate option-B and Option-C 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 233
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
I= depth limit
A
(a)-(iii), (b)-(ii), (c)-(iv), (d)-(i)
B
(a)-(ii), (b)-(iii), (c)-(iv), (d)-(i)
C
(a)-(i), (b)-(ii), (c)-(iv), (d)-(iii)
D
(a)-(i), (b)-(iii), (c)-(iv), (d)-(ii)
       Algorithms       Time-Complexity       UGC NET CS 2018-DEC Paper-2
Question 233 Explanation: 
BFS → O( b d ) worst case space complexity
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 234
Match List 1 with List 2 and choose the correct answer from the code given below
A
(a)-(iv), (b)-(iii), (c) -(ii), (d)-(i)
B
(a)-(i), (b)-(iv), (c) -(iii), (d)-(ii)
C
(a)-(iv), (b)-(i), (c) -(ii), (d)-(iii)
D
(a)-(i), (b)-(ii), (c) -(iii), (d)-(iv)
       Algorithms       Artificial-intelligence-algorithms       UGC NET CS 2018-DEC Paper-2
Question 234 Explanation: 
→ ​ Greedy Best-first Search:​ Selects a node for expansion if optimal path to that node has been found. Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule. Best-first search as estimating the promise of node n by a "heuristic evaluation function f(n) which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain."
→ ​ A* Search:​ Time complexity depends upon the quality of heuristic.
→ ​ Recursive Best-First 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.
→ ​ Iterative-deepening A* Search:​ Avoids substantial overhead associated with keeping the sorted queue of nodes
Question 235
In a ternary tree, the number of internal nodes of degree 1,2 and 3 is 4,3 and 3 respectively. The number of leaf nodes in the ternary tree is
A
11
B
12
C
10
D
9
       Algorithms       Trees       UGC NET CS 2018-DEC Paper-2
Question 235 Explanation: 
Number of internal nodes= 4+3+3= 10
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​ : nd-n +1 where ​ n ​ is number of nodes and d ​ is degree of the tree.
Question 236
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
A
13
B
16
C
17
D
14
       Algorithms       Graphs       UGC NET CS 2018-DEC Paper-2
Question 236 Explanation: 

The weight of this minimum spanning tree is 16.
Question 237
Big-O estimates for the factorial function and the logarithm of the factorial function i.e. n! and log n! is given by
A
O(n!) and O(n log n)
B
O(nn) and O(n log n)
C
O(n!) and O(log n!)
D
O(nn) and O(log n!)
       Algorithms       Time-Complexity       UGC NET CS 2014 June-paper-2
Question 237 Explanation: 
→ Given factorial function is n!. we can also write into nn. When we are writing into asymptotic order also the value remains same O(nn).
→ Given logarithm of the factorial function log n!.
= log n! (or)
= log nn (or)
= nlogn
When we are writing into asymptotic order also the value remains same O(nlogn).
Question 238
The second smallest of n elements can be found with _______ comparisons in worst case.
A
n + ceil(lg n) -2
B
n-1
C
lg n
D
3n/1
       Algorithms       Time-Complexity       UGC NET CS 2018-DEC Paper-2
Question 238 Explanation: 

This takes n-1 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)+log​ 2​ (n)-1
Example: 512 elements
In this case no. of comparisons will be, (512-1)+log​ 2​ (512) -1
=511+(9-1)
=511+8
=519
Question 239
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
A
4
B
2
C
3
D
5
       Algorithms       LCS       UGC NET CS 2018-DEC Paper-2
Question 239 Explanation: 

Possible subsequences are :130, 1210, 1301 and length of longest common subsequence is 4.
Question 240
Consider the midpoint (or Bresenham) algorithm for rasterizing lines given below :
(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.
A
Q and R only
B
P only
C
P and Q only
D
P,Q and R
       Algorithms       Bresenham       UGC NET CS 2018-DEC Paper-2
Question 240 Explanation: 
From the code given in question gives information that the algorithm will work if d is ever 0, So the statement R is false.
Line 10 and 12 will update the value of d , So the statement Q is true.
Question 241
In PERT/CPM, the merge event represents___________ of two or more events.
A
splitting
B
completion
C
beginning
D
joining
       Algorithms       PERT/CPM        UGC NET CS 2018-DEC Paper-2
Question 241 Explanation: 
→ The program (or project) evaluation and review technique (PERT) is a statistical tool used in project management, which was designed to analyze and represent the tasks involved in completing a given project.
→ The critical path method (CPM), or critical path analysis (CPA), is an algorithm for scheduling a set of project activities. It is commonly used in conjunction with the program evaluation and review technique (PERT).
→ A critical path is determined by identifying the longest stretch of dependent activities and measuring the time required to complete them from start to finish.
→ ​ Event: An event represents a point in time signifying the completion of some activities and the beginning of new ones. This is usually represented by a circle in a network which is also called a node or connector. The events are classified into three categories
1. Merge event – When more than one activity comes and joins an event such an event is known as merge event.
2. Burst event – When more than one activity leaves an event such an event is known as burst event.
3. Merge and Burst event – An activity may be merge and burst event at the same time as with respect to some activities it can be a merge event and with respect to some other activities it may be a burst event.
Question 242
​The solution of recurrence relation : T(n)=2T(sqrt(n))+lg(n) is
A
O(lg (n) lg(n))
B
O(lg (n))
C
O(n lg (n))
D
O(lg (n) lg(lg(n)))
       Algorithms       Recurrences       UGC NET CS 2018-DEC Paper-2
Question 242 Explanation: 

T (n) = l og log (n) · l og (n)
T (n) = l og(n) · l og log (n)
Question 243
Mergesort makes two recursive calls. Which statement is true after these two recursive calls finish, but before the merge step ?
A
The array elements form a heap.
B
Elements in each half of the array are sorted amongst themselves.
C
Elements in the first half of the array are less than or equal to elements in second half of the array.
D
All of the above
       Algorithms       Sorting       UGC NET CS 2014 June-paper-2
Question 243 Explanation: 
A merge sort works as follows:
→Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
→Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.
As per the merge sort, The elements in each half of the array are sorted amongst themselves.
Question 244
An algorithm is made up of 2 modules M1 and M2. If time complexity of modules M1 and M2 are h(n) and g(n) respectively, the time complexity of the algorithm is
A
min(h(n), g(n))
B
max(h(n), g(n))
C
h(n) + g(n)
D
h(n) * g(n)
       Algorithms       Time-Complexity       UGC NET CS 2014 June-paper-2
Question 244 Explanation: 
→ The time complexity of modules M1 and M2 are h(n) and g(n).
Let take some constants c1, c2, n1, n2 such that
T(n) ≤ c1*h(n), for all n≥n1.
T(n) ≤ c2 *h(n), for all n ≥ n2.
N=max(n1, n2) and C=max(c1, c2).
So,
T(n)≤C * h(n) for all n≥N
T(n)≤C * g(n) for all n≥N
T(n)≤C/2 * (h(n)+g(n))
Without loss of generality, let max(h(n), g(n))=h(n) .
So, T(n)≤C/2 (h(n)+h(n))≤C*h(n) .
So, complexity of h(n) is max(h(n), g(n))
Question 245
The amortized time complexity to perform ______ operation(s) in Splay trees is O(lg n).
A
Search
B
Search and Insert
C
Search and Delete
D
Search, Insert and Delete
       Algorithms       Time-Complexity       UGC NET CS 2013 Sep-paper-2
Question 245 Explanation: 
→ Amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case run time per operation, rather than per algorithm, can be too pessimistic.

Search (or) Find: For the Search (or) Find operation, we perform a normal BST find followed by a splay operation on the node found (or the leaf node last encountered, if the key was not found). We can charge the cost of going down the tree to the splay operation. Thus the amortized cost of find is O(log n).
Insert/delete: The amortized cost of the splay operation is also O(log n), and thus the amortized cost of insert/delete is O(log n).
Question 246
Suppose that the splits at every level of Quicksort are in proportion 1-β to β, where 0 < β ≤ 0.5 is a constant. The number of elements in an array is n. The maximum depth is approximately
A
0.5 β Ig n
B
0.5 (1 – β) Ig n
C
– (Ig n)/(Ig β)
D
– (Ig n)/Ig (1 – β)
       Algorithms       Sorting       UGC NET CS 2013 Sep-paper-2
Question 247
The solution of the recurrence relation T(m)=T(3m/4)+1 is :
A
θ(lg m)
B
θ(m)
C
θ(mlg m)
D
θ(lglg m)
       Algorithms       Asymptotic-Complexity       UGC NET CS 2018 JUNE Paper-2
Question 247 Explanation: 
Using Masters Method:
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 248
Which of the following algorithms solves the single-source shortest paths ?
A
Prim’s algorithm
B
Floyd - Warshall algorithm
C
Johnson’s algorithm
D
Dijkstra’s algorithm
       Algorithms       Greedy-approach       UGC NET CS 2018 JUNE Paper-2
Question 248 Explanation: 
Dijkstra’s algorithm is a Single source shortest path algorithm used to find the shortest path using Greedy approach.
Question 249
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 :
A
2.4
B
1.87
C
3.0
D
2.15
       Algorithms       Greedy-approach       UGC NET CS 2018 JUNE Paper-2
Question 249 Explanation: 

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 (4-bits)
E = 1001 (4-bits)
D = 101 (3-bits)
C = 11 (2-bits)
B = 0 (1-bit)
Average length = ((0.08×4)+(0.12×4)+(0.15×3)+(0.25×2)+(0.40×1)) / (0.08+0.12+0.15+0.25+0.40)
=2.15/1.0
= 2 .15
Question 250
Match the following with respect to algorithm paradigms :
A
(a)-(iv),(b)-(i), (c)-(iii), (d)-(ii)
B
(a)-(iv),(b)-(iii), (c)-(i), (d)-(ii)
C
(a)-(iii),(b)-(iv), (c)-(ii), (d)-(i)
D
(a)-(iv),(b)-(iii), (c)-(ii), (d)-(i)
       Algorithms       Dynamic-Programming-and-Greedy-approach       UGC NET CS 2018 JUNE Paper-2
Question 250 Explanation: 
8-Queens problem use Backtracking
Single-Source shortest paths use Greedy approach
STRASSEN’s Matrix multiplication use Divide and conquer technique
Optimal binary search trees use Dynamic programming
Question 251
The maximum number of comparisons needed to sort 9 items using radix sort is (assume each item is 5 digit octal number) :
A
45
B
72
C
360
D
450
       Algorithms       Sorting       UGC NET CS 2018 JUNE Paper-2
Question 251 Explanation: 
Total sort items=9
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 252
Big – O estimate for f(x) = (x+1) log(x2+1)+3x2 is given as
A
O(x log x)
B
O(x2)
C
O(x3)
D
O(x2 log x)
       Algorithms       Asymptotic-Complexity       UGC NET CS 2013 Dec-paper-2
Question 252 Explanation: 
f(x) = (x+1) log(x2+1)+3x2 in this function, 3x2 is leading term. So, we can call asymptotically O(n2).
Question 253
The total number of comparisons in a bubble sort is
A
0(log n)
B
0(n log n)
C
0(n)
D
None of the above
       Algorithms       Sorting       UGC NET CS 2011 Dec-Paper-2
Question 253 Explanation: 
The total number of comparisons in a bubble sort is O(n2)
Question 254
Give as good a big–O estimate as possible for the following functions : (nlogn+n2)(n3+2) and (n!+2n)(n3+log(n2+1))
A
O(n5+2n2) & O(n3*n!)
B
O(n5) & O(n3*2n)
C
O(n5) & O(n3* n!)
D
O(n5+2n2) & O(n3*2n)
       Algorithms       Asymptotic-Complexity       UGC NET CS 2013 June-paper-2
Question 254 Explanation: 
Step-1: Consider first function (nlogn+n2)(n3+2).
Here, It is performing multiplication of 2 polynomials.
(nlogn+n2) → Raising value is n2. We can write asymptotically O(n2)
(n3+2) → Raising value is n3. We can write asymptotically O(n3)
= O(n2)*O(n3)
= O(n5)
Step-2: Second function (n!+2n)(n3+log(n2+1))
Here, It is performing multiplication of 2 polynomials.
(n!+2n) → Raising value is n!. We can write asymptotically O(n!)
(n3+log(n2+1)) → Raising value is n3. We can write asymptotically O(n3)
= O(n!)*O(n3)
= O(n3* n!)
Question 255
Which of the following connected simple graph has exactly one spanning tree ?
A
Complete graph
B
Hamiltonian graph
C
Euler graph
D
None of the above
       Algorithms       Minimum-Spanning-Tree       UGC NET CS 2013 June-paper-2
Question 255 Explanation: 
→ Complete graph have nn-2 spanning trees.
→ Hamiltonian graph will get more than one spanning tree.
→ Euler graph will get more than one spanning tree.
Question 256
Which of the following is not primitive recursive but computable ?
A
Carnot function
B
Riemann function
C
Bounded function
D
Ackermann function
       Algorithms       Ackermann-function       NIELIT Technical Assistant_2016_march
Question 257
The total number of spanning trees that can be drawn using five labelled vertices is :
A
125
B
64
C
36
D
16
       Algorithms       Minimum-Spanning-Tree       UGC NET CS 2008 Dec-Paper-2
Question 257 Explanation: 
To find total number of spanning trees we are using a standard formula is nn-2.
n=5
=55-2
=53
=125
Question 258
Ball Mart has 10 7 different items in stock across all its stores worldwide. The company has collected billing data for 10 10 customer transactions. Each individual bill has at most 10 distinct items in it. Ball Mart’s CEO wants to optimize the company’s inventory and has asked for a list of those items that appear in at least 2% of the billed transactions. Which of the following is the most precise upper bound one can compute for the number of such items, given the data?
A
500
B
1000
C
5000
D
20000
       Algorithms       Time-Complexity       CHENNAI MATHEMATICAL INSTITUTE (M.Sc. / Ph.D. Programme in Computer Science)15 May 2013
Question 258 Explanation: 
An item that is in 2% of the bills must appear in 2 × 10 8 bills. Across all bills, there are at most (10 10 ) × 10 = 10 11 items mentioned. So at most (10 11 )/(2 × 10 8 ) = 500 items can appear in 2% of the bills. The number of items in stock is irrelevant.
Question 259
You have n lists, each consisting of m integers sorted in ascending order. Merging these lists into a single sorted list will take time:
A
O(nm log m)
B
O(mn log n)
C
O(m + n)
D
O(mn)
       Algorithms       Sorting       CHENNAI MATHEMATICAL INSTITUTE (M.Sc. / Ph.D. Programme in Computer Science)15 May 2013
Question 259 Explanation: 
We can merge two sorted lists of size k and ` in time O(k + `). We begin by merging the lists in pairs to generate n /2 lists of size 2m each, in total time O(mn). If we repeat this, we get n/ 4 lists of size 4m each, again in total time O(mn). Thus, in O(log n) rounds, we converge to a single sorted list. Each round takes time O(mn), so the total time is O(mn log n).
Another strategy to achieve complexity O(mn log n) is to build a min-heap of size n, consisting the first element in each of the n lists. We then extract the minimum element from the heap to the output and replace it in the heap with the next element from the list from which the minimum came. Thus, it takes time O(log n) to generate each element in the output and there are O(mn) output elements in all, so the overall time is O(mn log n).
On the other hand, if we can apply min() to n elements at a time, we can merge all n lists is parallel. Let the n lists be ` l1 , `l 2 , . . . , `l n . We maintain indices i 1 , i 2 , . . . , i n into these n lists, initially set to 1. At each stage we add j = min(` l1 [i 1 ], ` l2 [i 2> ], . . . , ` ln [i n ]) to the sorted output list and increment the corresponding index. Overall, we add mn elements to the sorted output and each element is generated in constant time, so the time taken is O(mn).
Question 260
You are given two sorted lists of integers of size m and n. Describe a divide and conquer algorithm for computing the k th smallest element in the union of the two lists in time O(log m + log n).
A
Descriptive Explanation
       Algorithms       Sorting       CHENNAI MATHEMATICAL INSTITUTE (M.Sc. / Ph.D. Programme in Computer Science)15 May 2013
Question 260 Explanation: 
Note that k is treated as a constant in this problem.
First of all, the question is interesting only if the lists have duplicate elements. Other- wise, we just merge the two lists as usual and after k steps we have the answer.
Let us first solve a simpler problem and find the k th smallest number in a single sorted list of length n. The first number in the list is clearly the smallest number. Let us call this number x 1 . The next number must be at least x 1 +1, so we search for x 1 +1 in the list using binary search. (Recall that binary search is an example of divide and conquer.) Either we find the number, in which case the second smallest number x 2 is x 1 +1, or we fail to find it, in which case we will be at a boundary between the last occurrence of x 1 and the first occurrence of the next smaller number, which is x 2 . We now search for x 2 +1 and discover x 3 . Repeat this k−1 times to find x k . Each binary search takes time log n, so overall this procedure takes time k log n, which is O(log n) if we treat k as a constant.
If we have two lists, we can find the first k numbers in the first list, which takes time O(log m) and then find the first k numbers in the second list, which takes time O(log n) and then merge these in time O(k) (which is a constant!) to find the k th smallest number overall.
In fact, we can reduce the number of binary searches to k and avoid the merge step. Maintain indices i 1 and i 2 for the two lists, pointing initially to the first element in lists 1 and 2, respectively. At each stage, the smaller of the numbers pointed to by i 1 and i 2 is the next number to be enumerated. We then advance i 1 or i 2 , as the case may be, using binary search as described above. After k such steps, we would have found the k th smallest number overall. Some steps may involve a binary search in list 1, which takes time O(log m) and others may involve a binary search in list 2, which takes time O(log n), so each step is bounded by max(O(log m), O(log n)). This gives an overall complexity of max(O(log m), O(log n)), which is equivalent to O(log m + log n).
Question 261
You are going abroad and you have to complete a number of formalities before you leave. Each task takes a full day to complete. Fortunately, you have an army of friends to help you and each task can be done by either you or any of your friends, so you can complete as many tasks as possible in parallel, on the same day. Some tasks depend on others: for instance, you cannot purchase foreign exchange till you have bought your ticket. If task B depends on task A, you can start B only after you complete A. A set of tasks with no pending dependencies can be completed in parallel. You are given a list of n such tasks to be completed, where each task comes with a set of other tasks that it depends on. The set of tasks is feasible: there are no circular dependencies. You want to compute the minimum number of days needed to complete all the tasks, given the constraints. (i) Model this problem formally using graphs. (ii) Describe an efficient algorithm for the problem and analyze the worst-case complexity of your algorithm.
A
Descriptive Explanation
       Algorithms       Time-Complexity       CHENNAI MATHEMATICAL INSTITUTE (M.Sc. / Ph.D. Programme in Computer Science)15 May 2013
Question 261 Explanation: 
(i) Construct a graph in which the tasks are the vertices and there is an edge (i, j) if task i must be completed before starting task j. This is a directed graph without cycles, so it is a directed acyclic graph (dag). Any path i 1 i 2 . . . i n of tasks would take a minimum of n days to complete because each edge in the path describes a dependency. Hence, the problem is one of finding the longest path in a dag.
(ii) In any dag, there must be some vertex with no incoming edge (indegree 0). Any vertex of indegree 0 represents a task that has no pending dependencies and can hence be immediately completed. Once it is completed, we can remove it from the graph and operate on the tasks that remain. The algorithm is thus the following.
• Initialize a counter c to 0.
• While the dag is not empty
– Remove all vertices of indegree 0
– Recompute indegrees of remaining vertices
– Increment c
The final value of c is the answer we seek.
The complexity of this algorithm depends on how we represent the graph. For G = (V, E) let |V | = n and |E| = m. If we use an adjacency matrix, for each vertex we remove, we have to scan a row of the matrix to determine which indegrees to decrement, so it will take time O(n 2 ). If we use adjacency lists, for each vertex we delete, we can scan its list of outgoing edges and directly decrement indegrees for its outgoing neighbours. Across the n vertices we delete, we scan each of the m edges once, so the overall time is O(n + m).
Question 262
Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. You hate to start or stop watching a match midway, so your aim is to watch as many complete matches as possible during the week. Suppose there are n such matches scheduled during the coming week and you know the starting and finishing time for each match. (i) Describe an efficient algorithm to compute the following: for each match, what is the next match whose starting time is strictly later than the finishing time of the current match? Analyze the worse-case complexity of your algorithm. (ii) Develop an algorithm based on dynamic programming to compute the maximum number of complete matches you can watch next week. Analyze the worse-case complexity of your algorithm.
A
Descriptive Explanation
       Algorithms       Dynamic-Programming       CHENNAI MATHEMATICAL INSTITUTE (M.Sc. / Ph.D. Programme in Computer Science)15 May 2013
Question 262 Explanation: 
(i) We can accumulate information about the matches in the order in which they appear in the TV schedule. Hence, we can assume that the starting times and ending times of the matches are recorded in two arrays B[1..n] and E[1..n], where B[i] and E[i] are the beginning and ending time, respectively, of match i and B is sorted in ascending order. For each match i, we use binary search in B to find the earliest match j such that E[i] ≤ B[j] and set Next[i] = j. We do n binary searches, so this takes time O(n log n).
(ii) Let Best[i] denote the maximum number of matches you can watch in the set {i, i + 1, . . . , n}. The overall answer we are looking for is Best[1].
Consider the set of matches {i, i + 1, . . . , n}. We have two options initially, and we must pick the better of the two.
• Watch match i. In this case, we get to watch one match immediately and as many matches as we can manage if we start with the match Next[i], so the overall number of matches is 1 + Best[Next[i]].
• Skip match i. In this case, the number of matches we get to watch is Best[i + 1].
Clearly Best[n] = 1 since there is no advantage in skipping the last match.
We can express this as a recurrence for Best[i] as follows, where Best[n] is the base case.
Best[i] = max(1 + Best[Next[i]], Best[i + 1])
Best[n] = 1
We can now start with the base case Best[n] = 1 and work backwards to compute Best[n − 1], Best[n − 2], . . . , Best[1] using dynamic programming, in time O(n).
Question 263
Suppose we have constructed a polynomial time reduction from problem A to problem B. Which of the following can we infer from this fact?
A
If the best algorithm for B takes exponential time, there is no polynomial time algorithm for A.
B
If the best algorithm for A takes exponential time, there is no polynomial time algorithm for B.
C
If we have a polynomial time algorithm for A, we must also have a polynomial time algorithm for B.
D
If we don’t know whether there is a polynomial time algorithm for B, there cannot be a polynomial time algorithm for A.
       Algorithms       P-NP       CHENNAI MATHEMATICAL INSTITUTE(M.Sc. / Ph.D. Programme in Computer Science) 18May 2015
Question 263 Explanation: 
If there were a polynomial time solution for B, we can use the reduction to obtain a polynomial time solution for A.
Question 264
You are given n positive integers, d 1 ≤ d 2 ≤ . . . ≤ d n , each greater than 0. Design a greedy algorithm to test whether these integers correspond to the degrees of some n-vertex simple undirected graph G = (V, E). (A simple graph has no self-loops and at most one edge between any pair of vertices.)
A
Descriptive Explanation
       Algorithms       Greedy-approach       CHENNAI MATHEMATICAL INSTITUTE(M.Sc. / Ph.D. Programme in Computer Science) 18May 2015
Question 264 Explanation: 
We will call a sequence graphical if it consists of the degrees of all the vertices in a graph. Thus the question asks for an algorithm to test whether a given nonincreasing sequence of length n is graphical. By the Havell-Hakimi theorem, a nonincreasing sequence s = (d 1 , d 2 , . . . , d n ) is graphical if and only if the sequence s 0 = (d 2 − 1, d 3 − 1, . . . , d d 1 +1 − 1, d d 1 +2 , . . . , d n ) is graphical. Noting that s 0 is a sequence of length n − 1, we are led to Algorithm 1.
Algorithm 1 Algorithm to check if a nonincreasing sequence is graphical
function IsGraphical(s)
Let the input sequence be s = (d 1 , d 2 , . . . , d n )
if d 1 = d 2 = · · · = d n<>/sub> = 0 then
return true
else if n = 1 and d 1 > 0 then
return false
else
Form the sequence s s' = (d 2 − 1, d 3 − 1, . . . , d d 1 +1 − 1, d d 1 +2 , . . . , d n )
Let s 00 be s 0 sorted in descending order
return IsGraphical(s' ' )
end if
end function
There are n recursive calls to the function IsGraphical, and the majority of the time in each call is spent in sorting the input sequence. Thus the algorithm takes time O(n 2 log n).
Question 265
There is a thin, long and hollow fibre with a virus in the centre. The virus occasionally becomes active and secretes some side products. The fibre is so thin that new side products secreted by the virus push the old products along the fibre towards its ends. The possible actions of the virus are as follows (a) Produce an acid molecule to its left and a base molecule to its right. (b) Produce a base molecule to its left and an acid molecule to its right. (c) Divide into two viruses, each of which continues to behave like its ancestor. (d) Die. You are given a sequence of acid and base molecules from one end of the fibre to the other end. Design an algorithm to check if a single virus could possibly have produced the given sequence. Use dynamic programming, checking smaller subsequences before checking bigger subsequences.
A
Descriptive Explanation
       Algorithms       Dynamic-Programming       CHENNAI MATHEMATICAL INSTITUTE(M.Sc. / Ph.D. Programme in Computer Science) 18May 2015
Question 265 Explanation: 

The language of the above grammar is the set of strings consisting of equal number of a’s and b’s.
A sequence of acid and base molecules is just a string over {a, b}. To check if a single virus could have produced the sequence, you can use CYK algorithm to check membership in the above context-free grammar.
Question 266
The complexity of Kruskal’s minimum spanning tree algorithm on a graph with ‘n’ nodes and ‘e ’ edges is :
A
O (n)
B
O (n log n)
C
O (e log n)
D
O (e)
       Algorithms       Minimum-Spanning-Tree       UGC NET CS 2008-june-Paper-2
Question 266 Explanation: 
MST-KRUSKAL(G,w)
1. A=∅
2. for each vertex v∈ G.V
3. MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v)∈G.E, taken in nondecreasing order by weight
6. if FIND-SET(u)≠FIND-SET(v)
7. A=A∪{(u,v)}
8. UNION(u,v)
9. return A
Analysis:
The running time of Kruskal’s algorithm for a graph G=(V,E) depends on how we implement the disjoint-set data structure.
→ Initializing the set A in line 1 takes O(1) time, and the time to sort the edges in line 4 is O(ElgE). (We will account for the cost of the |V| MAKE-SET operations in the for loop of lines 2–3 in a moment.)
→ The for loop of lines 5–8 performs O(E) FIND-SET and UNION operations on the disjoint-set forest.
→ Along with the |V| MAKE-SET operations, these take a total of O((V+E)α(V)) time, where α is the very slowly growing function.
→ Because we assume that G is connected, we have |E|>=|V|-1, and so the disjoint-set operations take O(Eα(V)) time.
→ Moreover, since α |V|=O(lg V)=O(lg E), the total running time of Kruskal’s algorithm is O(ElgE)
→ Observing that |E|<|V|2 , we have lg |E|=O(lg V), and so we can restate the running time of Kruskal’s algorithm as O(E lg V)
Question 267
Which of the following is true for a sorted list with ‘n’ elements ?
A
Insertion in a sorted array takes constant time.
B
Insertion in a sorted linear linked list takes constant time.
C
Searching for a key in a sorted array can be done in O(log n) time.
D
Searching for a key in a sorted linear linked list can be done in O(log n) time.
       Algorithms       Sorting       UGC NET CS 2008-june-Paper-2
Question 267 Explanation: 
TRUE: Searching for a key in a sorted array can be done in O(log n) time.
Because elements are in sorted order, we are using binary search tree. it will take worst case time complexity O(logn) only.
Question 268
A stable sort preserves the order of values that are equal with respect to the comparison function. We have a list of three dimensional points [(7, 1, 8), (3, 5, 7), (6, 1, 4), (6, 5, 9), (0, 2, 5), (9, 0, 9)]. We sort these in ascending order by the second coordinate. Which of the folllowing corresponds to a stable sort of this input?
A
[(9, 0, 9), (7, 1, 8), (6, 1, 4), (0, 2, 5), (6, 5, 9), (3, 5, 7)]
B
[(0, 2, 5), (3, 5, 7), (6, 1, 4), (6, 5, 9), (7, 1, 8), (9, 0, 9)]
C
[(9, 0, 9), (7, 1, 8), (6, 1, 4), (0, 2, 5), (3, 5, 7), (6, 5, 9)]
D
[(9, 0, 9), (6, 1, 4), (7, 1, 8), (0, 2, 5), (3, 5, 7), (6, 5, 9)]
       Algorithms       Sorting       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2017)
Question 268 Explanation: 
In a stable sort, the original order of the pairs (7,1,8),(6,1,4) and (3,5,7),(6,5,7) with equal second coordinates must be preserved in the sorted output.
Question 269
We have constructed a polynomial time reduction from problem A to problem B. Which of the following is a valid inference?
A
If the best algorithm for B takes exponential time, there is no polynomial time algorithm for A
B
If the best algorithm for A takes exponential time, there is no polynomial time algorithm for B.
C
If we have a polynomial time algorithm for A, we must also have a polynomial time algorithm for B.
D
If we don’t know whether there is a polynomial time algorithm for B, there cannot be a polynomial time algorithm for A.
       Algorithms       P-NP       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2017)
Question 269 Explanation: 
If we have a polynomial time solution for B, the reduction gives us a polynomial time solution for A.
Question 270
There are a number of tourist spots in a city and a company GoMad runs shuttle services between them. Each shuttle plies between a designated origin and destination, and has a name. Due to lack of coordination, the same name may be allotted to multiple routes. To make matters worse, another company GoCrazy introduces its shuttle services using the same set of shuttle names. A GoMad shuttle and a GoCrazy shuttle with the same name may start at different origins and/or end at different destinations. A pass from a company allows unlimited travel in all the company’s shuttles. For each company, we have a list that specifies all routes allotted to each shuttle name. Design an algorithm to find out if there is a source s, a target t, and a sequence of shuttle names σ such that, irrespective of whether you are carrying a GoMad pass or a GoCrazy pass, you can start at s and arrive at t using the sequence σ.
A
Descriptive Explanation
       Algorithms       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2017)
Question 270 Explanation: 
Create a graph where the set of vertices are pairs (Spot 1, Spot 2) of tourist spots. There is an edge labeled “Name 1” from (Spot 1, Spot 2) to (Spot 3, Spot 4) iff there is a GoMad shuttle “Name 1” from Spot 1 to Spot 3 and a GoCrazy shuttle “Name 1” from Spot 2 to Spot 4. The answer to the question is yes iff there is a directed path from a vertex (Spot 1, Spot 1) to a vertex (Spot 2, Spot 2).
Question 271
A
Descriptive Explanation
       Algorithms       Time-Complexity       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2017)
Question 271 Explanation: 
Compute two arrays A and B with A[i] and B[i] giving the length of the longest such sequence in (a 1 , b 1 ), . . . (a i , b i ) with a i and b i as the last elements, respectively.
Note that A[1] = 1 and B[1] = 1. To compute A[i] and B[i] for i ≥ 2, we first compute the following quantities:
Question 272
The time required to find shortest path in a graph with n vertices and e edges is :
A
O(e)
B
O(n)
C
O(e2)
D
O(n2)
       Algorithms       Greedy-approach       UGC NET CS 2007 June-Paper-2
Question 272 Explanation: 
→ We can use dijkstra’s algorithm to find shortest path in a graph with n vertices and e edges is O(ElogV).
→ We know that E ≤ V2 if graph is complete and time complexity is O(n2)
Question 273
Which algorithm has some average, worst case and best case time :
A
Binary search
B
Maximum of n numbers
C
Quick sort
D
Fibonacci search
       Algorithms       Time-Complexity       UGC NET CS 2007 June-Paper-2
Question 273 Explanation: 

Question 274
A group of war prisoners are trying to escape from a prison. They have thoroughly planned the escape from the prison itself, and after that they hope to find shelter in a nearby village. However, the village (marked as B, see picture below) and the prison (marked as A) are separated by a canyon which is also guarded by soldiers (marked as S). These soldiers sit in their pickets and rarely walk; the range of view of each soldier is limited to exactly 100 meters. Thus, depending on the locations of soldiers, it may be possible to pass the canyon safely, keeping the distance to the closest soldier strictly larger than 100 meters at any moment. The situation is depicted in the following picture, where the circles around S indicate range of view. Provide an algorithm to determine if the prisoners can pass the canyon unnoticed, given the width and the length of the canyon and the coordinates of every soldier in the canyon, and assuming that soldiers do not change their locations. (Hint: Model this as a graph, with soldiers represented by the vertices.)
A
Explanation
       Algorithms       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2016)
Question 274 Explanation: 
Consider a graph G = (V ∪ {N, S}, E) where V = {v s | s is a soldier}. N and S are two special vertices representing the north and south boundary of the canyon, respectively. For two soldiers s and s 0 , (v s , v s 0 ) ∈ E iff s and s 0 are at most 200 meters apart. For a soldier s, (v s , N ) ∈ E iff s is at most 100 meters from the north boundary, and similarly (v s , S) ∈ E iff s is at most 100 meters from the south boundary. It is clear that the prisoners cannot pass the canyon unnoticed iff there is a path between N and S. Thus it suffices to test reachability of S from N using any standard algorithm (for instance, one based on breadth-first search).
Question 275
An automatic spelling checker works as follows. Given a word w, first check if w is found in the dictionary. If w is not in the dictionary, compute a dictionary entry that is close to w. For instance if the user types ocurrance, the spelling checker should suggest occurrence, which belongs to the dictionary. Similarity between words such as occurrence and occurance is quantified in terms of alignment. An alignment between two strings w 1 and w 2 (over the alphabet {a, b, c, . . . , z}) is obtained by inserting hyphens in the two strings such that the modified strings align (i.e., the modified strings are of equal length, and at each position, either both strings have the same letter or one of the strings has a hyphen). Here are three examples of alignments. The first is between ocurrance and occurrence and the second and third are between ctatg and ttaagc. A mismatch in an alignment is a position where one of modified strings has a hyphen and the other does not. There are three mismatches in the first alignment given above, five mismatches in the second, and seven mismatches in the third. Use dynamic programming to give an efficient algorithm that takes two strings x and y (over the alphabet {a, b, c, . . . , z}) as its input, and computes the minimum number of mismatches among all alignments of x and y. What is the running time of your algorithm (in terms of the lengths of x and y)?
A
Explanation
       Algorithms       Dynamic-Programming       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2016)
Question 275 Explanation: 
Let x = a 1 a 2 · · · a m and y = b 1 b 2 · · · b n . For any string w and any i ∈ {0, . . . , |w|}, we let w[. . . i] denote the prefix of w of length i. For i ∈ {0, . . . , m} and j ∈ {0, . . . , n}, we let opt(i, j) denote the minimum number of mismatches among all alignments of x[. . . i] and y[. . . j]. It is easy to see that opt(0, j) = j and opt(i, 0) = i. When i, j > 0, an optimal alignment of x[. . . i] and y[. . . j] either aligns x[. . . i − 1] with y[. . . j − 1] and tries to match a i and b j (if possible), or aligns y[. . . j] with x[. . . i − 1], leaving a i unmatched, or aligns x[. . . i] with y[. . . j − 1], leaving b j unmatched.
This is reflected by the following recurrence :
opt(i, j) = min{opt(i − 1, j − 1) + c ij , opt(i − 1, j) + 1, opt(i, j − 1) + 1}.
where c ij denotes the cost of aligning a i (the string containing just the one letter) with b j . It is easy to see that

The following algorithm (which runs in O(mn) time) computes the minimum number of mismatches among alignments of x and y.
array A[0...m, 0...n]
array c[0...m, 0...n]
initialize A[i,0] = i for each i
initialize A[0,j] = j for each j
for j = 1,...,n
for i = 1,...,m
if a[i] == b[j] then c[i,j] = 0 else c[i,j] = 2
endfor
endfor
for j = 1,...,n
for i = 1,...,m
A[i,j] = min(A[i-1,j-1]+c[i,j], A[i-1,j]+1, A[i,j-1]+1)
endfor
endfor
return A[m,n]
Question 276
Air CMI operates direct flights between different cities. For any pair of cities A and B, there is at most one flight in a day from A to B. The online site FakeTrip is trying to compile a list of all routes available through Air CMI. (a) FakeTrip has a table of all direct flights operated by Air CMI. From this, it wants to prepare a list of all pairs of cities connected by a sequence of flights. Describe an algorithm for this and analyze the complexity of your algorithm. (b) CheapTricks is trying to enter the market by improving on FakeTrip. CheapTricks has realized that not all connections listed by FakeTrip are feasible because of arrival and departure constraints. A connection from A to B to C is possible if the scheduled arrival of the flight from A to B is at least one hour before the scheduled departure of the flight from B to C. Given a table of direct flights with scheduled arrival and departure times, describe an algorithm for CheapTricks to list all pairs of cities connected by a route on which all connections are feasible within the same day. Analyze the complexity of your algorithm.
A
Explanation
       Algorithms       Time-Complexity       CHENNAI MATHEMATICAL INSTITUTE - M.Sc. / Ph.D. Programme in Computer Science ( 15 May 2014 )
Question 276 Explanation: 
(a) Consider the directed graph G = (V, E), where V is the set of cities and (i, j) ∈ E if there is a direct flight from i to j. As usual let n be the number of vertices and m be the number of edges.
Let A be the adjacency matrix for G. A[i, j] = 1 iff there is a direct flight from i to j. The product matrix A × A = A 2 has the property that A 2 [i, j] > 0 iff there is a path of length 2 or less from i to j. In general A k has the property that A k [i, j] > 0 iff there is a path of length k or less from i to j. Given n cities, if i and j are connected by a path, the shortest path connecting them has length at most n−1, so it suffices to compute A n−1 . Multiplying two n × n matrices takes time O(n 3 ). We have to do this O(n) times, so O(n 4 ) overall.
Alternatively, use DFS or BFS from each vertex i to compute the set of cities reachable from i. Each DFS/BFS takes time O(n + m) and we repeat this n times, so this takes time O(n(n + m)).
(b) We can expand the graph to take into account arrival and departure times. Let V be the set of pairs (j, t) such that j is a city and there is a flight (i, j) from some city i to j that arrives at time t. In this graph, connect (i, t) to (j, t' ) if there is a flight from i to j that leaves from i at least one hour after t on the same day and arrives at j at time t'.
We can now use the DFS/BFS procedure of the previous part from each vertex (i, t) and collect together all pairs (i, j) such that for some t, t' , (j, t' ) is reachable from (i, t).
(We have assumed that every city has at least one incoming flight. If a city i does not have an incoming flight, make a single copy (i, 0) of the vertex.)
The number of vertices in the new graph is at most m, the number of edges in the original graph, since the number of copies we make of each vertex j is equal to its indegree, and the sum of all indegrees is the number of edges in the graph. (If two different flights arrive in j from different destinations at the same time, the vertices would be collapsed, so the number of vertices could be less than m).
Each outgoing edge (i, j) from i in the original graph would be duplicated at most as many times as there are X copies of i in the new graph. The number of edges in the new graph is at most indegree(i) · outdegree(i), for which an easy upper bound is m 2 . (This follows since ac + bd < (a + b)(c + d) for a, b, c, d > 0 and sum of the indegrees = sum of outdegrees = m.)
Thus, DFS/BFS in the new graph can be bounded by O(m(m + m 2 )) = O(m 3 )
.
Question 277
(a) Let A be an array of n integers, sorted so that A[1] ≤ A[2] ≤ · · · ≤ A[n]. You are given a number x. The aim is to find out if there are indices k and l such that A[k] + A[l] = x. Design an algorithm for this problem that works in time O(n). (b) Let A be array of n integers that is not assumed to be sorted. You are given a number x. The aim is to find out if there are indices k, l and m such that A[k] + A[l] + A[m] = x. Design an algorithm for this problem that works in time O(n 2 ).
A
Explanation
       Algorithms       Time-Complexity       CHENNAI MATHEMATICAL INSTITUTE - M.Sc. / Ph.D. Programme in Computer Science ( 15 May 2014 )
Question 277 Explanation: 
(a) Consider the two endpoints A[1] and A[n].
• If A[1] + A[n] > x, A[n] is useless since it cannot be paired with any number to achieve the sum—any sum A[i] + A[n], i > 1, will be greater than or equal to A[1] + A[n] since A[i] ≥ A[1].
• Likewise, if A[1] + A[n] < x, A[1] is useless since it cannot be paired with any number to achieve the sum.
Hence, we start with two pointers left and right, with left = 1 and right = n initially. At each stage, we check the sum A[left] + A[right]. If this sum exceeds x, we decrement right and if this sum is less than x we increment left. Eventually, either left and right meet and there is no solution, or we find the indices k and that we are looking for.
This takes a single scan of A, so the overall time is O(n).
(b) Suppose we fix the first index k = 1. Then the problem reduces to finding ` and m in 2, 3, . . . , n such that A[`] + A[m] = x − A[1]. This can be solved in time O(n) by the first part of this problem.
We vary k from 1, 2, . . . , n−3, and check for ` and m in k+1, k+2, . . . , n such that A[l`] + A[m] = x − A[k]. This takes time n−1 + · · · + 1 = O(n 2 ).
Question 278
You are given a sequence of n elements to sort. The input sequence consists of n/k subsequences,each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length n is to sort the k elements in each of the n/k subsequences. The lower bound on the number of comparisons needed to solve this variant of the sorting problem is
A
Ω(n)
B
Ω(n/k)
C
Ω(nlogk )
D
Ω(n/klogn/k)
       Algorithms       Sorting       UGC NET CS 2017 Nov- paper-3
Question 278 Explanation: 
There are n/k subsequences and each can be ordered in k! ways. This makes a (k!)n/k outputs. We can use the same reasoning:
(k!)n/k ≤ 2h
Taking the logarithm of both sides, we get:
h ≥ lg(k!)n/k
= (n/k)lg(k!)
≥ (n/k)(k/2)lg(k/2)
= (1/2)*(nlogk)-(1/2)*n
= Ω(nlogk)
Question 279
T(n)= 8T (n/2)+Cn, if n>1 = b, if n=1 Consider the recurrence relation:   Where b and c are constants. The order of the algorithm corresponding to above recurrence relation is:
A
n
B
n2
C
n log n
D
n3
       Algorithms       Time-Complexity       UGC NET CS 2017 Nov- paper-3
Question 279 Explanation: 
The above recurrence is in the form of masters theorem.
a=8,b=2,k=0 and p=0
Case-1: a>bk = 8>20
T(n)=O(nlogb^a)
= O(n3)
Question 280
Consider the following two sequences :
X = < B, C, D, C, A, B, C > and
Y = < C, A, D, B, C, B >
The length of longest common subsequence of X and Y is :
A
5
B
3
C
4
D
2
       Algorithms       Dynamic-Programming       UGC NET CS 2017 Nov- paper-3
Question 280 Explanation: 

Question 281
A text is made up of the characters a, b, c, d, e each occurring with the probability 0.11, 0.40, 0.16, 0.09 and 0.24 respectively. The optimal Huffman coding technique will have the average length of:
A
2.40
B
2.16
C
2.26
D
2.15
       Algorithms       Greedy-approach       UGC NET CS 2017 Nov- paper-3