Web Page

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{Year}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum} \\\hline\textbf{1 Mark Count}&2&0&2&2&3&3&0&2&3 \\\hline\textbf{2 Marks Count}&2&4&2&3&2&3&2&2.7&4 \\\hline\textbf{Total Marks}&6&8&6&8&7&9&\bf{6}&\bf{7.3}&\bf{9}\\\hline \end{array}}}$$

# Recent questions in Algorithms

1
Consider the array representation of a binary min-heap containing $1023$ elements. The minimum number of comparisons required to find the maximum in the heap is ___________.
2
Consider a graph $G = (V,E)$, where $V = \{v_1,v_2, \dots ,v_{100}\}$, $E = \{(v_i,v_j) \mid 1\leq i < j \leq 100\}$, and weight of the edge $(v_i,v_j)$ is $\mid i – j \mid$. The weight of minimum spanning tree of $G$ is _________
3
Among the following asymptotic expressions, which of these functions grows the slowest (as a function of $n$) asymptotically? $2^{\log n}$ $n^{10}$ $(\sqrt{\log n})^{\log ^{2} n}$ $(\log n)^{\sqrt{\log n}}$ $2^{2^{\sqrt{\log\log n}}}$
1 vote
4
Consider product of three matrices $M_1,M_2$ and $M_3$ having $w$ rows and $x$ columns, $x$ rows and $y$ columns, and $y$ rows and $z$ columns. Under what condition will it take less time to compute the product as $(M_1M_2)M_3$ than to compute $M_1(M_2M_3)$ ? Always take the same time $(1/x +1/z)<(1/w+1/y)$ $x>y$ $(w+x)>(y+z)$
5
What is the complexity of the following code? sum=0; for(i=1;i<=n;i*=2) for(j=1;j<=n;j++) sum++; Which of the following is not a valid string? $O(n^2)$ $O(n\log\ n)$ $O(n)$ $O(n\log\ n\log\ n)$
6
Huffman tree is constructed for the following data :$\{A,B,C,D,E\}$ with frequency $\{0.17,0.11,0.24,0.33\ \text{and} \ 0.15 \}$ respectively. $100\ 00\ 01101$ is decoded as $BACE$ $CADE$ $BAD$ $CADD$
7
If an array $A$ contains the items $10,4,7,23,67,12$ and $5$ in that order, what will be the resultant array $A$ after third pass of insertion sort? $67,12,10,5,4,7,23$ $4,7,10,23,67,12,5$ $4,5,7,67,10,12,23$ $10,7,4,67,23,12,5$
8
The master theorem assumes the subproblems are unequal sizes can be used if the subproblems are of equal size cannot be used for divide and conquer algorithms cannot be used for asymptotic complexity analysis
1 vote
9
Of the following sort algorithms, which has execution time that is least dependant on initial ordering of the input? Insertion sort Quick sort Merge sort Selection sort
1 vote
10
Consider the following statements : a) The running time of dynamic programming algorithm is always θ (p) where p is number of subproblems b)when a recurrence relation has cyclic dependency, it is impossible to use that recurrence relation (unmodified) in a correct dynamic program c) For a dynamic ... of the statement(s) is/are true 1) only b and a 2)only b 3) only b and c 4)only b and d
1 vote
11
What is the worst case time of insert and extract- min in an implementation of a priority queue using an unsorted array? Assume that all insertions can be accommodated 1) θ(1) ,θ(n) 2) θ(n) ,θ(1) 3) θ(1) ,θ(1) 4) θ(n) ,θ(n)
1 vote
12
$\text{Give asymptotic upper and lower bound for$\mathbf{T(n)}$given below.}\;\text{Assume$\mathrm {T(n)}$is constant for$\mathrm {n\le 2}.$}$ $\large{\mathrm{T(n) = 4T\left (\sqrt n \right ) + \lg^2 n}}$ $1)\;\mathrm{T(n)=\theta(\lg(\lg^2 n)\lg n)}$ ... $3)\;\;\mathrm{T(n) = \theta(\lg^2 n \lg \lg n)}$ $4)\;\;\mathrm{T(n) = \theta (\lg (\lg n)\lg n)}$
1 vote
13
Argue that since sorting $n$ elements takes $\Omega (n\ lgn)$ time in the worst case in the comparison model, any comparison-based algorithm for constructing a $BST$ from an arbitrary list of n elements takes $\Omega (n\ lgn)$ time in the worst case.
14
The diameter of a tree $T= (V, E)$ is defined as $max_{u,v\ \epsilon\ V}\ \delta(u,v)$, that is, the largest of all shortest-path distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm.
1 vote
15
There are two types of professional wrestlers: babyfaces ( good guys ) and heels ( bad guys ). Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of ... that each rivalry is between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it.
1 vote
16
Give an example of a directed graph $G=(V, E)$, a source vertex $s\ \epsilon\ V$ , and a set of tree edges $E_{\Pi}\subseteq E$ such that for each vertex $v\ \epsilon\ V$ , the unique simple path in the graph $(V, E_{\Pi})$ from s to v is a shortest path in G, yet the set of edges $E_{\Pi}$ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.
17
I am having difficulty in understanding np and np-hard topic in algorithms. If someone can provide some good source to learn about it in easy manner it would be a real help. Thank you!
$if ...F(n)=O(g(n)) Then ...it is true or false 2^{f(n)}=O(2^{g(n)}) Answer with reason$
Let $A$ be an $n\times n$ matrix of integers such that each row and each column is arranged in ascending order. We want to check whether a number $k$ appears in $A.$ If $k$ is present, we should report its position - that is, the row $i$ and column $j$ ... $2n$ values in $A.$ Justify the complexity of your algorithm. For both algorithms, describe a worst-case input where $k$ is present in $A.$