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

15 votes

7 answers

4361

GATE CSE 2004 | Question: 30, ISRO2017-10
The problem $\text{3-SAT}$ and $\text{2-SAT}$ are both in $\text{P}$ both $\text{NP}$ complete $\text{NP}$-complete and in $\text{P}$ respectively undecidable and $\text{NP}$ complete respectively

The problem $\text{3-SAT}$ and $\text{2-SAT}$ are both in $\text{P}$both $\text{NP}$ complete$\text{NP}$-complete and in $\text{P}$ respectivelyundecidable and $\text{NP}...

Kathleen

11.8k views

Kathleen asked Sep 18, 2014

77 votes

5 answers

4362

GATE CSE 2004 | Question: 29
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of $n$ $n^2$ $n \log n$ $n \log^2n$

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of$n$$n^2$$n \log n$$n \log^2n$

Kathleen

33.5k views

Kathleen asked Sep 18, 2014

59 votes

7 answers

4363

GATE CSE 2006 | Question: 17
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 it in linear time using ... pass of the array solves it using divide and conquer in time $\Theta (n\log n)$ solves it in time $\Theta( n^2)$

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 i...

Rucha Shelke

17.9k views

Rucha Shelke asked Sep 17, 2014

21 votes

5 answers

4364

GATE CSE 2006 | Question: 16, ISRO-DEC2017-27
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? R is NP-complete R is NP-hard Q is NP-complete Q is NP-hard

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Whic...

Rucha Shelke

18.1k views

Rucha Shelke asked Sep 17, 2014

35 votes

10 answers

4365

GATE CSE 2006 | Question: 15
Consider the following C-program fragment in which $i$, $j$ and $n$ are integer variables. for( i = n, j = 0; i > 0; i /= 2, j +=i ); Let $val(j)$ denote the value stored in the variable $j$ after termination of the for loop. Which one of the following is true? $val(j)=\Theta(\log n)$ $val(j)=\Theta (\sqrt{n})$ $val(j)=\Theta( n)$ $val(j)=\Theta (n\log n)$

Consider the following C-program fragment in which $i$, $j$ and $n$ are integer variables. for( i = n, j = 0; i 0; i /= 2, j +=i );Let $val(j)$ denote the value stored i...

Rucha Shelke

19.5k views

Rucha Shelke asked Sep 17, 2014

39 votes

4 answers

4366

GATE CSE 2006 | Question: 14, ISRO2011-14
Which one of the following in place sorting algorithms needs the minimum number of swaps? Quick sort Insertion sort Selection sort Heap sort

Which one of the following in place sorting algorithms needs the minimum number of swaps?Quick sortInsertion sortSelection sortHeap sort

Rucha Shelke

25.4k views

Rucha Shelke asked Sep 17, 2014

56 votes

7 answers

4367

GATE CSE 2003 | Question: 88
In the following $C$ program fragment, $j$, $k$, $n$ and TwoLog_n are integer variables, and $A$ is an array of integers. The variable $n$ is initialized to an integer $\geqslant 3$, and TwoLog_n is initialized to the value of $2^*\lceil \log_2(n) \rceil$ for (k = 3; k ... $\left\{m \mid m \leq n, \text{m is prime} \right\}$ { }

In the following $C$ program fragment, $j$, $k$, $n$ and TwoLog_n are integer variables, and $A$ is an array of integers. The variable $n$ is initialized to an integer $\...

Kathleen

12.3k views

Kathleen asked Sep 17, 2014

61 votes

4 answers

4368

GATE CSE 2003 | Question: 70
Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_{k+1}) \in E$ for all $k$ in $i$ through $j-1$. A simple path is a path in ... length from $j$ to $k$ If there exists a path from $j$ to $k$, every simple path from $j$ to $k$ contains at most $A[j,k]$ edges

Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_{k+1})...

Kathleen

17.6k views

Kathleen asked Sep 17, 2014

50 votes

11 answers

4369

GATE CSE 2003 | Question: 69
The following are the starting and ending times of activities $A, B, C, D, E, F, G$ and $H$ ... a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required? $3$ $4$ $5$ $6$

The following are the starting and ending times of activities $A, B, C, D, E, F, G$ and $H$ respectively in chronological order: $“a_s \: b_s \: c_s \: a_e \: d_s \: c_...

Kathleen

14.4k views

Kathleen asked Sep 17, 2014

25 votes

3 answers

4370

GATE CSE 2003 | Question: 68
What is the weight of a minimum spanning tree of the following graph? $29$ $31$ $38$ $41$

What is the weight of a minimum spanning tree of the following graph?$29$$31$$38$$41$

Kathleen

7.6k views

Kathleen asked Sep 17, 2014

86 votes

5 answers

4371

GATE CSE 2003 | Question: 67
Let $G =(V,E)$ be an undirected graph with a subgraph $G_1 = (V_1, E_1)$. Weights are assigned to edges of $G$ as follows. $w(e) = \begin{cases} 0 \text{, if } e \in E_1 \\1 \text{, otherwise} \end{cases}$ A single-source shortest path ... edges in the shortest paths from $v_1$ to all vertices of $G$ $G_1$ is connected $V_1$ forms a clique in $G$ $G_1$ is a tree

Let $G =(V,E)$ be an undirected graph with a subgraph $G_1 = (V_1, E_1)$. Weights are assigned to edges of $G$ as follows.$$w(e) = \begin{cases} 0 \text{, if } e \in E_...

