Skip to content
GATETECH

GATE CS Algorithms questions

Practise Algorithms questions for GATE CS. Explore official PYQs and original subject-wise quizzes, check answers and view available solutions. Free, no sign-in.

Compare greedy choices, dynamic-programming states and graph algorithms. Identify the input size before analysing the time and space complexity of each solution.

Subject, topic, year and type filter the full library. Match any choice within a filter, and all selected filter categories. Search, source and sort apply to this page.

20 on this page
Official PYQ2014AlgorithmsGraph Traversals (BFS, DFS)MCQ · 1 mark
Let GG be a graph with nn vertices and mm edges. What is the tightest upper bound on the running time of Depth First Search on GG, when GG is represented as an adjacency matrix?
Official PYQ2014AlgorithmsMinimum Spanning TreesNAT · 1 mark
The number of distinct minimum spanning trees for the weighted graph below is _____
Official PYQ2014AlgorithmsSearching, Sorting, HashingNAT · 1 mark
Suppose P,Q,R,S,TP, Q, R, S, T are sorted sequences having lengths 20,24,30,35,5020, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.
Official PYQ2014AlgorithmsAlgorithm Design: Dynamic ProgrammingNAT · 1 mark
Consider two strings AA = "qpqrr" and BB = "pqprqrp". Let xx be the length of the longest common subsequence (not necessarily contiguous) between AA and BB and let yy be the number of such longest common subsequences between AA and BB. Then x+10y=x +10y= ___.
Official PYQ2014AlgorithmsGraph Traversals (BFS, DFS)MCQ · 1 mark
Consider the tree arcs of a BFS traversal from a source node WW in an unweighted, connected, undirected graph. The tree TT formed by the tree arcs is a data structure for computing
Official PYQ2014AlgorithmsAsymptotic Worst Case Time and Space ComplexityMCQ · 1 mark
Which one of the following correctly determines the solution of the recurrence relation with T(1)=1T(1) = 1? T(n)=2T(n2)+log⁡nT(n)= 2T\left(\frac {n} {2}\right) + \log n
Official PYQ2014AlgorithmsAsymptotic Worst Case Time and Space ComplexityNAT · 1 mark
Consider the function func shown below: int func(int num) { int count = 0; while (num) { count++; num>>= 1; } return (count); } The value returned by func(435435) is ________
Official PYQ2014AlgorithmsAlgorithm Design: Dynamic ProgrammingNAT · 1 mark
Suppose you want to move from 00 to 100100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i, j with i<ji,\:j \:\text{with}\: i <j. Given a shortcut (i,j)(i,j), if you are at position ii on the number line, you may directly move to jj. Suppose T(k)T(k) …
Official PYQ2014AlgorithmsSearching, Sorting, HashingMCQ · 1 mark
You have an array of nn elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
Official PYQ2014AlgorithmsGraph Traversals (BFS, DFS)NAT · 1 mark
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.
Official PYQ2014AlgorithmsAsymptotic Worst Case Time and Space ComplexityMCQ · 1 mark
Let AA be the square matrix of size n×nn \times n. Consider the following pseudocode. What is the expected output? C=100; for i=1 to n do for j=1 to n do { Temp = A[i][j]+C; A[i][j] = A[j][i]; A[j][i] = Temp -C; } for i=1 to n do for j=1 to n do output (A[i][j]);
Official PYQ2013AlgorithmsAsymptotic Worst Case Time and Space ComplexityMCQ · 1 mark
Consider the following function: int unknown(int n){ int i, j, k=0; for (i=n/2; i<=n; i++) for (j=2; j<=n; j=j*2) k = k + n/2; return (k); } The return value of the function is
Official PYQ2013AlgorithmsSearching, Sorting, HashingMCQ · 1 mark
The number of elements that can be sorted in Θ(log⁡n)\Theta(\log n) time using heap sort is
Official PYQ2013AlgorithmsShortest Paths (Dijkstra, Bellman-Ford)MCQ · 1 mark
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
Official PYQ2013AlgorithmsSearching, Sorting, HashingMCQ · 1 mark
Which one of the following is the tightest upper bound that represents the number of swaps required to sort nn numbers using selection sort?
Official PYQ2012AlgorithmsSearching, Sorting, HashingMCQ · 1 mark
A list of nn strings, each of length nn, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
Official PYQ2012AlgorithmsMinimum Spanning TreesMCQ · 1 mark
Let GG be a weighted graph with edge weights greater than one and G′G' be the graph constructed by squaring the weights of edges in GG. Let TT and T′T' be the minimum spanning trees of GG and G′G', respectively, with total weights tt and t′t'. Which of the following statements is TRUE?
Official PYQ2012AlgorithmsAsymptotic Worst Case Time and Space ComplexityMCQ · 1 mark
Let W(n)W(n) and A(n)A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size nn. Which of the following is ALWAYS TRUE?
Official PYQ2012AlgorithmsAsymptotic Worst Case Time and Space ComplexityMCQ · 1 mark
The recurrence relation capturing the optimal execution time of the Towers of HanoiTowers \ of \ Hanoi problem with nn discs is
Official PYQ2011AlgorithmsMinimum Spanning TreesMCQ · 1 mark
An undirected graph G(V,E)G(V,E) contains n (n>2)n \: (n>2) nodes named v1,v2,…,vnv_1,v_2, \dots, v_n. Two nodes vi,vjv_i, v_j are connected if and only if 0<∣i−j∣≤20 < \mid i-j\mid \leq 2. Each edge (vi,vj)(v_i,v_j) is assigned a weight i+ji+j. A sample graph with n=4n=4 is shown below. The length of the path from v5v_5 to v6v_6 in the MST of previous question with …