Question:
Consider a directed graph \( G = (V,E) \), where \( V = \{0,1,2,\dots,100\} \) and
\[ E = \{(i,j) : 0<j - i \leq 2, \text{ for all } i,j \in V \}. \]
Suppose the adjacency list of each vertex is in \textit{decreasing order of vertex number, and depth-first search (DFS) is performed at vertex 0. The number of vertices that will be discovered after vertex 50 is:}
Consider a directed graph \( G = (V,E) \), where \( V = \{0,1,2,\dots,100\} \) and
\[ E = \{(i,j) : 0<j - i \leq 2, \text{ for all } i,j \in V \}. \]
Suppose the adjacency list of each vertex is in \textit{decreasing order of vertex number, and depth-first search (DFS) is performed at vertex 0. The number of vertices that will be discovered after vertex 50 is:}
Show Hint
When DFS is performed with an adjacency list sorted in decreasing order, higher-numbered vertices are visited first, affecting the traversal order significantly.
Updated On: Feb 3, 2026
Show Solution
Verified By Collegedunia
Correct Answer: 75
Solution and Explanation
Step 1: Understanding the graph structure.
Each vertex \( i \) has directed edges to \( i+1 \) and \( i+2 \), if they exist.
The adjacency list is sorted in decreasing order, meaning DFS explores the highest-numbered neighbor first. Step 2: DFS traversal starting from vertex 0.
DFS starts at 0 and always visits the highest-numbered connected vertex first.
This results in the traversal order: 0, 2, 4, ..., reaching 100 first.
After backtracking, vertices in the range \( 1, 3, 5, \dots \) get visited.
Step 3: Counting vertices discovered after vertex 50.
Since DFS reaches 100 before backtracking, all vertices from 51 to 100 are discovered after 50.
The number of such vertices is \( 100 - 25 = 75 \).
Thus, the number of vertices discovered after vertex 50 is: \[ 75. \]
Each vertex \( i \) has directed edges to \( i+1 \) and \( i+2 \), if they exist.
The adjacency list is sorted in decreasing order, meaning DFS explores the highest-numbered neighbor first. Step 2: DFS traversal starting from vertex 0.
DFS starts at 0 and always visits the highest-numbered connected vertex first.
This results in the traversal order: 0, 2, 4, ..., reaching 100 first.
After backtracking, vertices in the range \( 1, 3, 5, \dots \) get visited.
Step 3: Counting vertices discovered after vertex 50.
Since DFS reaches 100 before backtracking, all vertices from 51 to 100 are discovered after 50.
The number of such vertices is \( 100 - 25 = 75 \).
Thus, the number of vertices discovered after vertex 50 is: \[ 75. \]
Was this answer helpful?
0
0
Top GATE DA Computer Science Questions
A recursive function is given:
def mystery(n):
if n $<=$ 0:
return 1
else:
return mystery(n-1) + mystery(n-2)
Find the value of mystery(4).- GATE DA - 2026
- Computer Science
- Programming Languages
- def append_to_lst(val, lst=[]):
lst.append(val)
return lst
print(append_to_lst(1))
print(append_to_lst(2))
print(append_to_lst(3, []))- GATE DA - 2026
- Computer Science
- Programming Languages
def fun(L, i=0):
if i $>=$ len(L) - 1:
return 0
if L[i]> L[i+1]:
L[i+1], L[i] = L[i], L[i+1]
return 1 + fun(L, i+1)
else:
return fun(L, i+1)
data = [5, 3, 4, 1, 2]
count = 0
for _ in range(len(data)):
count += fun(data)
print(count)
- GATE DA - 2026
- Computer Science
- Programming Languages
- Assume a typical runtime stack is used for the recursive function mystery(n) as defined earlier. How many total function calls (stack activations), including the initial call, are made to compute mystery(4)?
- GATE DA - 2026
- Computer Science
- Programming Languages
- def outer():
x = []
def inner(val):
x.append(val)
return x
return inner
f1 = outer()
f2 = outer()
print(f1(10)) \# line P
print(f1(20)) \# line Q
print(f2(30)) \# line R
print(f1(40)) \# line S
Which of the following is/are correct?- GATE DA - 2026
- Computer Science
- Programming Languages
View More Questions
Top GATE DA Data Structures Questions
- Consider a hash table of size 10 with indices \( \{0, 1, \dots, 9\} \), with the hash function \[ h(x) = 3x \, (\text{mod} \, 10), \] where linear probing is used to handle collisions. The hash table is initially empty and then the following sequence of keys is inserted into the hash table: 1, 4, 5, 6, 14, 15. The indices where the keys 14 and 15 are stored are, respectively:
- GATE DA - 2025
- Computer Science
- Data Structures
- Consider the following pseudocode.
Create empty stack S Set x = 0, flag = 0, sum = 0 Push x onto S while (S is not empty){ if (flag equals 0){ Set x = x + 1 Push x onto S } if (x equals 8): Set flag = 1 if (flag equals 1){ x = Pop(S) if (x is odd): Pop(S) Set sum = sum + x } } Output sumThe value of \( sum \) output by a program executing the above pseudocode is:- GATE DA - 2025
- Computer Science
- Data Structures
Consider a directed graph \( G = (V,E) \), where \( V = \{0,1,2,\dots,100\} \) and
\[ E = \{(i,j) : 0 < j - i \leq 2, \text{ for all } i,j \in V \}. \] Suppose the adjacency list of each vertex is in decreasing order of vertex number, and depth-first search (DFS) is performed at vertex 0. The number of vertices that will be discovered after vertex 50 is:- GATE DA - 2025
- Computer Science
- Data Structures
- Consider the following pseudocode.
Create empty stack S Set x = 0, flag = 0, sum = 0 Push x onto S while (S is not empty){ if (flag equals 0){ Set x = x + 1 Push x onto S } if (x equals 8): Set flag = 1 if (flag equals 1){ x = Pop(S) if (x is odd): Pop(S) Set sum = sum + x } } Output sumThe value of \( sum \) output by a program executing the above pseudocode is:- GATE DA - 2025
- Computer Science
- Data Structures
Top GATE DA Questions
- Rishi and Swathi are students of Class 5. Pavan and Tanvi are students of Class 4. Rishi and Pavan are boys. Swathi and Tanvi are girls. These four students played a total of three games of chess. The games were played one after another. A player who lost a game did not participate in any more games. It was observed that:
1. The first game was the only game where two students of the same class played against each other.
2. The students of Class 5 won more games than the students of Class 4.
3. The boys won 2 games and the girl won 1 game.
The student who did not lose any game is:- GATE DA - 2026
- Logical Reasoning
Consider two distinct positive numbers \( m, n \) with \( m > n \). Let \[ x = n^{\log_n m}, \quad y = m^{\log_m n}. \] The relation between \( x \) and \( y \) is -
- GATE DA - 2026
- Logarithms
- Consider the supervised learning task. The objective function being minimized is \( f(w) = w \cdot x \), where \( w \in \mathbb{R} \) is the parameter. Stochastic Gradient Descent with learning rate of 0.10. Let \( w = 10.00 \) be the \( i^{\text{th}} \) iteration (\( w_i \)). The value of \( w \) at the end of iteration \( (i+1) \) is if \( x = 10 \) ________. Round off 2 decimal.
- GATE DA - 2026
- Machine Learning
- The value of \[ \sum_{j=0}^{\infty} \sum_{i=1}^{\infty} 2^{-j} 3^{-i} \] is ________.
- GATE DA - 2026
- Sequences and Series
- Consider the Ridge LRR is being used to learn prediction function \( y_{\text{pred}} = w^T x \) where \( w, x \in \mathbb{R}^2 \) & mean absolute error (MAE) is used to measure the prediction error. A weight of 0.20 is associated with the regularizer. At an intermediate step of training process assume that the parameter \( w = [-3.00, 4.00]^T \). In the next step for the I/P \( x = [1.00, 2.00]^T \), the predicted value of \( y \) is noted. Let the relation b/w \( x = [x_1, x_2]^T \) & the true value of \( y \) be \( y_{\text{true}} = x_1 + x_2 \). The value of the overall regularized loss for instance is __________ (upto 2 decimal).
- GATE DA - 2026
- Machine Learning
View More Questions