Register

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|c|c|c|c|c|c|}\hline \textbf{Year}& \textbf{2026 - 1}& \textbf{2026 - 2}& \textbf{2025 - 1}& \textbf{2025 - 2}& \textbf{2024 - 1}& \textbf{2024 - 2}& \textbf{2023}& \textbf{2022}& \textbf{2021 - 1}& \textbf{2021 - 2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}\\\hline \textbf{1 Mark Count}&4&4&2&2&1&2&2&2&3&2&1&2.4&4\\\hline \textbf{2 Marks Count}&6&4&3&3&4&2&2&2&3&4&2&3.3&6\\\hline \textbf{Total Marks}&16&12&8&8&9&6&6&6&9&10&\bf{6}&\bf{9}&\bf{16}\\\hline \end{array}}}$$

Filter

Questions without a selected answer in Algorithms

1 1 vote
1 1 answer
204
204 views
GO Classes DPP | GATE CS, DA | Algorithms | Directed Graph
Let $G$ be a directed graph with nonnegative edge weights, and let $s$ and $t$ be vertices of $G$.Consider the statement:Any shortest path from $s$ to $t$ in $G$ is also ...
User Avatar
1 1 vote
1 1 answer
132
132 views
GO Classes DPP | GATE CS, DA | Algorithms | Quick Sort
During sorting, one complete processing of all elements whose final positions have not yet been determined is called a pass.Which of the following sequences cannot be the...
User Avatar
2 2 votes
1 1 answer
90
90 views
GO Classes DPP | GATE CS, DA | Algorithms | Hashing
An initially empty hash table $\text{HT}$ has length $11$.The hash function is:$H(key)=key \bmod 7$Collisions are resolved using linear probing.The following keys are ins...
User Avatar
1 1 vote
1 1 answer
110
110 views
GO Classes DPP | GATE CS, DA | Algorithms | Time Complexity
The algorithm $\text{ALGSORT}$ sorts an array of distinct integers using comparisons.The function $\text{MININDEX(V,i,j)}$ returns the position of the smallest element in...
User Avatar
1 1 vote
1 1 answer
102
102 views
GO Classes DPP | GATE CS, DA | Algorithms | MST vs Shortest Path Tree
Consider the following statement:For every connected weighted graph $G$, there exists some vertex $v$ such that a shortest path tree rooted at $v$ is identical to a minim...
User Avatar
2 2 votes
1 1 answer
90
90 views
GO Classes DPP | GATE CS, DA | Algorithms | Bellman Ford
Consider a simple version of Bellman-Ford algorithm where we initialize $\text{distTo}[s]$ to $0$ and the rest of $\text{distTo}[v]$ to $+\infty$. Then fix an order on al...
User Avatar
1 1 vote
1 1 answer
87
87 views
GO Classes DPP | GATE CS, DA | Algorithms | Dijkstra's Algorithm
Consider Dijkstra's algorithm on a graph having $V$ vertices and $E$ edges.Suppose an indexed priority queue is not used.Instead, the tentative distances are stored only ...
User Avatar
1 1 vote
1 1 answer
62
62 views
GO Classes DPP | GATE CS, DA | Algorithms | Edge Relaxation
Consider a directed edge $e = v \to w$ with weight $7$. Suppose that during a shortest path algorithm:$\operatorname{distTo}[v] = 16$ and $\operatorname{distTo}[w] = 25$...
User Avatar
1 1 vote
1 1 answer
86
86 views
GO Classes DPP | GATE CS, DA | Algorithms | Time Complexity
Suppose Huffman coding is implemented as follows.Initially, the $n$ symbols are stored in a min priority queue according to their frequencies.The algorithm repeatedly per...
User Avatar
1 1 vote
1 1 answer
86
86 views
GO Classes DPP | GATE CS, DA | Algorithms | MST
Let, $G=(V,E)$ be a connected undirected graph. Edge weights may be negative.We want to choose, $E'\subseteq E$ such that $G'=(V,E')$ is connected and: $\sum_{e\in E'}w(e...
User Avatar
0 0 votes
1 1 answer
86
86 views
GO Classes DPP | GATE CS, DA | Algorithms | Dijkstra's Algorithm
Let $G=(V,E)$ be a directed graph with positive edge weights.Given vertices $s,w,t$ we want the length of the shortest path from $s$ to $t$ that must pass through $w$.Con...
User Avatar
2 2 votes
1 1 answer
73
73 views
GO Classes DPP | GATE CS, DA | Algorithms | Floyd-Warshall
What is the primary reason to use Floyd's algorithm for the all-pairs shortest-path problem instead of Dijkstra's algorithm?Faster for dense graphs. Faster for sparse gra...
User Avatar
0 0 votes
1 1 answer
116
116 views
GO Classes DPP | GATE CS, DA | Algorithms | Binary Search
Which of the following cannot be a sequence of keys compared during a binary search for some target key?$500,200,450,180$ $500,450,200,180$ $180,500,200,450$ $180,200,500...
User Avatar
0 0 votes
1 1 answer
59
59 views
GO Classes DPP | GATE CS, DA | Algorithms | Time Complexity
Consider,f1(N): x = 0 for i = 0 to N - 1: x++ return xand,f2(N, R): x = 0 for i = 0 to N - 1: for j = 1; j <= R; j = j + j: x = x + f1(j) return xWhat is the order of gro...
User Avatar
1 1 vote
1 1 answer
105
105 views
GO Classes DPP | GATE CS, DA | Algorithms | Dijkstra's Algorithm
Let $G$ be a directed graph with nonnegative edge weights.Run Dijkstra's algorithm from source $s$. After the algorithm terminates, use the $\text{prev}$ pointers to cons...
User Avatar
0 0 votes
1 1 answer
76
76 views
GO Classes DPP | GATE CS, DA | Algorithms | Minimum Spanning Tree
Consider the following statements.Let $M$ be an MST of a connected undirected graph with positive edge weights. If $7$ is added to every edge weight, $M$ is guaranteed to...
User Avatar
1 1 vote
1 1 answer
74
74 views
GO Classes DPP | GATE CS, DA | Algorithms | Bellman-Ford
Consider the following directed weighted graph with source vertex $0$:Bellman-Ford performs one complete pass, relaxing edges in this exact order:$$0\rightarrow1,\quad 0\...
User Avatar
2 2 votes
1 1 answer
105
105 views
GO Classes DPP | GATE CS, DA | Algorithms | Analysis of Algorithms
The following running times are observed for a program:$$\begin{array}{|c|c|}\hlineN & \text{Running time} \\\hline1000 & 0.1\text{ seconds} \\2000 & 0.3\text{ seconds} \...
User Avatar
0 0 votes
1 1 answer
67
67 views
GO Classes DPP | GATE CS, DA | Algorithms | Linear Probing
A linear-probing hash table of length $10$ uses:$h(k) = k \bmod 10$After inserting eight keys into an initially empty table, the table is:$$\begin{array}{|c|c|c|c|c|c|c|c...
User Avatar
1 1 vote
1 1 answer
98
98 views
GO Classes DPP | GATE CS, DA | Algorithms | Minimum Spanning Tree
Let $G=(V,E)$ be a connected weighted undirected graph in which all edge weights are distinct.Let, $e=(u,v)$ be an edge of weight $w(e)$.Construct a graph $G'$ containing...
User Avatar
0 0 votes
1 1 answer
75
75 views
GO Classes DPP | GATE CS, DA | Algorithms | Sorting Complexity
Let $P$ be the problem of sorting $n\geq1$ elements using only comparisons.Consider the class of all comparison-based algorithms that correctly solve $P$.What is the asym...
User Avatar
0 0 votes
1 1 answer
84
84 views
GO Classes DPP | GATE CS, DA | Algorithms | Hash Collision Handling
When hashing is used for table addressing, a collision-resolution method is generally required.Why?Collision handling is required only when the table is completely full. ...
User Avatar
0 0 votes
1 1 answer
96
96 views
GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Analysis
Let $T_A(n)$ and $T_B(n)$ denote the worst-case running times of two algorithms $A$ and $B$ that solve the same problem.We say that $A$ is asymptotically more efficient t...
User Avatar
0 0 votes
1 1 answer
55
55 views
GO Classes DPP | GATE CS, DA | Algorithms | Dijkstra's Algorithm
Suppose every edge weight of a graph is either:a positive integer, or exactly $-1$.Consider the statement:Dijkstra's algorithm will always compute the correct shortest-pa...
User Avatar
3 3 votes
1 1 answer
139
139 views
GO Classes DPP | GATE CS, DA | Algorithms | Dijkstra's Algorithm
Consider the following code executed while processing vertex $v$:for each edge e in G.adj(v): w = e.to() if dist[w] dist[v] + e.weight(): dist[w] = dist[v] + e.weight() ...
User Avatar
4 4 votes
1 1 answer
87
87 views
GO Classes DPP | GATE CS, DA | Algorithms | Minimum Spanning Trees
Consider the statement:The minimum spanning tree of a connected weighted graph $G$ is unique if and only if all edge weights in $G$ are distinct.True False
User Avatar
1 1 vote
1 1 answer
109
109 views
GO Classes DPP | GATE CS, DA | Algorithms | Divide & Conquer
Consider three recursive algorithms.Algorithm $\mathbf{1}$Divides a problem of size $N$ into two subproblems of size $N/2$ and performs constant additional work.$T_1(N)=2...
User Avatar
2 2 votes
1 1 answer
86
86 views
GO Classes DPP | GATE CS, DA | Algorithms | Selection Algorithms
Let, $L=\langle r_1,r_2,\ldots,r_n\rangle$ be an arbitrary list of integers, not necessarily distinct.Which of the following statements is incorrect?There exists an optim...
User Avatar
2 2 votes
1 1 answer
80
80 views
GO Classes DPP | GATE CS, DA | Algorithms | Complexity Analysis
Consider the following recursive function $\texttt{Pot}$, which computes $x^n$, where $x$ is real and $n$ is an integer.Pot(x, n): if x == 0: return 0 if n == 0: return 1...
User Avatar
2 2 votes
1 1 answer
100
100 views
GO Classes DPP | GATE CS, DA | Algorithms | Dynamic Programming
True or False:In every dynamic-programming solution, the asymptotic space requirement must be at least as large as the total number of distinct subproblems.True False
User Avatar
To see more, click for the full list of questions or popular tags.