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
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 of $G$, when $G$ is represented using adjacency matrix? $O(n)$ $O(m+n)$ $O(n^2)$ $O(mn)$
2
Suppose $T(n)=2T(n/2)+n$, $T(0)=T(1)=1$ which one of the following is false? $T(n)=O(n^2)$ $T(n)=\Theta(n\log n)$ $T(n)=\Omega(n^2)$ $T(n)=O(n\log n)$
1 vote
3
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 $2$ $4$ $3$ $5$
4
Which algorithm has same average, worst case and best case time ? Binary search Maximum of n number Quick sort Fibonacci search
5
Binary search tree is an example of : Divide and conquer technique Greedy algorithm Back tracking Dynamic Programming
6
How much extra space is used by heapsort ? $O (1)$ $O (\log n)$ $O (n)$ $O (n^2)$
7
The asymptotic upper bound solution of the recurrence relation given by $T(n)=2T \left ( \frac{n}{2} \right)+\frac{n}{\lg n}$ is: $O(n^{2})$ $O(n \lg n)$ $O(n \lg \lg n)$ $O(\lg \lg n)$
8
Any decision tree that sorts $n$ elements has height $\Omega (\lg n)$ $\Omega ( n)$ $\Omega (n \lg n)$ $\Omega ( n^{2})$
9
Red-black trees are one of many search tree schemes that are “balanced” in order to guarantee that basic dynamic–set operations take____ time in the worst case. $O(1)$ $O(\lg n)$ $O( n)$ $O(n \lg n)$
10
The minimum number of scalar multiplication required, for parenthesization of a matrix-chain product whose sequence of dimensions for four matrices is $< 5,10,3,12,5>$ is $630$ $580$ $480$ $405$
11
Dijkstra’s algorithm is based on Divide and conquer paradigm Dynamic programming Greedy approach Backtracking paradigm
12
Match the following with respect to algorithm paradigms: ...
13
Which of the following is true for computation time in insertion, deletion and finding maximum and minimum element in a sorted array ? Insertion - $0(1)$, Deletion - $0(1)$, Maximum - $0(1)$, Minimum - $0(1)$ Insertion - $0(1)$, Deletion - $0(1)$, Maximum - $0(n)$, Minimum - $0(n)$ ... , Maximum - $0(1)$, Minimum - $0(1)$ Insertion - $0(n)$, Deletion - $0(n)$, Maximum - $0(n)$, Minimum - $0(n)$
14
Which of the following statements is false? Optimal binary search tree construction can be performed efficiently using dynamic programming. Breadth-first search cannot be used to find connected components of a graph. Given the prefix and postfix walks of a binary tree, the tree cannot be reconstructed uniquely. Depth-first-search can be used to find the connected components of a graph. a b c d
15
For parameters $a$ and $b$, both of which are $\omega(1)$, $T(n) = T(n^{1/a})+1$, and $T(b)=1$. Then $T(n)$ is $\Theta (\log_a \log _b n)$ $\Theta (\log_{ab} n$) $\Theta (\log_{b} \log_{a} \: n$) $\Theta (\log_{2} \log_{2} n$)
16
What is the worst case time complexity of inserting $n^{2}$ elements into an AVL-tree with $n$ elements initially? $\Theta (n^{4})$ $\Theta (n^{2})$ $\Theta (n^{2}\log n)$ $\Theta (n^{3})$
17
Consider a double hashing scheme in which the primary hash function is $h_1(k)= k \text{ mod } 23$, and the secondary hash function is $h_2(k)=1+(k \text{ mod } 19)$. Assume that the table size is $23$. Then the address returned by probe $1$ in the probe sequence (assume that the probe sequence begins at probe $0$) for key value $k=90$ is_____________.
Let $G = (V, G)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST of the resultant graph ... $\Theta (\mid E \mid \mid V \mid) \\$ $\Theta(E \mid \log \mid V \mid) \\$ $\Theta( \mid V \mid)$
Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in E$, define ${w}'(u,v)$ as $w(u,v)+f(u)-f(v)$. Which one of the options completes the ... distance from $s$ to $u$ in the graph obtained by adding a new vertex $s$ to $G$ and edges of zero weight from $s$ to every vertex of $G$
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 ___________.