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

Most viewed questions in Algorithms

1
Level of a node is distance from root to that node. For example, level of root is 1 and levels of left and right children of root is 2. The maximum number of nodes on level i of a binary tree is In the following answers, the operator '^' indicates power a) 2^i-1 b)2^i c)2^i+1 d)2^(i+1/2)
2
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
3
1. The number of swappings needed to sort the numbers: 8, 22, 7, 9, 31, 19, 5, 13 in ascending order using bubble sort is— (a) 11 (b) 12 (c) 13 (d) 14 I know how to solve it using straightforward method. What I did was to write every pass and check the swappings. But , it takes too much time. Is there any shortcut possible ?
4
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 __________
5
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 $O(n^2)$ $O(n \log n)$ $\Theta(n\log n)$ $O(n^3)$
6
The number of possible min-heaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______
7
Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any $n > 0$ is: $\lceil \log_2n \rceil +1$ $n$ $\lceil \log_2n \rceil$ $\lfloor \log_2n \rfloor +1$
8
Please tell me the complete steps how to solve this problem. $\Large T(n) = T ( \sqrt n )+ 1$
9
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 Half of the product of the $3$ consecutive integers. One-third of the product of the $3$ consecutive integers. One-sixth of the product of the $3$ consecutive integers. None of the above.
10
The average number of key comparisons required for a successful search for sequential search on $n$ items is $\frac{n}{2}$ $\frac{n-1}{2}$ $\frac{n+1}{2}$ None of the above
11
Consider the following recurrence: $T(n)=2T\left ( \sqrt{n}\right )+1,$ $T(1)=1$ Which one of the following is true? $T(n)=\Theta (\log\log n)$ $T(n)=\Theta (\log n)$ $T(n)=\Theta (\sqrt{n})$ $T(n)=\Theta (n)$
12
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of $n$ $n^2$ $n \log n$ $n \log^2n$
13
The number of elements that can be sorted in $\Theta(\log n)$ time using heap sort is $\Theta(1)$ $\Theta(\sqrt{\log} n)$ $\Theta(\frac{\log n}{\log \log n})$ $\Theta(\log n)$
14
$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? If $e$ is the lightest edge of some cycle in $G$, then ... heaviest edge of some cycle in $G$, then every MST of $G$ excludes $e$. I only. II only. Both I and II. Neither I nor II.
15
The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is $\Theta(n)$ $\Theta(\log n)$ $\Theta(\log^*n)$ $\Theta(1)$
16
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 $O (n \log n)$ $O(n^{2} \log n)$ $O(n^{2} + \log n)$ $O(n^{2})$
17
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.
The cube root of a natural number $n$ is defined as the largest natural number $m$ such that $(m^3 \leq n)$ . The complexity of computing the cube root of $n$ ($n$ is represented by binary notation) is $O(n)$ but not $O(n^{0.5})$ $O(n^{0.5})$ but not $O((\log n)^k)$ for any constant ... $m>0$ $O( (\log \log n)^k )$ for some constant $k > 0.5$, but not $O( (\log \log n)^{0.5} )$
Suppose there are $\lceil \log n \rceil$ sorted lists of $\lfloor n /\log n \rfloor$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure) $O(n \log \log n)$ $\Theta(n \log n)$ $\Omega(n \log n)$ $\Omega\left(n^{3/2}\right)$