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{2021-1}&\textbf{2021-2}&\textbf{2020}&\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}&3&2&3&2&0&2&2&3&3&0&2.2&3
\\\hline\textbf{2 Marks Count}&3&4&4&2&4&2&3&2&3&2&3&4
\\\hline\textbf{Total Marks}&9&10&11&6&8&6&8&7&9&\bf{6}&\bf{8.2}&\bf{11}\\\hline
\end{array}}}$$

Recent questions in Algorithms

5 votes
4 answers
1
Let $G$ be a connected undirected weighted graph. Consider the following two statements. $S_1$: There exists a minimum weight edge in $G$ which is present in every minimum spanning tree of $G$. $S_2$: If every edge in $G$ has distinct weight, then $G$ has a unique minimum spanning ... $S_1$ is true and $S_2$ is false $S_1$ is false and $S_2$ is true Both $S_1$ and $S_2$ are false
asked Feb 18 in Algorithms Arjun 1.6k views
1 vote
3 answers
2
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$? $\Theta ( \sqrt{n})$ $\Theta (\log _2(n))$ $\Theta(n^2)$ $\Theta(n)$
asked Feb 18 in Algorithms Arjun 1.1k views
4 votes
2 answers
3
Consider the following $\text{ANSI C}$ function: int SomeFunction (int x, int y) { if ((x==1) || (y==1)) return 1; if (x==y) return x; if (x > y) return SomeFunction(x-y, y); if (y > x) return SomeFunction (x, y-x); } The value returned by $\textrm{SomeFunction(15, 255)}$ is __________
asked Feb 18 in Algorithms Arjun 726 views
3 votes
2 answers
4
Consider the string $\textrm{abbccddeee}$. Each letter in the string must be assigned a binary code satisfying the following properties: For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter. For any two letters ... assignments which satisfy the above two properties, what is the minimum length of the encoded string? $21$ $23$ $25$ $30$
asked Feb 18 in Algorithms Arjun 944 views
5 votes
3 answers
5
For constants $a \geq 1$ and $b>1$, consider the following recurrence defined on the non-negative integers: $T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n)$ Which one of the following options is correct about the recurrence $T(n)$? If $f(n)$ is $n \log_2(n)$, then $T(n)$ ... $\Theta(n^{\log_b(a)})$ If $f(n)$ is $\Theta(n^{\log_b(a)})$, then $T(n)$ is $\Theta(n^{\log_b(a)})$
asked Feb 18 in Algorithms Arjun 1k views
3 votes
2 answers
6
Consider the following directed graph: Which of the following is/are correct about the graph? The graph does not have a topological order A depth-first traversal starting at vertex $S$ classifies three directed edges as back edges The graph does not have a strongly connected component For each pair of vertices $u$ and $v$, there is a directed path from $u$ to $v$
asked Feb 18 in Algorithms Arjun 890 views
4 votes
2 answers
7
Consider the following $\text{ANSI C}$ program #include <stdio.h> int foo(int x, int y, int q) { if ((x<=0) && (y<=0)) return q; if (x<=0) return foo(x, y-q, q); if (y<=0) return foo(x-q, y, q); return foo(x, y-q, q) + foo(x-q, y, q); } int main( ) { int r = foo(15, 15, 10); printf(“%d”, r); return 0; } The output of the program upon execution is _________
asked Feb 18 in Algorithms Arjun 789 views
4 votes
2 answers
8
In a directed acyclic graph with a source vertex $\textsf{s}$, the $\textit{quality-score}$ of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex $v$ other than $\textsf{s}$, the quality-score of $v$ is ... quality-score of $\textsf{s}$ is assumed to be $1$. The sum of the quality-scores of all vertices on the graph shown above is _______
asked Feb 18 in Algorithms Arjun 925 views
4 votes
4 answers
9
Consider the following three functions. $f_1=10^n\quad f_2=n^{\log n}\quad f_3=n^{\sqrt {n}}$ Which one of the following options arranges the functions in the increasing order of asymptotic growth rate? $f_3, f_2, f_1$ $f_2, f_1, f_3$ $f_1, f_2,f_3$ $f_2, f_3, f_1$
asked Feb 18 in Algorithms Arjun 949 views
3 votes
3 answers
10
Consider the following array.$\begin{array}{|l|l|l|l|l|l|} \hline 23&32&45&69&72&73&89&97 \\ \hline\end{array}$ Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order? Selection sort Mergesort Insertion sort Quicksort using the last element as pivot
asked Feb 18 in Algorithms Arjun 974 views
1 vote
3 answers
11
6 votes
5 answers
12
Consider the following recurrence relation. $T\left ( n \right )=\left\{\begin{array} {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.$ Which one of the following options is correct? $T(n)=\Theta (n^{5/2})$ $T(n)=\Theta (n\log n)$ $T(n)=\Theta (n)$ $T(n)=\Theta ((\log n)^{5/2})$
asked Feb 18 in Algorithms Arjun 2.2k views
2 votes
2 answers
13
Define $R_n$ to be the maximum amount earned by cutting a rod of length $n$ meters into one or more pieces of integer length and selling them. For $i>0$, let $p[i]$ denote the selling price of a rod whose length is $i$ meters. Consider the array of prices: ... $R_7$? $R_7=18$ $R_7=19$ $R_7$ is achieved by three different solutions $R_7$ cannot be achieved by a solution consisting of three pieces
asked Feb 18 in Algorithms Arjun 1.1k views
2 votes
1 answer
14
Consider a $\textit{dynamic}$ hashing approach for $4$-bit integer keys: There is a main hash table of size $4$. The $2$ least significant bits of a key is used to index into the main hash table. Initially, the main hash table entries are empty. Thereafter, when more keys are hashed into it, to resolve ... in decimal notation)? $5,9,4,13,10,7$ $9,5,10,6,7,1$ $10,9,6,7,5,13$ $9,5,13,6,10,14$
asked Feb 18 in Algorithms Arjun 719 views
2 votes
3 answers
15
Consider the following $\text{ANSI C}$ function: int SimpleFunction(int Y[], int n, int x) { int total = Y[0], loopIndex; for (loopIndex=1; loopIndex<=n-1; loopIndex++) total=x*total +Y[loopIndex]; return total; } Let $\textsf{Z}$ be an array of $10$ elements with $\textsf{Z}[i]=1$, for all $i$ such that $0 \leq i \leq 9$. The value returned by $\textsf{SimpleFunction(Z},10,2)$ is __________
asked Feb 18 in Algorithms Arjun 523 views
1 vote
2 answers
16
Consider the following program. Assume that $x$ and $y$ are integers. f(x, y) { if (y != 0) return (x * f(x,y-1)); else return 1; } What is $f(6,3)?$ $243$ $729$ $125$ $216$
asked Jan 29 in Algorithms soujanyareddy13 142 views
1 vote
1 answer
17
For any string $\text{str, length(str)}$ returns the length of the string, $\text{append(str1, str2)}$ concatenates $\text{str1}$ with another string $\text{str2}$, and $\text{trim(str)}$ removes any spaces that exist at the end of the string $\text{str}$. The function $\text{reverse(str, i, j)}$ ... n; i=i+1) { if(str[i] is ' ') { reverse(str, j, i-1); j = i + 1; } } trim(str); return str; }
asked Jan 29 in Algorithms soujanyareddy13 67 views
0 votes
1 answer
18
If algorithm $A$ and another algorithm $B$ take $\log_2 (n)$ and $\sqrt{n}$ microseconds, respectively, to solve a problem, then the largest size $n$ of a problem these algorithms can solve, respectively, in one second are ______ and ______. $2^{10^n}$ and $10^6$ $2^{10^n}$ and $10^{12}$ $2^{10^n}$ and $6.10^6$ $2^{10^n}$ and $6.10^{12}$
asked Nov 20, 2020 in Algorithms jothee 586 views
0 votes
0 answers
19
The running time of an algorithm is $O(g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n)) \cdot (O= \textit{ big }O)$ its worst-case running time is $\Omega (g(n))$ ... , $(o = \textit{ small } o)$ Choose the correct answer from the options given below: $(a)$ only $(b)$ only $(c)$ only $(d)$ only
asked Nov 20, 2020 in Algorithms jothee 230 views
0 votes
1 answer
20
Match $\text{List I}$ with $\text{List II}$ ... $A-I, B-II, C-III, D-IV$ $A-II, B-I, C-III, D-IV$ $A-II, B-IV, C-III, D-I$
asked Nov 20, 2020 in Algorithms jothee 153 views
...