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}}}$$

Hot questions in Algorithms

3 votes

3 answers

121

GATE CSE 2024 | Set 1 | Question: 32
Consider the following recurrence relation: $T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text { for } n \geq 1, \\ 1 \quad \text { for } n=1\end{array}\right.$ Which one of the following options is CORRECT? $T(n)=\Theta(n \log \log n)$ $T(n)=\Theta(n \log n)$ $T(n)=\Theta\left(n^2 \log n\right)$ $T(n)=\Theta\left(n^2 \log \log n\right)$

Consider the following recurrence relation:$T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text { for } n \geq 1, \\ 1 \quad \text { for } n=1\end{array}\right.$Whic...

Arjun

2.1k views

Arjun asked Feb 16

1 votes

1 answer

122

GATE CSE 2024 | Set 1 | Question: 31
An array $[82,101,90,11,111,75,33,131,44,93]$ is heapified. Which one of the following options represents the first three elements in the heapified array? $82,90,101$ $82,11,93$ $131,11,93$ $131,111,90$

An array $[82,101,90,11,111,75,33,131,44,93]$ is heapified. Which one of the following options represents the first three elements in the heapified array?$...

Arjun

2.3k views

Arjun asked Feb 16

2 votes

2 answers

123

GATE CSE 2024 | Set 1 | Question: 24
The number of spanning trees in a complete graph of $4$ vertices labelled $\text{A, B, C,}$ and $\text{D}$ is _________.

The number of spanning trees in a complete graph of $4$ vertices labelled $\text{A, B, C,}$ and $\text{D}$ is _________.

Arjun

2.0k views

Arjun asked Feb 16

1 votes

1 answer

124

GATE CSE 2024 | Set 2 | Question: 41
Let $\text{G}$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $\text{G}$ has even weight. Which of the following statements is/are TRUE for every such graph $\text{G}$ ... $\text{C}$ have even weight $\text{OR}$ all edges in $\text{C}$ have odd weight

Let $\text{G}$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $\text{G}$ has even weight. Which o...

Arjun

2.0k views

Arjun asked Feb 16

63 votes

7 answers

125

GATE CSE 2001 | Question: 1.16
Let $f(n) = n^2 \log n$ and $g(n) = n(\log n)^{10}$ be two positive functions of $n$. Which of the following statements is correct? $f(n) = O(g(n)) \text{ and } g(n) \neq O(f(n))$ $g(n) = O(f(n)) \text{ and } f(n) \neq O(g(n))$ $f(n) \neq O(g(n)) \text{ and } g(n) \neq O(f(n))$ $f(n) =O(g(n)) \text{ and } g(n) = O(f(n))$

Let $f(n) = n^2 \log n$ and $g(n) = n(\log n)^{10}$ be two positive functions of $n$. Which of the following statements is correct?$f(n) = O(g(n)) \text{ and } g(n) \neq ...

Kathleen

18.9k views

Kathleen asked Sep 14, 2014

41 votes

4 answers

126

GATE CSE 2017 Set 2 | Question: 50
A message is made up entirely of characters from the set $X=\{P, Q, R, S, T\}$ ... message of $100$ characters over $X$ is encoded using Huffman coding, then the expected length of the encoded message in bits is ______.

