Algorithms

Topics

• Asymptotic Analysis and Time/Space Complexity 42
• Searching and Sorting Algorithms 23
• Divide and Conquer 7
• Greedy Algorithms 13
• Dynamic Programming 15
• Graph Traversals, Topological Sort and Connectivity 24
• Minimum Spanning Trees 17
• Single-Source and All-Pairs Shortest Paths 6

All Algorithms questions

Hide the 1 question not in the current syllabus

1. GATE CS 2026 Set 1MCQ1 markMedium (estimate)

   GATE CS 2026 Set 1, Q.17

   Consider the following recurrence relations: For all $n>1$, $T_1(n)=4T_1\left(\frac{n}{2}\right)+T_2(n)$ $T_2(n)=5T_2\left(\frac{n}{4}\right)+\Theta ({\log }_{2}n)$ Ass...

   Asymptotic Analysis and Time/Space Complexity

2. GATE CS 2026 Set 1MCQ2 marksMedium (estimate)

   GATE CS 2026 Set 1, Q.41

   Let $G(V,E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the n...

   Single-Source and All-Pairs Shortest Paths

3. GATE CS 2026 Set 1MSQ2 marksMedium (estimate)

   GATE CS 2026 Set 1, Q.49

   Let $G(V,E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G$ is/are true?

   Minimum Spanning Trees

4. GATE CS 2026 Set 1MSQ2 marksMedium (estimate)

   GATE CS 2026 Set 1, Q.50

   Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G(V,E)$ as input, where $d[v]$ and $f[v]$ are the discovery time and fini...

   Graph Traversals, Topological Sort and Connectivity

5. GATE CS 2026 Set 1MSQ2 marksEasy (estimate)

   GATE CS 2026 Set 1, Q.55

   An undirected, unweighted, simple graph $G(V,E)$ is said to be 2-colorable if there exists a function $c:V\to \{0,1\}$ such that for every $(u,v)\in E$…

   Graph Traversals, Topological Sort and Connectivity

6. GATE CS 2026 Set 2MCQ1 markEasy (estimate)

   GATE CS 2026 Set 2, Q.24

   Consider the following functions, where $n$ is a positive integer. $n^{1/3},\log (n),\log (n!),2^{\log (n)}$ Which one of the following options lists the fun...

   Asymptotic Analysis and Time/Space Complexity

7. GATE CS 2026 Set 2MSQ1 markEasy (estimate)

   GATE CS 2026 Set 2, Q.25

   Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $\Theta (n)$?

   Asymptotic Analysis and Time/Space Complexity

8. GATE CS 2026 Set 2NAT1 markEasy (estimate)

   GATE CS 2026 Set 2, Q.32

   Consider an array $A=[10,7,8,19,41,35,25,31]$. Suppose the merge sort algorithm is executed on array $A$ to sort it in increasing order. The merge sort algorithm will c...

   Divide and Conquer

9. GATE CS 2026 Set 2MCQ2 marksEasy (estimate)

   GATE CS 2026 Set 2, Q.37

   Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$, which one of the following options gives the worst case t...

   Single-Source and All-Pairs Shortest Paths

10. GATE CS 2026 Set 2MCQ2 marksEasy (estimate)

    GATE CS 2026 Set 2, Q.38

    Consider an array $A$ of integers of size $n$. The indices of $A$ run from $1$ to $n$. An algorithm is to be designed to check whether $A$ satisfies the condition given below.…

    Searching and Sorting Algorithms

11. GATE CS 2026 Set 2MCQ2 marksMedium (estimate)

    GATE CS 2026 Set 2, Q.39

    Consider a table $T$, where the elements $T[i][j]$, $0\le i,j\le n$, represent the cost of the optimal solutions of different subproblems of a problem that is being solved us...

    Dynamic Programming

12. GATE CS 2025 Set 1MCQ1 markEasy (estimate)

    GATE CS 2025 Set 1, Q.18

    Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$. For any two vertices, $u$ and $v$, let $d_1(u,v)$ and $d_2(u,v)$ be the...

    Minimum Spanning Trees

13. GATE CS 2025 Set 1MCQ1 markEasy (estimate)

    GATE CS 2025 Set 1, Q.20

    Consider the following recurrence relation: $T(n)=2T(n-1)+n{2}^n\text{ for }n>0,T(0)=1.$ Which ONE of the following options is CORRECT?

    Asymptotic Analysis and Time/Space Complexity

14. GATE CS 2025 Set 1NAT1 markEasy (estimate)

    GATE CS 2025 Set 1, Q.33

    The pseudocode of a function fun() is given below: fun(int A[0,...,n-1]){ for i=0 to n-2 for j=0 to n-i-2 if (A[j]>A[j+1]) then swap A[j] and A[j+1] } Let $A[0,\dots ,29]$ be...

    Searching and Sorting Algorithms

15. GATE CS 2025 Set 1MCQ2 marksMedium (estimate)

    GATE CS 2025 Set 1, Q.43

    Let $G(V,E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u,v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the m...

    Graph Traversals, Topological Sort and Connectivity

16. GATE CS 2025 Set 1NAT2 marksMedium (estimate)

    GATE CS 2025 Set 1, Q.64

    The maximum value of $x$ such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is _________ . (answer in integer) An undirec...

    Minimum Spanning Trees

17. GATE CS 2025 Set 2MCQ1 markEasy (estimate)

    GATE CS 2025 Set 2, Q.20

    Consider an unordered list of $N$ distinct integers. What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

    Searching and Sorting Algorithms

18. GATE CS 2025 Set 2MSQ1 markMedium (estimate)

    GATE CS 2025 Set 2, Q.29

    Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph $G$ is/are TRUE?

    Graph Traversals, Topological Sort and Connectivity

19. GATE CS 2025 Set 2MCQ2 marksEasy (estimate)

    GATE CS 2025 Set 2, Q.37

    Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge. Which ONE of the following st...

    Minimum Spanning Trees · Single-Source and All-Pairs Shortest Paths

20. GATE CS 2025 Set 2MCQ2 marksMedium (estimate)

    GATE CS 2025 Set 2, Q.41

    An array $A$ of length $n$ with distinct elements is said to be bitonic if there is an index $1\le i\le n$ such that $A[\mathrm{1..}i]$ is sorted in the non-decreasing order and…

    Searching and Sorting Algorithms · Divide and Conquer

21. GATE CS 2025 Set 2NAT2 marksMedium (estimate)

    GATE CS 2025 Set 2, Q.59

    Consider the following algorithm someAlgo that takes an undirected graph $G$ as input. someAlgo(G) 1. Let v be any vertex in G. Run BFS on G starting at v. Let u be a vertex i...

    Graph Traversals, Topological Sort and Connectivity

22. GATE CS 2024 Set 1MCQ1 markEasy (estimate)

    GATE CS 2024 Set 1, Q.17

    Given an integer array of size $N$, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass t...

    Asymptotic Analysis and Time/Space Complexity · Searching and Sorting Algorithms

23. GATE CS 2024 Set 1MCQ2 marksMedium (estimate)

    GATE CS 2024 Set 1, Q.42

    Consider the following recurrence relation: $T(n)=\{\begin{array}{ll}\sqrt{n}T(\sqrt{n})+n& \text{for }n\ge 1,\\ 1& \text{for }n=1.\end{array}$ Which one of the follow...

    Asymptotic Analysis and Time/Space Complexity

24. GATE CS 2024 Set 1MSQ2 marksMedium (estimate)

    GATE CS 2024 Set 1, Q.45

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

    Graph Traversals, Topological Sort and Connectivity

25. GATE CS 2024 Set 1NAT2 marksEasy (estimate)

    GATE CS 2024 Set 1, Q.60

    The number of edges present in the forest generated by the DFS traversal of an undirected graph $G$ with 100 vertices is 40. The number of connected components in $G$ is _________

    Graph Traversals, Topological Sort and Connectivity

26. GATE CS 2024 Set 2MCQ1 markMedium (estimate)

    GATE CS 2024 Set 2, Q.15

    Let $T(n)$ be the recurrence relation defined as follows: $T(0)=1$, $T(1)=2$, and $T(n)=5T(n-1)-6T(n-2)$ for $n\ge 2$ Which one of the following statements is TRUE?

    Asymptotic Analysis and Time/Space Complexity · Combinatorics, Counting, Recurrence Relations and Generating Functions

27. GATE CS 2024 Set 2NAT1 markMedium (estimate)

    GATE CS 2024 Set 2, Q.35

    Let $A$ be an array containing integer values. The distance of $A$ is defined as the minimum number of elements in $A$ that must be replaced with another integer so that the res...

    Dynamic Programming

28. GATE CS 2024 Set 2MCQ2 marksMedium (estimate)

    GATE CS 2024 Set 2, Q.42

    Consider an array X that contains n positive integers. A subarray of X is defined to be a sequence of array locations with consecutive indices. The C code snippet given be...

    Dynamic Programming · Data Types, Operators and Control Flow

29. GATE CS 2024 Set 2NAT2 marksMedium (estimate)

    GATE CS 2024 Set 2, Q.59

    The number of distinct minimum-weight spanning trees of the following graph is _________ Undirected weighted graph with 7 vertices a, b, c, d, e, f, g and 12 edges: (a,b)=1, (a,...

    Minimum Spanning Trees · Graph Theory

30. GATE CS 2023MSQ1 markEasy (estimate)

    GATE CS 2023, Q.29

    Let $f$ and $g$ be functions of natural numbers given by $f(n)=n$ and $g(n)=n^2$. Which of the following statements is/are TRUE?

    Asymptotic Analysis and Time/Space Complexity

31. GATE CS 2023MSQ2 marksEasy (estimate)

    GATE CS 2023, Q.54

    Consider functions Function 1 and Function 2 expressed in pseudocode as follows: Function 1 Function 2 while n > 1 do for i = 1 to 100 * n do for i = 1 to n do x = x + 1; x...

    Asymptotic Analysis and Time/Space Complexity

32. GATE CS 2022MCQ1 markEasy (estimate)

    GATE CS 2022, Q.11

    Which one of the following statements is TRUE for all positive functions $f(n)$?

    Asymptotic Analysis and Time/Space Complexity

33. GATE CS 2022MSQ2 marksMedium (estimate)

    GATE CS 2022, Q.49

    Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?

    Minimum Spanning Trees

34. GATE CS 2021 Set 1MCQ1 markMedium (estimate)

    GATE CS 2021 Set 1, Q.12 (CS Q.2)

    Let $P$ be an array containing $n$ integers. Let $t$ be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum value...

    Searching and Sorting Algorithms

35. GATE CS 2021 Set 1MCQ1 markEasy (estimate)

    GATE CS 2021 Set 1, Q.13 (CS Q.3)

    Consider the following three functions. $f_1=10^n,f_2=n^{\log n},f_3=n^{\sqrt{n}}$ Which one of the following options arranges the functions in the increas...

    Asymptotic Analysis and Time/Space Complexity

36. GATE CS 2021 Set 1MCQ1 markEasy (estimate)

    GATE CS 2021 Set 1, Q.19 (CS Q.9)

    Consider the following array. 23 32 45 69 72 73 89 97 Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the ab...

    Searching and Sorting Algorithms

37. GATE CS 2021 Set 1NAT1 markMedium (estimate)

    GATE CS 2021 Set 1, Q.27 (CS Q.17)

    Consider the following undirected graph with edge weights as shown: A 3 by 3 grid graph with 9 vertices and labeled edge weights of 0.1 and 0.9. The number of minimum-weight spa...

    Minimum Spanning Trees

38. GATE CS 2021 Set 1MCQ2 marksMedium (estimate)

    GATE CS 2021 Set 1, Q.40 (CS Q.30)

    Consider the following recurrence relation. $T(n)=\{\begin{array}{ll}T(n/2)+T(2n/5)+7n& \text{if }n>0\\ 1& \text{if }n=0\end{array}$ Which one of the following opti...

    Asymptotic Analysis and Time/Space Complexity

39. GATE CS 2021 Set 1MSQ2 marksMedium (estimate)

    GATE CS 2021 Set 1, Q.50 (CS Q.40)

    Define $R_n$ to be the maximum amount earned by cutting a rod of length $n$ meters into one or more pieces of integer length and selling them. For $i>0$, let $p[i]$ denote the...

    Dynamic Programming

40. GATE CS 2021 Set 1MSQ2 marksMedium (estimate)

    GATE CS 2021 Set 1, Q.51 (CS Q.41)

    An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let $T$...

    Graph Traversals, Topological Sort and Connectivity

41. GATE CS 2021 Set 2MCQ1 markMedium (estimate)

    GATE CS 2021 Set 2, Q.11 (CS Q.1)

    Let $G$ be a connected undirected weighted graph. Consider the following two statements. $S_1$: There exists a minimum weight edge in $G$ which is present in every minimum spann...

    Minimum Spanning Trees

42. GATE CS 2021 Set 2MCQ1 markEasy (estimate)

    GATE CS 2021 Set 2, Q.18 (CS Q.8)

    What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$?

    Divide and Conquer

43. GATE CS 2021 Set 2MCQ2 marksMedium (estimate)

    GATE CS 2021 Set 2, Q.36 (CS Q.26)

    Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties: 1. For any two letters, the code assigned to one...

    Greedy Algorithms

44. GATE CS 2021 Set 2MCQ2 marksEasy (estimate)

    GATE CS 2021 Set 2, Q.49 (CS Q.39)

    For constants $a\ge 1$ and $b>1$, consider the following recurrence defined on the non-negative integers: $T(n)=a\cdot T\left(\frac{n}{b}\right)+f(n)$ Which one of the...

    Asymptotic Analysis and Time/Space Complexity

45. GATE CS 2021 Set 2MSQ2 marksMedium (estimate)

    GATE CS 2021 Set 2, Q.56 (CS Q.46)

    Consider the following directed graph: A 4 by 4 directed grid graph with 16 solid black vertices and directed edges between adjacent vertices. The bottom-left vertex is labeled...

    Graph Traversals, Topological Sort and Connectivity

46. GATE CS 2021 Set 2NAT2 marksMedium (estimate)

    GATE CS 2021 Set 2, Q.65 (CS Q.55)

    In a directed acyclic graph with a source vertex $s$, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a v...

    Dynamic Programming

47. GATE CS 2020MCQ1 markMedium (estimate)

    GATE CS 2020, Q.12 (CS Q.2)

    For parameters $a$ and $b$, both of which are $\omega (1)$, $T(n)=T(n^{1/a})+1$, and $T(b)=1$. Then $T(n)$ is

    Asymptotic Analysis and Time/Space Complexity

48. GATE CS 2020MCQ2 marksMedium (estimate)

    GATE CS 2020, Q.41 (CS Q.31)

    Let $G=(V,E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighted edge…

    Greedy Algorithms · Graph Traversals, Topological Sort and Connectivity

49. GATE CS 2020MCQ2 marksMedium (estimate)

    GATE CS 2020, Q.50 (CS Q.40)

    Let $G=(V,E)$ be a directed, weighted graph with weight function $w:E\to \mathbb{R}$. For some function $f:V\to \mathbb{R}$, for each edge $(u,v)\in E$, define…

    Graph Traversals, Topological Sort and Connectivity

50. GATE CS 2020NAT2 marksEasy (estimate)

    GATE CS 2020, Q.59 (CS Q.49)

    Consider a graph $G=(V,E)$, where $V=\{v_1,v_2,\dots ,v_{100}\}$, $E=\{(v_i,v_j)\mid 1\le i<j\le 100\}$, and weight of the edge $(v_i,v_j)$ is $|i-j|$. The wei...

    Greedy Algorithms · Graph Traversals, Topological Sort and Connectivity

51. GATE CS 2019NAT1 markMedium (estimate)

    GATE CS 2019, Q.30 (CS Q.20)

    An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed...

    Searching and Sorting Algorithms

52. GATE CS 2019NAT1 markEasy (estimate)

    GATE CS 2019, Q.35 (CS Q.25)

    Consider a sequence of 14 elements: $A=[-5,-10,6,3,-1,-2,13,4,-9,-1,4,12,-3,0]$. The subsequence sum $S(i,j)={\sum }_{k=i}^{j}A[k]$. Determine the maximum of…

    Divide and Conquer

53. GATE CS 2019MCQ2 marksMedium (estimate)

    GATE CS 2019, Q.47 (CS Q.37)

    There are $n$ unsorted arrays: $A_1,A_2,\dots ,A_n$. Assume that $n$ is odd. Each of $A_1,A_2,\dots ,A_n$ contains $n$ distinct elements. There are no common elements betwee...

    Divide and Conquer

54. GATE CS 2019MCQ2 marksMedium (estimate)

    GATE CS 2019, Q.48 (CS Q.38)

    Let $G$ be any connected, weighted, undirected graph. I. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. II. $G$ has a unique minimum spanni...

    Greedy Algorithms

55. GATE CS 2018MCQ2 marksMedium (estimate)

    GATE CS 2018, Q.40 (CS Q.30)

    Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. (I) No e...

    Graph Traversals, Topological Sort and Connectivity

56. GATE CS 2018MCQ2 marksMedium (estimate)

    GATE CS 2018, Q.41 (CS Q.31)

    Assume that multiplying a matrix $G_1$ of dimension $p\times q$ with another matrix $G_2$ of dimension $q\times r$ requires $pqr$ scalar multiplications. Computing the product...

    Dynamic Programming

57. GATE CS 2018NAT2 marksMedium (estimate)

    GATE CS 2018, Q.57 (CS Q.47)

    Consider the following undirected graph G: Undirected weighted graph G with 5 vertices and 7 edges, with edge weights 1, 3, 4, 4, 4, 5, and variable x. Choose a value for $x$ th...

    Greedy Algorithms

58. GATE CS 2018NAT2 marksMedium (estimate)

    GATE CS 2018, Q.58 (CS Q.48)

    Consider the weights and values of items listed below. Note that there is only one unit of each item. Item number Weight (in Kgs) Value (in Rupees) 1 10 60 2 7 28 3 4 20 4 2 24...

    Dynamic Programming

59. GATE CS 2017 Set 1MCQ1 markEasy (estimate)

    GATE CS 2017 Set 1, Q.4 (CS Q.4)

    Consider the following functions from positive integers to real numbers: $10,\sqrt{n},n,{\log }_{2}n,\frac{100}{n}$ The CORRECT arrangement of the abov...

    Asymptotic Analysis and Time/Space Complexity

60. GATE CS 2017 Set 1MCQ1 markEasy (estimate)

    GATE CS 2017 Set 1, Q.5 (CS Q.5)

    Consider the following table: Algorithm Design Paradigm (P) Kruskal (i) Divide and Conquer (Q) Quicksort (ii) Greedy (R) Floyd-Warshall (iii) Dynamic Programming Match the algor...

    Greedy Algorithms · Dynamic Programming · Divide and Conquer

61. GATE CS 2017 Set 1MCQ2 marksEasy (estimate)

    GATE CS 2017 Set 1, Q.26 (CS Q.26)

    Let $G=(V,E)$ be any connected undirected edge-weighted graph. The weights of the edges in $E$ are positive and distinct. Consider the following statements: (I) Minimum Spann...

    Greedy Algorithms · Graph Theory

62. GATE CS 2017 Set 1NAT2 marksMedium (estimate)

    GATE CS 2017 Set 1, Q.48 (CS Q.48)

    Let $A$ be an array of 31 numbers consisting of a sequence of 0's followed by a sequence of 1's. The problem is to find the smallest index $i$ such that $A[i]$ is 1 by probing t...

    Searching and Sorting Algorithms

63. GATE CS 2017 Set 2MCQ1 markEasy (estimate)

    GATE CS 2017 Set 2, Q.3 (CS Q.3)

    Match the algorithms with their time complexities: | Algorithm | Time complexity | | :--- | :--- | | (P) Towers of Hanoi with $n$ disks | (i) $\Theta (n^2)$ | | (Q) Binary search...

    Asymptotic Analysis and Time/Space Complexity · Searching and Sorting Algorithms

64. GATE CS 2017 Set 2MCQ1 markMedium (estimate)

    GATE CS 2017 Set 2, Q.15 (CS Q.15)

    The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph b...

    Graph Traversals, Topological Sort and Connectivity · Graph Representations and Disjoint Sets

65. GATE CS 2017 Set 2MCQ2 marksMedium (estimate)

    GATE CS 2017 Set 2, Q.30 (CS Q.30)

    Consider the recurrence function $T(n)=\{\begin{array}{ll}2T(\sqrt{n})+1,& n>2\\ 2,& 0<n\le 2\end{array}$ Then $T(n)$ in terms of $\Theta$ notation is

    Asymptotic Analysis and Time/Space Complexity

66. GATE CS 2017 Set 2MCQ2 marksMedium (estimate)

    GATE CS 2017 Set 2, Q.38 (CS Q.38)

    Consider the following C function. int fun(int n) { int i, j; for (i = 1; i <= n; i++) { for (j = 1; j < n; j += i) { printf("%d %d", i, j); } } } Time complexity of…

    Asymptotic Analysis and Time/Space Complexity

67. GATE CS 2017 Set 2NAT2 marksMedium (estimate)

    GATE CS 2017 Set 2, Q.50 (CS Q.50)

    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: | Character | Probability...

    Greedy Algorithms

68. GATE CS 2016 Set 1NAT1 markMedium (estimate)

    GATE CS 2016 Set 1, Q.21 (CS Q.11)

    Consider the following directed graph: Directed acyclic graph with six vertices labeled a, b, c, d, e, and f. Directed edges are from a to b, a to d, b to c, d to e, c to f, and...

    Graph Traversals, Topological Sort and Connectivity

69. GATE CS 2016 Set 1MCQ1 markEasy (estimate)

    GATE CS 2016 Set 1, Q.23 (CS Q.13)

    The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

    Searching and Sorting Algorithms

70. GATE CS 2016 Set 1MCQ1 markMedium (estimate)

    GATE CS 2016 Set 1, Q.24 (CS Q.14)

    Let $G$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements...

    Minimum Spanning Trees

71. GATE CS 2016 Set 1NAT2 marksMedium (estimate)

    GATE CS 2016 Set 1, Q.48 (CS Q.38)

    Consider the weighted undirected graph with 4 vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$…

    Single-Source and All-Pairs Shortest Paths

72. GATE CS 2016 Set 1NAT2 marksMedium (estimate)

    GATE CS 2016 Set 1, Q.49 (CS Q.39)

    Let $G$ be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of...

    Minimum Spanning Trees

73. GATE CS 2016 Set 1MCQ2 marksMedium (estimate)

    GATE CS 2016 Set 1, Q.50 (CS Q.40)

    $G=(V,E)$ is an undirected simple graph in which each edge has a distinct weight, and $e$ is a particular edge of $G$. Which of the following statements about the minimum spa...

    Minimum Spanning Trees

74. GATE CS 2016 Set 2NAT1 markMedium (estimate)

    GATE CS 2016 Set 2, Q.21 (CS Q.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$-th vertex in thi...

    Graph Traversals, Topological Sort and Connectivity

75. GATE CS 2016 Set 2MCQ1 markMedium (estimate)

    GATE CS 2016 Set 2, Q.23 (CS Q.13)

    Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE? I. Quicksort...

    Searching and Sorting Algorithms

76. GATE CS 2016 Set 2MCQ1 markEasy (estimate)

    GATE CS 2016 Set 2, Q.24 (CS Q.14)

    The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

    Dynamic Programming

77. GATE CS 2016 Set 2NAT2 marksMedium (estimate)

    GATE CS 2016 Set 2, Q.48 (CS Q.38)

    Let $A_1,A_2,A_3,$ and $A_4$ be four matrices of dimensions $10\times 5$, $5\times 20$, $20\times 10$, and $10\times 5$, respectively. The minimum number of scalar multipl...

    Dynamic Programming

78. GATE CS 2016 Set 2NAT2 marksHard (estimate)

    GATE CS 2016 Set 2, Q.49 (CS Q.39)

    The given diagram shows the flowchart for a recursive function $A(n)$. Assume that all statements, except for the recursive calls, have $O(1)$ time complexity. If the worst case...

    Asymptotic Analysis and Time/Space Complexity

79. GATE CS 2015 Set 1MCQ1 markEasy (estimate)

    GATE CS 2015 Set 1, Q.12 (CS Q.2)

    Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting $n$ ($n\ge 2$) numbers? In the recurrence equati...

    Asymptotic Analysis and Time/Space Complexity

80. GATE CS 2015 Set 1MCQ1 markEasy (estimate)

    GATE CS 2015 Set 1, Q.16 (CS Q.6)

    Match the following: | | Algorithm | | Design Paradigm | | :--- | :--- | :--- | :--- | | (P) | Prim's algorithm for minimum spanning tree | (i) | Backtracking | | (Q) | Floyd-Wa...

    Greedy Algorithms

81. GATE CS 2015 Set 1MCQ2 marksMedium (estimate)

    GATE CS 2015 Set 1, Q.41 (CS Q.31)

    Consider the following C function: int fun1(int n) { int i, j, k, p, q = 0; for (i = 1; i < n; ++i) { p = 0; for (j = n; j > 1; j = j / 2) ++p; for (k = 1; k < p; k = k * 2...

    Asymptotic Analysis and Time/Space Complexity

82. GATE CS 2015 Set 1NAT2 marksHard (estimate)

    GATE CS 2015 Set 1, Q.53 (CS Q.43)

    The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D...

    Minimum Spanning Trees

83. GATE CS 2015 Set 1MCQ2 marksMedium (estimate)

    GATE CS 2015 Set 1, Q.55 (CS Q.45)

    Let $G=(V,E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x\in V$, let $d(x)$ denote the shortest distance in $G$ from $s$ to...

    Graph Traversals, Topological Sort and Connectivity

84. GATE CS 2015 Set 2MCQ1 markMedium (estimate)

    GATE CS 2015 Set 2, Q.12 (CS Q.2)

    Consider two decision problems $Q_1,Q_2$ such that $Q_1$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_2$. Then which one of the following is c...

    Asymptotic Analysis and Time/Space Complexity

85. GATE CS 2015 Set 2MCQ1 markEasy (estimate)

    GATE CS 2015 Set 2, Q.32 (CS Q.22)

    An unordered list contains $n$ distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

    Searching and Sorting Algorithms

86. GATE CS 2015 Set 2MCQ2 marksEasy (estimate)

    GATE CS 2015 Set 2, Q.46 (CS Q.36)

    Given below are some algorithms, and some algorithm design paradigms. List-I 1. Dijkstra's Shortest Path 2. Floyd-Warshall algorithm to compute all pairs shortest path 3. Bi...

    Dynamic Programming

87. GATE CS 2015 Set 2MCQ2 marksMedium (estimate)

    GATE CS 2015 Set 2, Q.55 (CS Q.45)

    Suppose you are provided with the following function declaration in the C programming language: int partition(int a[], int n); The function treats the first element of a[] a...

    Searching and Sorting Algorithms

88. GATE CS 2015 Set 3MCQ1 markEasy (estimate)

    GATE CS 2015 Set 3, Q.14 (CS Q.4)

    Consider the equality ${\sum }_{i=0}^n{i}^3=X$ and the following choices for $X$…

    Asymptotic Analysis and Time/Space Complexity

89. GATE CS 2015 Set 3MCQ2 marksMedium (estimate)

    GATE CS 2015 Set 3, Q.37 (CS Q.27)

    Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a proble...

    Searching and Sorting Algorithms · Asymptotic Analysis and Time/Space Complexity

90. GATE CS 2015 Set 3NAT2 marksEasy (estimate)

    GATE CS 2015 Set 3, Q.50 (CS Q.40)

    Let $G$ be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of $G$ is 500. When the weight of each edge of $G$ is increased by f...

    Minimum Spanning Trees

91. GATE CS 2015 Set 3MCQ2 marksMedium (estimate)

    GATE CS 2015 Set 3, Q.52 (CS Q.42)

    Let $f(n)=n$ and $g(n)=n^{1+\sin n}$, where $n$ is a positive integer. Which of the following statements is/are correct? I. $f(n)=O(g(n))$ II. $f(n)=\Omega (g(n))$

    Asymptotic Analysis and Time/Space Complexity

92. GATE CS 2015 Set 3MCQ2 marksMedium (estimate)

    GATE CS 2015 Set 3, Q.63 (CS Q.53)

    Language $L_1$ is polynomial time reducible to language $L_2$. Language $L_2$ is polynomial time reducible to $L_3$, which in turn is polynomial time reducible to language $L_4$...

    Asymptotic Analysis and Time/Space Complexity

93. GATE CS 2014 Set 1MCQ1 markEasy (estimate)

    GATE CS 2014 Set 1, Q.13 (CS Q.3)

    Let $G=(V,E)$ be a directed graph where $V$ is the set of vertices and $E$ the set of edges. Then which one of the following graphs has the same strongly connected components as...

    Graph Traversals, Topological Sort and Connectivity

94. GATE CS 2014 Set 1MCQ1 markEasy (estimate)

    GATE CS 2014 Set 1, Q.21 (CS Q.11)

    Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjacency ma...

    Graph Traversals, Topological Sort and Connectivity

95. GATE CS 2014 Set 1MCQ1 markEasy (estimate)

    GATE CS 2014 Set 1, Q.23 (CS Q.13)

    Consider the directed graph given below. Directed graph on four vertices P, Q, R, and S Which one of the following is TRUE?

    Graph Traversals, Topological Sort and Connectivity

96. GATE CS 2014 Set 1MCQ1 markMedium (estimate)

    GATE CS 2014 Set 1, Q.24 (CS Q.14)

    Let $P$ be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let $t_1$ and $t_2$ be the number of comparisons made by $P$ for the inpu...

    Searching and Sorting Algorithms

97. GATE CS 2014 Set 1NAT2 marksMedium (estimate)

    GATE CS 2014 Set 1, Q.49 (CS Q.39)

    The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.

    Searching and Sorting Algorithms

98. GATE CS 2014 Set 1MCQ2 marksMedium (estimate)

    GATE CS 2014 Set 1, Q.52 (CS Q.42)

    Consider the following pseudo code. What is the total number of multiplications to be performed? D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D *...

    Asymptotic Analysis and Time/Space Complexity

99. GATE CS 2014 Set 2MCQ1 markEasy (estimate)

    GATE CS 2014 Set 2, Q.23 (CS Q.13)

    Which one of the following correctly determines the solution of the recurrence relation with $T(1)=1$? $T(n)=2T\left(\frac{n}{2}\right)+\log n$

    Asymptotic Analysis and Time/Space Complexity

100. GATE CS 2014 Set 2MCQ1 markEasy (estimate)

     GATE CS 2014 Set 2, Q.24 (CS Q.14)

     Consider the tree arcs of a BFS traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for comp...

     Graph Traversals, Topological Sort and Connectivity

101. GATE CS 2014 Set 2NAT2 marksMedium (estimate)

     GATE CS 2014 Set 2, Q.47 (CS Q.37)

     Consider two strings $A=\text{"qpqrr"}$ and $B=\text{"pqprqrp"}$. Let $x$ be the length of the longest common subsequence (not necessarily contiguous) between $A$ and $B$ an...

     Dynamic Programming

102. GATE CS 2014 Set 2NAT2 marksMedium (estimate)

     GATE CS 2014 Set 2, Q.48 (CS Q.38)

     Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a ti...

     Greedy Algorithms

103. GATE CS 2014 Set 2NAT2 marksMedium (estimate)

     GATE CS 2014 Set 2, Q.62 (CS Q.52)

     The number of distinct minimum spanning trees for the weighted graph below is _____. Weighted undirected planar graph with edge weights 1 and 2 for MST enumeration Weighted grap...

     Minimum Spanning Trees

104. GATE CS 2014 Set 3NAT1 markMedium (estimate)

     GATE CS 2014 Set 3, Q.21 (CS Q.11)

     The minimum number of arithmetic operations required to evaluate the polynomial $P(X)=X^5+4X^3+6X+5$ for a given value of $X$, using only one temporary variable is _____.

     Asymptotic Analysis and Time/Space Complexity

105. GATE CS 2014 Set 3NAT1 markHard (estimate)

     GATE CS 2014 Set 3, Q.23 (CS Q.13)

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

     Graph Traversals, Topological Sort and Connectivity

106. GATE CS 2014 Set 3MCQ1 markEasy (estimate)

     GATE CS 2014 Set 3, Q.24 (CS Q.14)

     You have an array of $n$ 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...

     Searching and Sorting Algorithms

107. GATE CS 2014 Set 3NAT2 marksEasy (estimate)

     GATE CS 2014 Set 3, Q.47 (CS Q.37)

     Suppose you want to move from 0 to 100 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...

     Dynamic Programming

108. GATE CS 2014 Set 3MCQ2 marksEasy (estimate)

     GATE CS 2014 Set 3, Q.48 (CS Q.38)

     Consider the decision problem 2CNFSAT defined as follows: $\{\Phi \mid \Phi \text{ is a satisfiable propositional formula in CNF with at most two literals per clause}\}$ For e...

     Asymptotic Analysis and Time/Space Complexity

109. GATE CS 2014 Set 3MCQ2 marksMedium (estimate)

     GATE CS 2014 Set 3, Q.52 (CS Q.42)

     Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j...

     Searching and Sorting Algorithms

110. GATE CS 2013MCQ1 markEasy (estimate)

     GATE CS 2013, Q.6 (CS Q.6)

     Which one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort?

     Searching and Sorting Algorithms

111. GATE CS 2013MCQ1 markEasy (estimate)

     GATE CS 2013, Q.19 (CS Q.19)

     What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of $n$ vertices?

     Single-Source and All-Pairs Shortest Paths

112. GATE CS 2013MCQ2 marksMedium (estimate)

     GATE CS 2013, Q.30 (CS Q.30)

     The number of elements that can be sorted in $\Theta (\log n)$ time using heap sort is

     Searching and Sorting Algorithms

113. GATE CS 2012MCQ1 markEasy (estimate)

     GATE CS 2012, Q.4 (CS Q.4)

     Assuming $\text{P}\ne \text{NP}$, which of the following is TRUE?

     Asymptotic Analysis and Time/Space Complexity

114. GATE CS 2012MCQ1 markEasy (estimate)

     GATE CS 2012, Q.16 (CS Q.16)

     The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with $n$ discs is

     Divide and Conquer · Asymptotic Analysis and Time/Space Complexity

115. GATE CS 2012MCQ1 markEasy (estimate)

     GATE CS 2012, Q.18 (CS Q.18)

     Let $W(n)$ and $A(n)$ denote respectively, the worst case and average case running time of an algorithm executed on an input of size $n$. Which of the following is ALWAYS TRUE?

     Asymptotic Analysis and Time/Space Complexity

116. GATE CS 2012MCQ2 marksMedium (estimate)

     GATE CS 2012, Q.29 (CS Q.29)

     Let $G$ be a weighted graph with edge weights greater than one and $G^{\prime }$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T^{\prime }$ be the minimum spannin...

     Greedy Algorithms · Graph Traversals, Topological Sort and Connectivity

117. GATE CS 2012MCQ2 marksMedium (estimate)

     GATE CS 2012, Q.39 (CS Q.39)

     A list of $n$ strings, each of length $n$, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

     Searching and Sorting Algorithms · Asymptotic Analysis and Time/Space Complexity

118. GATE CS 2012MCQ2 marksMedium (estimate)

     GATE CS 2012, Q.40 (CS Q.40)

     Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra's shortest path algorit...

     Single-Source and All-Pairs Shortest Paths · Greedy Algorithms

119. GATE CS 2011MCQ1 markMedium (estimate)Not in current syllabus

     GATE CS 2011, Q.5 (CS Q.5)

     A company needs to develop a strategy for software product development for which it has a choice of two programming languages L1 and L2. The number of lines of code (LOC) develo...

     Asymptotic Analysis and Time/Space Complexity

120. GATE CS 2011MCQ1 markMedium (estimate)

     GATE CS 2011, Q.7 (CS Q.7)

     A company needs to develop digital signal processing software for one of its newest inventions. The software is expected to have 40000 lines of code. The company needs to determ...

     Asymptotic Analysis and Time/Space Complexity

121. GATE CS 2011MCQ1 markEasy (estimate)

     GATE CS 2011, Q.25 (CS Q.25)

     An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array $A[0:n-1]$ is given below. Let $L_i$ denote the length of the longest mon...

     Dynamic Programming

122. GATE CS 2011MCQ2 marksMedium (estimate)

     GATE CS 2011, Q.37 (CS Q.37)

     Which of the given options provides the increasing order of asymptotic complexity of functions $f_1,f_2,f_3$ and $f_4$?…

     Asymptotic Analysis and Time/Space Complexity

123. GATE CS 2011MCQ2 marksMedium (estimate)

     GATE CS 2011, Q.38 (CS Q.38)

     Four matrices $M_1,M_2,M_3$ and $M_4$ of dimensions $p\times q$, $q\times r$, $r\times s$ and $s\times t$ respectively can be multiplied in several ways with different num...

     Dynamic Programming

124. GATE CS 2011MCQ2 marksMedium (estimate)

     GATE CS 2011, Q.54 (CS Q.54)

     What will be the cost of the minimum spanning tree (MST) of such a graph with $n$ nodes?

     Minimum Spanning Trees

125. GATE CS 2011MCQ2 marksMedium (estimate)

     GATE CS 2011, Q.55 (CS Q.55)

     The length of the path from $v_5$ to $v_6$ in the MST of previous question with $n=10$ is

     Minimum Spanning Trees