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

Recent questions in Algorithms

65 votes

12 answers

4321

GATE IT 2005 | Question: 14
In a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges. The number of connected components in $G$ is $k$ $k+1$ $n-k-1$ $n-k$

In a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges. The number of connected components in $G$ is$k$$k+1$$n-k-1$$n-k$

17.8k views

Ishrat Jahan asked Nov 3, 2014

22 votes

5 answers

4322

GATE IT 2004 | Question: 57
Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm. ... $\text{P-III, Q-II, R-IV, S-I}$ $\text{P-IV, Q-II, R-I, S-III}$

Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to de...

5.9k views

Ishrat Jahan asked Nov 2, 2014

25 votes

4 answers

4323

GATE IT 2004 | Question: 56
Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree? ... $\text{(A, D), (A, B), (D, F), (F, C), (F, G), (G, E)}$

Consider the undirected graph below:Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges repres...

14.2k views

Ishrat Jahan asked Nov 2, 2014

45 votes

7 answers

4324

GATE IT 2004 | Question: 55
Let $f(n)$, $g(n)$ and $h(n)$ be functions defined for positive integers such that $f(n) = O(g(n))$, $g(n) \neq O(f(n))$, $g(n) = O(h(n))$, and $h(n) = O(g(n))$. Which one of the following statements is FALSE? $f(n) + g(n) = O(h(n) + h(n))$ $f(n) = O(h(n))$ $h(n) \neq O(f(n))$ $f(n)h(n) \neq O(g(n)h(n))$

Let $f(n)$, $g(n)$ and $h(n)$ be functions defined for positive integers such that $f(n) = O(g(n))$, $g(n) \neq O(f(n))$, $g(n) = O(h(n))$, and $h(n) = O(g(n))$.Which one...

13.3k views

Ishrat Jahan asked Nov 2, 2014

25 votes

3 answers

4325

GATE IT 2006 | Question: 52
The following function computes the value of $\binom{m}{n}$ correctly for all legal values $m$ and $n$ ($m ≥1, n ≥ 0$ and $m > n$) int func(int m, int n) { if (E) return 1; else return(func(m -1, n) + func(m - 1, n - 1)); } In the above function, which of the following is the ... $(m = = 1)$ $(n = = 0) || (m = = n)$ $(n = = 0)$ && $(m = = n)$

