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
Two alternative package $A$ and $B$ are available for processing a database having $10^{k}$ records. Package $A$ requires $0.0001 n^{2}$ time units and package $B$ requires $10n\log _{10}n$ time units to process $n$ records. What is the smallest value of $k$ for which package $B$ will be preferred over $A$? $12$ $10$ $6$ $5$
2
The most efficient algorithm for finding the number of connected components in a $n$ undirected graph on $n$ vertices and $m$ edges has time complexity $\Theta (n)$ $\Theta (m)$ $\Theta (m+n)$ $\Theta (mn)$
3
An element in an array $X$ is called a leader if it is greater than all elements to the right of it in $X$. The best algorithm to find all leaders in an array solves it in linear time using a left to right pass of the array solves in linear time using a right to left pass of the array solves it using divide and conquer in time $\theta (n\log n)$ solves it in time $\theta (n^{2})$
4
An algorithm is made up pf two modules $M1$ and $M2.$ If order of $M1$ is $f(n)$ and $M2$ is $g(n)$ then the order of algorithm is $max(f(n),g(n))$ $min(f(n),g(n))$ $f(n) + g(n)$ $f(n) \times g(n)$
5
The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by $T(n) = 8T(n/2) + qn,$ if $n>1$ $= p,$ if $n = 1$ Where $p,q$ are constants. The order of this algorithm is $n^{2}$ $n^{n}$ $n^{3}$ $n$
6
The average search time for hashing with linear probing will be less if the load factor Is far less than one Equals one Is far greater than one None of the above
7
The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by $T(n) = 8T(n/2) + qn,$ if $n>1$ $= p,$ if $n = 1$ Where $p,q$ are constants. The order of this algorithm is $n^{2}$ $n^{n}$ $n^{3}$ $n$
8
Consider the following C code segment: int Ls Prime(n) { int i,n; for(i=2;i<=sqrt(n);i++) if(n%i ==0) { printf( NOT Prime.\n ); return 0; } return 1; } Let $T(n)$ denote the number of times the for loop is executed by the program on input $n.$ ... $T(n) = O(\sqrt{n})$ and $T(n) = \Omega (1)$ $T(n) = O(n)$ and $T(n) = \Omega (\sqrt{n})$ None of these
9
Which of the following algorithm solve the all-pair shortest path problem? Dijakstra’s algorithm Floyd’s algorithm Prim’s algorithm Warshall’s algorithm
10
An algorithm is made up of two modules $M1$ and $M2.$ If order of $M1$ is $f(n)$ and $M2$ is $g(n)$ then he order of algorithm is $max(f(n),g(n))$ $min(f(n),g(n))$ $f(n) + g(n)$ $f(n) \times g(n)$
1 vote
11
Which type of algorithm is used to solve the "$8$ Queens" problem ? Greedy Dynamic Divide and conquer Backtracking
1 vote
12
The average search time of hashing, with linear probing will be less if the load factor : is far less than $1$ equals $1$ is far greater than $1$ none of the options
13
Merge sort uses : Divide-and-conquer Backtracking Heuristic approach Greedy approach
1 vote
14
Given two sorted list of size '$m$' and '$n$' respectively. The number of comparisons needed in the worst case by the merge sort algorithm will be : $m^{*}n$ minimum of $m, n$ maximum of $m, n$ $m+n-1$
15
Which of the following sorting algorithms does not have a worst case running time of $O(n​^2​)$? Insertion sort. Merge sort. Quick sort. Bubble sort.
16
A hash function $f$ defined as $f(\text{key})=\text{key mod }7$, with linear probing, insert the keys $37,38,72,48,98,11,56$ into a table indexed from $11$ will be stored in the location $3$ $4$ $5$ $6$
1 vote
17
A hash table has space for $100$ records. Then the probability of collision before the table is $10\%$ full, is $0.45$ $0.5$ $0.3$ $0.34$ (approximately)
18
Time complexity of an algorithm $T(n)$, where $n$ is the input size is given by $\begin{array}{ll}T(n) & =T(n-1)+1/n, \text{ if }n>1\\ & =1, \text{ otherwise} \end{array}$ The order of this algorithm is $\log n$ $n$ $n^2$ $n^n$
19
What is the type of the algorithm used in solving the $4$ Queens problem? Greedy Branch and Bound Dynamic Backtracking