Algorithms — GATE Previous Year Questions

Suppose \(T(n) = 2T(n/2) + n\), with \(T(0) = T(1) = 1\).

Which one of the following is FALSE?

The most efficient algorithm for finding the number of connected components in an undirected graph on \(n\) vertices and \(m\) edges has time complexity

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?

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

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

Consider the following array of elements:

<89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100>

The minimum number of interchanges needed to convert it into a max-heap is

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

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

Assume that multiplying a matrix \(G_1\) of dimension \(p \times q\) with another matrix \(G_2\) of dimension \(q \times r\) requires \(pqr\) scalar multiplications. Computing the product of \(n\) matrices \(G_1 G_2 G_3 \ldots G_n\) using dynamic programming, the time complexity is

There are \(n\) unsorted arrays: \(A_1, A_2, \ldots, A_n\). Assume that \(n\) is odd. Each of \(A_1, A_2, \ldots, A_n\) 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 \(A_1, A_2, \ldots, A_n\) is

Consider the following recurrence relation:

\(T(n) = T(n/2) + T(2n/5) + 7n\) for \(n > 0\), and \(T(0) = 0\).

Which one of the following options is correct?