Questions & Answers of Algorithms

Question No. 4

Consider the following function from positive integers to real numbers:

                        $\style{font-family:'Times New Roman'}{10,\;\sqrt n,\;n,\;\log_2n,\;\frac{100}n.}$

The CORRECT arrangement of the above functions in increasing  order of asymptotic complexity is:

Question No. 5

Consider the following table:

                   Algorithms                   Design Paradigms
(P) Kruskal (i) Divided and conquer
(Q) Quicksort (ii) Greedy
(R) Floyd-Warshall (iii) Dynamic Programming

Match the algorithms to the design paradigms they are based on.

Question No. 26

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

(I) Munimum 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?

Question No. 48

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 _________

Question No. 103

Match the algorithms with their time complexities:

Algorithm Time complexity
(P) Towers of Hanoi with n disks (i)$\style{font-family:'Times New Roman'}{\Theta(n^2)}$
(Q) Binary search given n stored numbers (ii)$\style{font-family:'Times New Roman'}{\Theta(n\;\log\;n)}$
(R) Heap sort given n numbers at the worst case (iii)$\style{font-family:'Times New Roman'}{\Theta(2^n)}$
(S) Addition of two n$\style{font-family:'Times New Roman'}\times$n matrices (iv)$\style{font-family:'Times New Roman'}{\Theta(\log\;n)}$

Question No. 115

The Breadth First search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

 

Question No. 130

Consider the recurrence function $\style{font-family:'Times New Roman'}{T(n)=\left\{\begin{array}{l}2T\;(\sqrt n)+1,\;\;\;\;n>2\\2,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;0<n\leq2\end{array}\right.}$

Then T(n) in terms of  $\style{font-family:'Times New Roman'}\Theta$ notation is

Question No. 138

Consider the following C function

int. fun(int.in) {
         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 $\theta$ notation is

Question No. 12

Let an be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for $a_n$?

Question No. 21

Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is .

Question No. 23

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

Question No. 24

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

P: Minimum spanning tree of G does not change

Q: Shortest path between any pair of vertices does not change

Question No. 37

Consider the recurrence relation $\style{font-family:'Times New Roman'}{a_1=8,a_n=6n^2+2n+a_{n-1}.\mathrm{Let}\;a_{99}=K\times10^4.}$ The value of K is __________. 

Question No. 48

Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} is given by the entry $W_{ij}$ in the matrix W.

                                                W=02852058850x58x0

The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is ________ .

Question No. 49

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

Question No. 50

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

Question No. 121

Breadth First Search(BFS) is started ona binary tree beginning from the root vertex. There is a vertext at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is _________.

Question No. 123

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 Θ($\style{font-family:'Times New Roman'}{n^2}$) time 

II. Bubblesort runs in Θ($\style{font-family:'Times New Roman'}{n^2}$) time

III. Mergesort runs in Θ(n) time

IV. Insertion sort runs inΘ(n) time

Question No. 124

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

Question No. 13

Match the following:

(P) Prim’s algorithm for minimum spanning tree (i) Backtracking
(Q) Floyd – Warshal algorithm for all pairs shortest paths (ii) Greedy method
(R) Mergesort (iii) Dynamic programming
(S) Hamiltonian circuit (iv) Divide and conquer

Question No. 14

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.

Question No. 38

Consider the following C program segment.
while(first <= last)
{
    if(array[middle] < search)
       first = middle + 1;
    else if (array[middle] = = search)
              found = TRUE;
    else last = middle – 1;
    middle = (first + last)/2;
}
if (first > last) notPresent = TRUE;

The cyclomatic complexity of the program segment is ______.

Question No. 45

Let an represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for an?

Question No. 51

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u) - d(v)?

Question No. 60

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 form 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 asymptotic complexity considering all the operations?

Question No. 63

The graph shown below has 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 _______.

Question No. 64

Consider the following C function.
int fun1 (int n){
      int i, j, k, p, q = 0;
      for (i = 1; i < n; ++i) {
            p = 0;
           for(j = n; j > 1; j = j/2)
                 ++p;
           for(k =1; k < p; k = k*2)
                ++q;
      }
      return q;
}

Which one of the following most closely approximates the return value of the function fun1?

Question No. 116

An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

Question No. 147

Given below are some algorithms, and some algorithm design paradigms.

1. Dijkstra’s Shortest Path              i. Divide and Conquer
2. Floyd-Warshall algorithm to compute all pairs shortest path              ii. Dynamic Programming
3. Binary search on a sorted array              iii. Greedy design
4. Backtracking search on a graph              iv. Depth-first search
               v. Breadth-first search

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

Question No. 150

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

Question No. 220

Consider the equality $\sum\limits_{i=0}^ni^3=X$ and the following choices for X.

I.θn4

II. θn5

III. On4

IV.Ωn3

The equality above remains correct if X is replaced by

Question No. 222

Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is ______.

Question No. 237

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?