The following function computes the value of $\binom{m}{n}$ correctly for all legal values $m$ and $n$ ($m ≥1, n ≥ 0$ and $m n$)int func(int m, int n) { if (E) retu...

8.2k views

Ishrat Jahan asked Oct 31, 2014

32 votes

2 answers

4326

GATE IT 2006 | Question: 48
The characters $a$ to $h$ have the set of frequencies based on the first $8$ Fibonacci numbers as follows $a : 1$, $b : 1$, $c : 2$, $d : 3$, $e : 5$, $f : 8$, $g : 13$, $h : 21$ A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code? $110111100111010$ $fdheg$ $ecgdf$ $dchfg$ $fehdg$

The characters $a$ to $h$ have the set of frequencies based on the first $8$ Fibonacci numbers as follows$a : 1$, $b : 1$, $c : 2$, $d : 3$, $e : 5$, $f : 8$, $g : 13$, $...

13.1k views

Ishrat Jahan asked Oct 31, 2014

29 votes

8 answers

4327

GATE IT 2006 | Question: 47
Consider the depth-first-search of an undirected graph with $3$ vertices $P$, $Q$, and $R$. Let discovery time $d(u)$ represent the time instant when the vertex $u$ is first visited, and finish time $f(u)$ represent the time instant when the ... are two connected components, and $Q$ and $R$ are connected There are two connected components, and $P$ and $Q$ are connected

Consider the depth-first-search of an undirected graph with $3$ vertices $P$, $Q$, and $R$. Let discovery time $d(u)$ represent the time instant when the vertex $u$ is fi...

11.2k views

Ishrat Jahan asked Oct 31, 2014

37 votes

7 answers

4328

GATE IT 2006 | Question: 46
Which of the following is the correct decomposition of the directed graph given below into its strongly connected components? $\left \{ P, Q, R, S \right \}, \left \{ T \right \},\left \{ U \right \}, \left \{ V \right \}$ ... $\left \{ P, Q, R, S, T, U, V \right \}$

Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?$\left \{ P, Q, R, S \right \}, \left \{ T \...

11.9k views

Ishrat Jahan asked Oct 31, 2014

6 votes

1 answer

4329

GATE IT 2006 | Question: 10
A problem in NP is NP-complete if it can be reduced to the 3-SAT problem in polynomial time the 3-SAT problem can be reduced to it in polynomial time it can be reduced to any other problem in NP in polynomial time some problem in NP can be reduced to it in polynomial time

A problem in NP is NP-complete ifit can be reduced to the 3-SAT problem in polynomial timethe 3-SAT problem can be reduced to it in polynomial timeit can be reduced to an...

6.1k views

Ishrat Jahan asked Oct 31, 2014

43 votes

6 answers

4330

GATE IT 2007 | Question: 81
Let $P_1, P_2,\dots , P_n $be $n$ points in the $xy$-plane such that no three of them are collinear. For every pair of points $P_i$ and $P_j$, let $L_{ij}$ be the line passing through them. Let $L_{ab}$ ... $\Theta\left(n\right)$ $\Theta\left(n\log n\right)$ $\Theta\left(n\log^2 n\right)$ $\Theta\left(n^2\right)$

Let $P_1, P_2,\dots , P_n $be $n$ points in the $xy$-plane such that no three of them are collinear. For every pair of points $P_i$ and $P_j$, let $L_{ij}$ be the line pa...

6.3k views

Ishrat Jahan asked Oct 30, 2014

52 votes

11 answers

4331

GATE IT 2007 | Question: 24
A depth-first search is performed on a directed acyclic graph. Let $d[u]$ denote the time at which vertex $u$ is visited for the first time and $f[u]$ the time at which the DFS call to the vertex $u$ terminates. Which of the following statements is always TRUE for all edges $(u, v)$ in the graph ? $d[u] < d[v]$ $d[u] < f[v]$ $f[u] < f[v]$ $f[u] > f[v]$

A depth-first search is performed on a directed acyclic graph. Let $d[u]$ denote the time at which vertex $u$ is visited for the first time and $f[u]$ the time at which t...

13.7k views

Ishrat Jahan asked Oct 29, 2014

51 votes

3 answers

4332

GATE IT 2007 | Question: 17
Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute $b^n \bmod{m}, 0 \leq b, n \leq m$ ? $O(\log n)$ $O(\sqrt n)$ $O\Biggl (\frac{n}{\log n} \Biggr )$ $O(n)$

Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications require...

8.8k views

Ishrat Jahan asked Oct 29, 2014

34 votes

4 answers

4333

GATE IT 2007 | Question: 3, UGCNET-June2012-III: 34
Consider a weighted, undirected graph with positive edge weights and let $uv$ be an edge in the graph. It is known that the shortest path from the source vertex $s$ to $u$ has weight 53 and the shortest path from $s$ to $v$ has weight 65. Which one of the ... $(u,v) \leq 12$ Weight $(u,v) = 12$ Weight $(u,v) \geq 12$ Weight $(u,v) > 12$

Consider a weighted, undirected graph with positive edge weights and let $uv$ be an edge in the graph. It is known that the shortest path from the source vertex $s$ to $u...

11.5k views

Ishrat Jahan asked Oct 29, 2014

18 votes

3 answers

4334

GATE IT 2008 | Question: 83
Consider the code fragment written in C below : void f (int n) { if (n <= 1) { printf ("%d", n); } else { f (n/2); printf ("%d", n%2); } } Which of the following implementations will produce the same output for $f(173)$ as the above code? ... { printf ("%d", n%2); f (n/2); } } Both $P1$ and $P2$ $P2$ only $P1$ only Neither $P1$ nor $P2$

Consider the code fragment written in C below : void f (int n) { if (n <= 1) { printf ("%d", n); } else { f (n/2); printf ("%d", n%2); } }Which of the following im...

8.8k views

Ishrat Jahan asked Oct 29, 2014

15 votes

4 answers

4335

GATE IT 2008 | Question: 82
Consider the code fragment written in C below : void f (int n) { if (n <=1) { printf ("%d", n); } else { f (n/2); printf ("%d", n%2); } } What does f(173) print? $010110101$ $010101101$ $10110101$ $10101101$

Consider the code fragment written in C below :void f (int n) { if (n <=1) { printf ("%d", n); } else { f (n/2); printf ("%d", n%2); } }What does f(173) print?$010110101$...

9.3k views

Ishrat Jahan asked Oct 29, 2014

23 votes

3 answers

4336

GATE IT 2008 | Question: 47
Consider the following sequence of nodes for the undirected graph given below: $a$ $b$ $e$ $f$ $d$ $g$ $c$ $a$ $b$ $e$ $f$ $c$ $g$ $d$ $a$ $d$ $g$ $e$ $b$ $c$ $f$ $a$ $d$ $b$ $c$ $g$ $e$ $f$ A Depth First Search (DFS) is started at ... first visited. Which of the above is/are possible output(s)? $1$ and $3$ only $2$ and $3$ only $2, 3$ and $4$ only $1, 2$ and $3$ only

Consider the following sequence of nodes for the undirected graph given below:$a$ $b$ $e$ $f$ $d$ $g$ $c$$a$ $b$ $e$ $f$ $c$ $g$ $d$$a$ $d$ $g$ $e$ $b$ $c$ $f$$a$ $d$ $b$...

8.0k views

Ishrat Jahan asked Oct 28, 2014

30 votes

5 answers

4337

GATE IT 2008 | Question: 45
For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree? $\text{(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)}$ ... $\text{(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)}$

For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Span...

13.4k views

Ishrat Jahan asked Oct 28, 2014

74 votes

9 answers

4338

GATE IT 2008 | Question: 44
When $n = 2^{2k}$ for some $k \geqslant 0$, the recurrence relation $T(n) = √(2) T(n/2) + √n$, $T(1) = 1$ evaluates to : $√(n) (\log n + 1)$ $√(n) \log n$ $√(n) \log √(n)$ $n \log √n$

When $n = 2^{2k}$ for some $k \geqslant 0$, the recurrence relation$T(n) = √(2) T(n/2) + √n$, $T(1) = 1$evaluates to :$√(n) (\log n + 1)$$√(n) \log n$$√(n) \log...

17.4k views

Ishrat Jahan asked Oct 28, 2014

66 votes

7 answers

4339

GATE IT 2008 | Question: 43
If we use Radix Sort to sort $n$ integers in the range $\left (n^{k/2}, n^k \right ]$, for some $k > 0$ which is independent of $n$, the time taken would be? $\Theta(n)$ $\Theta(kn)$ $\Theta(n \log n)$ $\Theta(n^2)$

If we use Radix Sort to sort $n$ integers in the range $\left (n^{k/2}, n^k \right ]$, for some $k 0$ which is independent of $n$, the time taken would be?$\Theta(n)$$\T...

20.8k views

Ishrat Jahan asked Oct 28, 2014

10 votes

3 answers

4340

GATE IT 2008 | Question: 11
For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE? If X can be solved in polynomial time, then so can Y X is NP-complete X is NP-hard X is in NP, but not necessarily NP-complete

For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?If X can be solved in polynomial time, then so can YX is NP-c...

7.1k views

Ishrat Jahan asked Oct 27, 2014

Page:

« prev
1
...
212
213
214
215
216
217
218
219
220
221
222
...
242
next »