A message is made up entirely of characters from the set $X=\{P, Q, R, S, T\}$. The table of probabilities for each of the characters is shown below:$$\begin{array}{|c|c|...

Arjun

21.3k views

Arjun asked Feb 14, 2017

4 votes

2 answers

127

GATE CSE 2024 | Set 1 | Question: 35
Let $G$ be a directed graph and $T$ a depth first search $\text{(DFS)}$ spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth first search $\text{(BFS)}$ tree in $G$, rooted at $v$. Which of the following ... the tree $T$ There are no forward-edge in $G$ with respect to the tree $T$ The only edges in $G$ are the edges in $T$

Let $G$ be a directed graph and $T$ a depth first search $\text{(DFS)}$ spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth fir...

Arjun

3.3k views

Arjun asked Feb 16

59 votes

7 answers

128

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

38 votes

5 answers

129

GATE CSE 2018 | Question: 48
Consider the weights and values of items listed below. Note that there is only one unit of each item. ... The total value of items picked by the greedy algorithm is denoted by $V_{greedy}$. The value of $V_{opt}-V_{greedy}$ is ____

Consider the weights and values of items listed below. Note that there is only one unit of each item.$$\begin{array}{|c|c|c|}\hline \textbf{Item number} & \textbf{Weigh...

gatecse

22.3k views

gatecse asked Feb 14, 2018

60 votes

5 answers

130

GATE CSE 2015 Set 3 | Question: 39
Consider the following recursive C function. void get(int n) { if (n<1) return; get (n-1); get (n-3); printf("%d", n); } If $get(6)$ function is being called in $main()$ then how many times will the $get()$ function be invoked before returning to the $main()$? $15$ $25$ $35$ $45$

Consider the following recursive C function.void get(int n) { if (n<1) return; get (n-1); get (n-3); printf("%d", n); }If $get(6)$ function is being called in $main()$ th...

go_editor

18.2k views

go_editor asked Feb 15, 2015

63 votes

4 answers

131

GATE CSE 2000 | Question: 2.19
Let $G$ be an undirected graph. Consider a depth-first traversal of $G$, and let $T$ be the resulting depth-first search tree. Let $u$ be a vertex in $G$ and let $v$ be the first new (unvisited) vertex visited after visiting $u$ in the traversal. Which of the following ... in $T$ If $\{u, v\}$ is not an edge in $G$ then $u$ and $v$ must have the same parent in $T$

Let $G$ be an undirected graph. Consider a depth-first traversal of $G$, and let $T$ be the resulting depth-first search tree. Let $u$ be a vertex in $G$ and let $v$ be t...

Daggerhunt

18.6k views

Daggerhunt asked Nov 16, 2014

49 votes

8 answers

132

GATE CSE 2016 Set 2 | Question: 11
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n^{\text{th}}$ vertex in this BFS traversal, then the maximum possible value of $n$ is __________

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n^{\text{th}...

Akash Kanase

13.2k views

Akash Kanase asked Feb 12, 2016

10 votes

1 answer

133

GATE CSE 2023 | Question: 46
Let $U=\{1,2,3\}$. Let $2^{U}$ denote the powerset of $U$. Consider an undirected graph $G$ whose vertex set is $2^{U}$. For any $A, B \in 2^{U},(A, B)$ is an edge in $G$ if and only if (i) $A \neq B$, and (ii) ... $A$ is denoted by $\mathcal{B}(A)$. If $\emptyset$ denotes the empty set, then the cardinality of $\mathcal{B}(\emptyset)$ is ______________.

Let $U=\{1,2,3\}$. Let $2^{U}$ denote the powerset of $U$. Consider an undirected graph $G$ whose vertex set is $2^{U}$. For any $A, B \in 2^{U},(A, B)$ is an edge in $G$...

admin

6.4k views

admin asked Feb 15, 2023

47 votes

9 answers

134

GATE CSE 2014 Set 1 | Question: 37
There are $5$ bags labeled $1$ to $5$. All the coins in a given bag have the same weight. Some bags have coins of weight $10$ gm, others have coins of weight $11$ gm. I pick $1, 2, 4, 8, 16$ coins respectively from bags $1$ to $5$ Their total weight comes out to $323$ gm. Then the product of the labels of the bags having $11$ gm coins is ___.

There are $5$ bags labeled $1$ to $5$. All the coins in a given bag have the same weight. Some bags have coins of weight $10$ gm, others have coins of weight $11$ gm. I p...

go_editor

9.6k views

go_editor asked Sep 28, 2014

11 votes

4 answers

135

GATE CSE 2021 Set 2 | Question: 23
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 __________

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

Arjun

5.1k views

Arjun asked Feb 18, 2021

48 votes

5 answers

136

GATE CSE 2009 | Question: 39
In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time complexity of the quick sort? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$

In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time com...

Kathleen

21.3k views

Kathleen asked Sep 22, 2014

35 votes

10 answers

137

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

1 votes

1 answer

138

GATE CSE 2024 | Set 2 | Question: 49
The number of distinct minimum-weight spanning trees of the following graph is

The number of distinct minimum-weight spanning trees of the following graph is

Arjun

1.9k views

Arjun asked Feb 16

12 votes

2 answers

139

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 50
Given an unsorted array of $n$ distinct elements, you want to find this set of $\log n$ elements: those at positions $1,2,4,8,16, \ldots, n/2$ if array were sorted. In other words, find the largest element, the second largest element, the ... the subarray) $\Theta(\log n)$ $\Theta(n)$ $\Theta(n \log n)$ $\Theta\left(n^{2}\right)$

Given an unsorted array of $n$ distinct elements, you want to find this set of $\log n$ elements: those at positions $1,2,4,8,16, \ldots, n/2$ if array were sorted. In ot...

GO Classes

985 views

GO Classes asked Jan 13

21 votes

7 answers

140

GATE CSE 2007 | Question: 5
Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below. Which of the following is not a topological ordering? $1$ $2$ $3$ $4$ $5$ $6$ $1$ $3$ $2$ $4$ $5$ $6$ $1$ $3$ $2$ $4$ $6$ $5$ $3$ $2$ $4$ $1$ $6$ $5$

Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below.Which of the following is not a topological ordering?$1$ $2$ $3$ $4$ $5$ $6$$1$ $3$ $2$ $4$ $5$ $6$$1$ $3$ $2$ $4$...

7.9k views

pC asked Dec 21, 2015

Page:

« prev
1
2
3
4
5
6
7
8
9
10
11
12
...
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