search
Log In

Web Page

Searching, Sorting, Hashing, Asymptotic worst case time and Space complexity, Algorithm design techniques: Greedy, Dynamic programming, and Divide‐and‐conquer, Graph search, Minimum spanning trees, Shortest paths.

$$\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

5 votes
4 answers
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 ___________.
asked Feb 12, 2020 in Algorithms Arjun 3.5k views
3 votes
5 answers
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 _________
asked Feb 12, 2020 in Algorithms Arjun 2.3k views
5 votes
4 answers
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}}}$
asked Feb 11, 2020 in Algorithms Lakshman Patel RJIT 615 views
1 vote
3 answers
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)$
asked Jan 13, 2020 in Algorithms Satbir 605 views
5 votes
2 answers
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)$
asked Jan 13, 2020 in Algorithms Satbir 1.3k views
4 votes
2 answers
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$
asked Jan 13, 2020 in Algorithms Satbir 964 views
4 votes
5 answers
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$
asked Jan 13, 2020 in Algorithms Satbir 1.5k views
2 votes
2 answers
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
asked Jan 13, 2020 in Algorithms Satbir 654 views
1 vote
4 answers
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
asked Jan 13, 2020 in Algorithms Satbir 518 views
1 vote
1 answer
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
asked Dec 22, 2019 in Algorithms Sanjay Sharma 963 views
1 vote
1 answer
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)
asked Dec 22, 2019 in Algorithms Sanjay Sharma 612 views
1 vote
2 answers
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)}$
asked Dec 21, 2019 in Algorithms Sanjay Sharma 1.1k views
1 vote
1 answer
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.
asked Nov 20, 2019 in Algorithms KUSHAGRA गुप्ता 373 views
0 votes
1 answer
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.
asked Nov 12, 2019 in Algorithms KUSHAGRA गुप्ता 199 views
1 vote
1 answer
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.
asked Nov 12, 2019 in Algorithms KUSHAGRA गुप्ता 287 views
1 vote
1 answer
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.
asked Nov 12, 2019 in Algorithms KUSHAGRA गुप्ता 233 views
0 votes
2 answers
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!
asked Sep 22, 2019 in Algorithms luc_Bloodstone 234 views
0 votes
3 answers
18
$if ...F(n)=O(g(n)) Then ...it is true or false 2^{f(n)}=O(2^{g(n)}) Answer with reason$
asked Sep 22, 2019 in Algorithms shubhamkks1005 146 views
0 votes
2 answers
19
F(n)=O{ [ f(n)]^2} This statement is true or false With reason..
asked Sep 22, 2019 in Algorithms shubhamkks1005 145 views
1 vote
1 answer
20
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.$
asked Sep 13, 2019 in Algorithms gatecse 128 views
...