Kathleen

20.1k views

Kathleen asked Sep 17, 2014

66 votes

12 answers

4372

GATE CSE 2003 | Question: 61
In a permutation $a_1 ... a_n$, of n distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i > a_j$. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of $1. . . n$? $\frac{n(n-1)}{2}$ $\frac{n(n-1)}{4}$ $\frac{n(n+1)}{4}$ $2n[\log_2n]$

In a permutation $a_1 ... a_n$, of n distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i a_j$.If all permutations are equally likel...

Kathleen

22.1k views

Kathleen asked Sep 17, 2014

52 votes

7 answers

4373

GATE CSE 2003 | Question: 35
Consider the following recurrence relation $T(1)=1$ $T(n+1) = T(n)+\lfloor \sqrt{n+1} \rfloor$ for all $n \geq 1$ The value of $T(m^2)$ for $m \geq 1$ is $\frac{m}{6}\left(21m-39\right)+4$ $\frac{m}{6}\left(4m^2-3m+5\right)$ $\frac{m}{2}\left(3m^{2.5}-11m+20\right)-5$ $\frac{m}{6}\left(5m^3-34m^2+137m-104\right)+\frac{5}{6}$

Consider the following recurrence relation$T(1)=1$$T(n+1) = T(n)+\lfloor \sqrt{n+1} \rfloor$ for all $n \geq 1$The value of $T(m^2)$ for $m \geq 1$ is$\frac{m}{6}\left(21...

Kathleen

13.9k views

Kathleen asked Sep 16, 2014

63 votes

2 answers

4374

GATE CSE 2003 | Question: 22
The usual $\Theta(n^2)$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running ... $\Theta(n^2)$ become $\Theta(n (\log n)^2)$ become $\Theta(n \log n)$ become $\Theta(n)$

The usual $\Theta(n^2)$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already ...

Kathleen

15.8k views

Kathleen asked Sep 16, 2014

24 votes

5 answers

4375

GATE CSE 2003 | Question: 21
Consider the following graph: Among the following sequences: abeghf abfehg abfhge afghbe Which are the depth-first traversals of the above graph? I, II and IV only I and IV only II, III and IV only I, III and IV only

Consider the following graph: Among the following sequences:abeghfabfehgabfhgeafghbeWhich are the depth-first traversals of the above graph?I, II and IV onlyI and IV only...

Kathleen

13.2k views

Kathleen asked Sep 16, 2014

53 votes

3 answers

4376

GATE CSE 2003 | Question: 20
Consider the following three claims: $(n+k)^m = \Theta(n^m)$ where $k$ and $m$ are constants $2^{n+1} = O(2^n)$ $2^{2n+1} = O(2^n)$ Which of the following claims are correct? I and II I and III II and III I, II, and III

Consider the following three claims:$(n+k)^m = \Theta(n^m)$ where $k$ and $m$ are constants$2^{n+1} = O(2^n)$$2^{2n+1} = O(2^n)$Which of the following claims are correct?...

Kathleen

18.7k views

Kathleen asked Sep 16, 2014

15 votes

3 answers

4377

GATE CSE 2003 | Question: 12
Ram and Shyam have been asked to show that a certain problem $\Pi$ is $\text{NP-complete}.$ Ram shows a polynomial time reduction from the $\text{3-SAT}$ problem to $\Pi$, and Shyam shows a polynomial time reduction from $\Pi$ to $\text{3-SAT.}$ Which of ... not NP-complete $\Pi$ is in NP, but is not NP-complete $\Pi$ is NP-complete $\Pi$ is neither NP-hard, nor in NP

Ram and Shyam have been asked to show that a certain problem $\Pi$ is $\text{NP-complete}.$ Ram shows a polynomial time reduction from the $\text{3-SAT}$ problem to $\Pi$...

Kathleen

8.2k views

Kathleen asked Sep 16, 2014

27 votes

3 answers

4378

GATE CSE 2003 | Question: 1
Consider the following $C$ function. For large values of $y$, the return value of the function $f$ best approximates float f,(float x, int y) { float p, s; int i; for (s=1,p=1,i=1; i<y; i++) { p *= x/i; s += p; } return s; } $x^y$ $e^x$ $\text{ln} (1+x)$ $x^x$

Consider the following $C$ function.For large values of $y$, the return value of the function $f$ best approximatesfloat f,(float x, int y) { float p, s; int i; for (s=1,...

Kathleen

10.3k views

Kathleen asked Sep 16, 2014

59 votes

7 answers

4379

GATE CSE 2006 | Question: 12
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: Queue Stack Heap B-Tree

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:QueueStackHeapB-Tree

Rucha Shelke

31.6k views

Rucha Shelke asked Sep 16, 2014

32 votes

7 answers

4380

GATE CSE 2006 | Question: 11
Consider a weighted complete graph $G$ on the vertex set $\{v_1,v_2,.....v_n\}$ such that the weight of the edge $(v_i, v_j)$ is $2|i-j|$. The weight of a minimum spanning tree of $G$ is: $n-1$ $2n-2$ $\begin{pmatrix} n \\ 2 \end{pmatrix}$ $n^2$

Consider a weighted complete graph $G$ on the vertex set $\{v_1,v_2,.....v_n\}$ such that the weight of the edge $(v_i, v_j)$ is $2|i-j|$. The weight of a minimum spanni...

Rucha Shelke

14.9k views

Rucha Shelke asked Sep 16, 2014

Page:

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

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true