Question No. 255

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

Question No. 263

Suppose c=c[0], ... , c[k-1] is an array of length k, where all the entries are from the set {0, 1}. For any positive integers a and n, consider the following pseudocode.

DOSOMETHING (c, a, n)
z ← 1
for i ← 0 to k – 1
    do zz2mod n
    if c[i] = 1
        then z ← (z $\times$ a) mod n
    return z

If k = 4, c = <1, 0, 1, 1>, a = 2 and n = 8, then the output of DOSOMETHING (c, a, n) is _________.

Question No. 264

Let f(n) = n and g(n) = n(1+sin n), where n is a positive integer. Which of the following statements is/are correct?

I. f(n) = O(g(n))
II. f(n) = Ω(g(n))

Question No. 21

Let G be a graph with n vertices and m edges.what is the tightest upper bound on the running time of depth first search on G, when G is represented as an adjecency matrix?

Question No. 22

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtree having exactly 4 nodes is Onalogbn. Then the value of a+10b is _____.

Question No. 23

Consider the directed graph given below.

which of the following is TRUE?

Question No. 24

Let P be a quicksort program to sort numbers in ascendinng order using the first element as the pivot. Let t1 and t2 be the number of comparisions made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. which one of the following holds?

Question No. 49

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.

Question No. 50

Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

Question No. 52

Consider the following pseudo code. What is the total number of multiplications to be performed?

  D = 2
    for i = 1 to n do
      for j = i to n do
        for k = j + 1 to n do
          D = D * 3

Question No. 122

A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

Question No. 123

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?

Tn=2Tn2+logn

Question No. 124

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

Question No. 147

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 = ___.

Question No. 148

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

Question No. 162

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

Question No. 221

The minimum number of arithematic operation required to evaluate the polynomial PX=X5+4X3+6X+5 for a given value of X,using only one temporary variable is_____.

 

Question No. 223

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

 

Question No. 224

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

Question No. 249

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 0(na logbn + mc logdn), the value of a + 10b + 100c + 1000d is ____.

Question No. 250

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?

Question No. 6

Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

Question No. 7

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?

Question No. 19

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

Question No. 30

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

Question No. 31

Consider the following function:
int unknown(int n){
int i, j, k=0;
for (i=n/2; i<=n; i++)
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);
}

The return value of the function is

Question No. 5

The worst case running time to search for an element in a balanced binary search tree with n2n elements is

Question No. 16

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

Question No. 18

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?

Question No. 29

Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?

Question No. 39

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

Question No. 40

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.

Question No. 25

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0:n- 1] is given below.

Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array.

Initialize Ln-1 =1.

For all i such that 0in-2

Li=1+Li+1ifA[i]<A[i+1]1otherwise

Finally the length of the longest monotonically increasing sequence is Max (L0, L1,…….Ln-1).

Which of the following statements is TRUE?

Question No. 37

Which of the given options provides the increasing order of asymptotic complexity of functions f1,f2,f3, and f4?

f1n=2n    f2n=n32  f3n=nlog2n  f4n=nlog2n

Question No. 38

Four matrices M1, M2 , M3 and M4, of dimensions p × q , q × r , r × s and s × t respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as ((M1 × M2) × (M3 × M4)). The total number of scalar multiplications is pqr + rst + prt. When multiplied as (((M1 × M2) ×M3) ×M4), the total number of scalar multiplications is pqr+ prs+ pst.
If p = 10, q = 100, r = 20, s = 5, and t = 80, then the minimum number of scalar multiplications needed is

Question No. 54

An undirected graph G(V,E) contains n (n > 2) nodes named v1,v2.....vn.two node vi,vj are connected if and only if 0 <| i - j | ≤ 2. Each edge (vi, vj)is assigned a weight i +j.
A sample graph with n = 4 is shown below.

What will be the cost of minimum spanning tree(MST) of such agraph with n node?

Question No. 55

An undirected graph G(V,E) contains n (n > 2) nodes named v1,v2.....vn.two node vi,vj are connected if and only if 0 <| i - j | ≤ 2. Each edge (vi, vj)is assigned a weight i +j.
A sample graph with n = 4 is shown below.

The length of the path from v5 to v6 in the MST of previous question with n=10 is

Question No. 12

Two alternative packages A and B are available for processing a database having 10k records. Package A requires 0.0001n2 time units and package B requires 10nlog10n time units to process n records. What is the smallest value of k for which package B will be preferred over A?

Question No. 34

The weight of a sequence a0, a1,…, an-1 of real numbers is defined as a0 + a1 /2 +…+ aa-1/2n-1. A subsequence of a sequence is obtained by deleting some elements from the sequence. keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a0, a1,…, an-1 and Y the maximum possibble weight of a subsequence of a0, a1,…, an-1. Then X is equal to

Question No. 50

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.

W=018141012498120731470249320

 What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

Question No. 51

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.

W=018141012498120731470249320

What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?