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

2 votes
9 answers
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.
asked Mar 31 in Algorithms Lakshman Patel RJIT 391 views
0 votes
1 answer
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
asked Mar 31 in Algorithms Lakshman Patel RJIT 154 views
0 votes
3 answers
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$
asked Mar 31 in Algorithms Lakshman Patel RJIT 160 views
0 votes
1 answer
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$
asked Mar 31 in Algorithms Lakshman Patel RJIT 97 views
0 votes
1 answer
5
What is the type of the algorithm used in solving the $4$ Queens problem? Greedy Branch and Bound Dynamic Backtracking
asked Mar 31 in Algorithms Lakshman Patel RJIT 94 views
0 votes
2 answers
6
0 votes
1 answer
7
0 votes
1 answer
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$
asked Mar 31 in Algorithms Lakshman Patel RJIT 80 views
0 votes
1 answer
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)$
asked Mar 31 in Algorithms Lakshman Patel RJIT 81 views
0 votes
1 answer
10
0 votes
1 answer
11
0 votes
2 answers
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
asked Mar 31 in Algorithms Lakshman Patel RJIT 83 views
0 votes
2 answers
13
Two main measures for the efficiency of an algorithm are: Processor and Memory Complexity and Capacity Time and Space Data and Space
asked Mar 31 in Algorithms Lakshman Patel RJIT 71 views
0 votes
1 answer
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
asked Mar 31 in Algorithms Lakshman Patel RJIT 91 views
0 votes
1 answer
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)
asked Mar 31 in Algorithms Lakshman Patel RJIT 72 views
0 votes
2 answers
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)$
asked Mar 30 in Algorithms Lakshman Patel RJIT 189 views
0 votes
1 answer
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$
asked Mar 30 in Algorithms Lakshman Patel RJIT 59 views
0 votes
1 answer
18
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)$
asked Mar 30 in Algorithms Lakshman Patel RJIT 73 views
0 votes
1 answer
19
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
asked Mar 30 in Algorithms Lakshman Patel RJIT 91 views
...