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
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.
2
If there is in NP-Complete language L whose complement is in NP, then complement of any language in NP is in P NP both (A) and (B) None of these
3
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$
4
Two alternative packages $A$ and $B$ are available for processing a database having $10k$ records. Package $A$ requires $0.0001n2$ time units and package $B$ requires $10 n \log 10n$ 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$
5
What is the type of the algorithm used in solving the $4$ Queens problem? Greedy Branch and Bound Dynamic Backtracking
6
Selection sort, quick sort is a stable sorting method True,True False,False True,False False,True
7
Which of the following sorting procedures is the slowest? Quick Sort Merge Sort Shell Sort Bubble Sort
8
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with $n$ discs is: $T(n)=2T(n-2)+2$ $T(n)=2T(n/2)+1$ $T(n)=2T(n-1)+n$ $T(n)=2T(n-1)+1$
9
Complexity of Kruskal's algorithm for finding minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is: $O(mn)$ $O(m)$ $O(m+n)$ $O(n)$
10
Find the odd one out Merge Sort TVSP Problem Knapsack Problem OBST Problem
11
The Knapsack problem belongs to which domain of problems? Optimization NP complete Linear Solution Sorting
12
The running time of Quick sort algorithm depends heavily on the selection of: No. of inputs Arrangement of elements in an array Size of elements Pivot Element
13
Two main measures for the efficiency of an algorithm are: Processor and Memory Complexity and Capacity Time and Space Data and Space
14
What is the solution to the recurrence $T(n)=T \bigg (\dfrac{n}{2} \bigg )+n$? $O(\log n)$ $O(n)$ $O(n\log n)$ None of these
15
The concept of order Big O is important because It can be used to decide the best algorithm that solves a given problem It is the lower bound of the growth rate of algorithm It determines the maximum size of a problem that can be solved in a given amount of time Both (A) and (B)
16
What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$
17
$0/1$-Knapsack is a well known problem where, it is desired to get the maximum total profit by placing $n$ items (each item is having some weight and associated profit) into a knapsack of capacity $W$. The table given below shows the weights and associated profits for $5$ items, where one unit of ... $19$ $18$ $17$ $20$
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are $\Theta(n \log n),\Theta(n \log n) \text{ and } \Theta(n^2)$ $\Theta(n^2),\Theta(n^2)\text{ and } \Theta(n \log n)$ $\Theta(n^2), \Theta(n \log n)\text{ and } \Theta(n \log n)$ $\Theta(n^2),\Theta(n\log n) \text{ and } \Theta(n^2)$
Which of the following standard algorithms is not Dynamic Programming based? Bellman-Ford Algorithm for single source shortest path Floyd Warshall Algorithm for all pairs shortest paths $0-1$ Knapsack problem Prim’s Minimum Spanning Tree
Four Matrices $M_1, M_2, M_3$ and $M_4$ of dimensions $p \times q$, $q \times r$, $r \times s$ and $s \times t$ ... $t=80$, then the number of scalar multiplications needed is $248000$ $44000$ $19000$ $25000$