Algorithms GATE PYQ Solutions
| Q1➡ | GATE CSE 2021 Set-1 Consider the following three Functions  Which one of the following options arranges the functions in the increasing order of asymptotic growth rate? |
| i ➥ f2, f1, f3 |
| ii ➥ f3, f2, f1 |
| iii ➥ f2, f3, f1 |
| iv ➥ f1, f2, f3 |
Show Answer With Best Explanation
Answer: III
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Asymptotic Complexity | Help-Line |
| Q2➡ | GATE CSE 2021 Set-1 Consider the following array:  Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order? |
| i ➥ Quicksort using the last element as pivot |
| ii ➥ Selection sort |
| iii ➥ Mergesort |
| iv ➥ Insertion sort |
Show Answer With Best Explanation
Answer: IV
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Time Complexity | Help-Line |
| Q3➡ | GATE CSE 2021 Set-1 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 values in an arbitrary array of n elements. Which one of the following choices is correct? |
i ➥  |
ii ➥  |
iii ➥  |
iv ➥  |
Show Answer With Best Explanation
Answer: III
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Time Complexity | Help-Line |
| Q4➡ | GATE CSE 2021 Set-1 Consider the following undirected graph with edge weights as shown:  The number of minimum-weight spanning trees of the graph is ______ |
Show Answer With Best Explanation
Answer: 3
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Minimum Spanning Tree | Help-Line |
| Q5➡ | GATE CSE 2021 Set-1 Consider the following recurrence relation.  Which one of the following options is correct? |
i ➥  |
ii ➥  |
iii ➥  |
iv ➥  |
Show Answer With Best Explanation
Answer: III
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Time Complexity | Help-Line |
| Q6➡ | GATE CSE 2021 Set-1 Define Rn to be the maximum amount earned by cutting a rod of length n metres into one or more pieces of integer length and selling them. For i > 0, let p[i] denote the selling price of a rod whose length is i meters. Consider the array of prices: p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18 Which of the following statements is/are correct about R7? |
| i ➥ R7 cannot be achieved by a solution consisting of three pieces. |
| ii ➥ R7 is achieved by three different solutions. |
| iii ➥ R7=19 |
| iv ➥ R7=18 |
Show Answer With Best Explanation
Answer: II, IV
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Dynamic Programming | Help-Line |
| Q7➡ | GATE CSE 2021 Set-2 What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n? |
i ➥  |
ii ➥  |
iii ➥  |
iv ➥  |
Show Answer With Best Explanation
Answer: III
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Time Complexity | Help-Line |
| Q8➡ | GATE CSE 2021 Set-2 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 letter must not be a prefix of the code assigned to the other letter. 2. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter. Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string? |
| i ➥ 25 |
| ii ➥ 21 |
| iii ➥ 30 |
| iv ➥ 23 |
Show Answer With Best Explanation
Answer: IV
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Hamming code | Help-Line |
| Q9➡ | GATE CSE 2021 Set-2 For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers:  Which one of the following options is correct about the recurrence T(n)? |
i ➥  |
ii ➥  |
iii ➥  |
iv ➥  |
Show Answer With Best Explanation
Answer: I
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Master Theorem | Help-Line |
| Q10➡ | GATE CSE 2020 For parameters a and b, both of which are ω(1), T(n) = T(n1/a)+1, and T(b)=1. Then T(n) is |
| i ➥ θ(logab n) |
| ii ➥ θ(logb loga n) |
| iii ➥ θ(loga logb n) |
| iv ➥ θ(log2 log2 n) |
Show Answer With Best Explanation
Answer: III
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Recurrences | Help-Line |
| Q11➡ | GATE CSE 2020 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 (u,v) ∈ V×V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is |
| i ➥ θ(|E||V|) |
| ii ➥ θ(|E|+|V|) |
| iii ➥ θ(|V|) |
| iv ➥ θ(|E| log|V|) |
Show Answer With Best Explanation
Answer: III
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Minimum Spanning Tree | Help-Line |
| Q12➡ | GATE CSE 2020 Consider a graph G = (V, E), where V = {v1, v2, …, v100}, E = {(vi, vj) | 1 ≤ i < j ≤ 100}, and weight of the edge (vi, vj) is |i – j|. The weight of the minimum spanning tree of G is _______. |
Show Answer With Best Explanation
Answer: 99
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Minimum Spanning Tree | Help-Line |
| Q13➡ | GATE CSE 2019 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 in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is ________. |
Show Answer With Best Explanation
Answer: 0.08
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Sorting | Help-Line |
| Q14➡ | GATE CSE 2019 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)=  Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)___________. |
Show Answer With Best Explanation
Answer: 29
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Dynamic Programming | Help-Line |
| Q15➡ | GATE CSE 2019 There are n unsorted arrays: A1, A2, …, An. Assume that n is odd. Each of A1, A2, …, An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A1, A2, …, An is |
| i ➥ O(n2) |
| ii ➥ Ω(n2 log n) |
| iii ➥ O(n) |
| iv ➥ O(n log n) |
Show Answer With Best Explanation
Answer: I
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Sorting | Help-Line |
| Q16➡ | GATE CSE 2018 Consider the weights and values of items listed below. Note that there is only one unit of each item.  The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by Vopt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by Vgreedy. The value of Vopt − Vgreedy is __ . |
Show Answer With Best Explanation
Answer: 16
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | 0/1-Knapsack | Help-Line |
| Q17➡ | GATE CSE 2018 Consider the following undirected graph G:  Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is _________. |
Show Answer With Best Explanation
Answer: 4
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Minimum-Spanning-Tree | Help-Line |
| Q18➡ | GATE CSE 2017 Set-1 Consider the following table:  Match the algorithm to design paradigms they are based on: |
| i ➥ (P)↔(ii), Q↔(i), (R)↔(iii) |
| ii ➥ (P)↔(ii), Q↔(iii), (R)↔(i) |
| iii ➥ (P)↔(i), Q↔(ii), (R)↔(iii) |
| iv ➥ (P)↔(iii), Q↔(i), (R)↔(ii) |
Show Answer With Best Explanation
Answer: I
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Design paradigms | Help-Line |
| Q19➡ | GATE CSE 2017 Set-1 Consider the following functions from positives integers to real numbers  The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is: |
i ➥  |
ii ➥  |
iii ➥  |
iv ➥  |
Show Answer With Best Explanation
Answer: II
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Asymptotic Complexity | Help-Line |
| Q20➡ | GATE CSE 2017 Set-1 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 Spanning Tree of G is always unique. (II) Shortest path between any two vertices of G is always unique. Which of the above statements is/are necessarily true? |
| i ➥ (II) only |
| ii ➥ (I) only |
| iii ➥ neither (I) nor (II) |
| iv ➥ both (I) and (II) |
Show Answer With Best Explanation
Answer: II
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Minimum Spanning Tree | Help-Line |
| Q21➡ | GATE CSE 2017 Set-1 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 the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is ___________. |
Show Answer With Best Explanation
Answer: 5
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Searching | Help-Line |
| Q22➡ | GATE CSE 2017 Set-2 Match the algorithms with their time complexities:  |
| i ➥ P→(iv), Q→(iii), R→(i), S→(ii) |
| ii ➥ P→(iv), Q→(iii), R→(ii), S→(i) |
| iii ➥ P→(iii), Q→(iv), R→(ii), S→(i) |
| iv ➥ P→(iii), Q→(iv), R→(i), S→(ii) |
Show Answer With Best Explanation
Answer: III
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Time Complexity | Help-Line |
| Q23➡ | GATE CSE 2017 Set-2 Consider the recurrence function  Then T(n) in terms of Θ notation is |
| i ➥ Θ(n) |
| ii ➥ Θ(√n) |
| iii ➥ Θ(logn) |
| iv ➥ Θ(loglogn) |
Show Answer With Best Explanation
Answer: III
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Time Complexity | Help-Line |
| Q24➡ | GATE CSE 2017 Set-2 Consider the following C function.  Time complexity of fun in terms of Θ notation is |
| i ➥ Θ(n2 logn) |
| ii ➥ Θ(n logn) |
| iii ➥ Θ(n2) |
| iv ➥ Θ(n√n) |
Show Answer With Best Explanation
Answer: II
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Time Complexity | Help-Line |
| Q25➡ | GATE CSE 2017 Set-2 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:  If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is _______. |
Show Answer With Best Explanation
Answer: 225
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Huffman Coding | Help-Line |
| Q26➡ | GATE CSE 2016 Set-1 The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are: |
| i ➥ Θ(nlogn), Θ(nlogn), and Θ(n2) |
| ii ➥ Θ(n2 ), Θ(n2 ), and Θ(nlogn) |
| iii ➥ Θ(n2), Θ(nlogn), and Θ(nlogn) |
| iv ➥ Θ(n2), Θ(nlogn), and Θ(n2) |
Show Answer With Best Explanation
Answer: IV
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Sorting | Help-Line |
| Q27➡ | GATE CSE 2016 Set-1 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 G can have is _______. |
Show Answer With Best Explanation
Answer: 7
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Minimum Spanning Tree | Help-Line |
| Q28➡ | GATE CSE 2016 Set-1 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 spanning trees (MSTs) of G is/are TRUE? • I. If e is the lightest edge of some cycle in G , then every MST of G includes e • II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e |
| i ➥ neither I nor II |
| ii ➥ both I and II |
| iii ➥ II only |
| iv ➥ I only |
Show Answer With Best Explanation
Answer: III
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Minimum Spanning Tree | Help-Line |
| Q29➡ | GATE CSE 2016 Set-2 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 runs in Θ(n2) time II. Bubblesort runs in Θ(n2) time III. Mergesort runs in Θ(n) time IV. Insertion sort runs in Θ(n) time |
| i ➥ I and II only |
| ii ➥ I and III only |
| iii ➥ II and IV only |
| iv ➥ I and IV only |
Show Answer With Best Explanation
Answer: IV
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Sorting | Help-Line |
| Q30➡ | GATE CSE 2016 Set-2 The Floyd-Warshall algorithm for all-pair shortest paths computation is based on |
| i ➥ Greedy paradigm. |
| ii ➥ Divide-and-Conquer paradigm. |
| iii ➥ Dynamic Programming paradigm. |
| iv ➥ Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm. |
Show Answer With Best Explanation
Answer: III
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Floyd Warshall Algorithm | Help-Line |
| Q31➡ | GATE CSE 2016 Set-2 Let A1, A2, A3 and A4 be four matrices of dimensions 10 × 5, 5 × 20, 20 × 10, and 10 × 5, respectively. |
Show Answer With Best Explanation
Answer: 1500
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Matrix Chain Multiplication | Help-Line |
| Q32➡ | GATE CSE 2016 Set-2 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 time complexity of this function is O(nα), then the least possible value (accurate upto two decimal positions) of α is ______. |
Show Answer With Best Explanation
Answer: 2.2 to 2.4
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Time Complexity | Help-Line |
Q33➡ | GATE CSE 2015 Set-1  |
| i ➥ P-iii, Q-ii, R-iv, S-i |
| ii ➥ P-i, Q-ii, R-iv, S-iii |
| iii ➥ P-ii, Q-iii, R-iv, S-i |
| iv ➥ P-ii, Q-i, R-iii, S-iv |
Show Answer With Best Explanation
Answer: III
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Matching | Help-Line |
| Q34➡ | GATE CSE 2015 Set-1 Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(≥ 2) numbers? In the recurrence equations given in the options below, c is a constant. |
| i ➥ T(n) = 2T(n/2) + cn |
| ii ➥ T(n) = T(n – 1) + T(1) + cn |
| iii ➥ T(n) = 2T(n – 1) + cn |
| iv ➥ T(n) = T(n/2) + cn |
Show Answer With Best Explanation
Answer: II
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Quick Sort | Help-Line |
| Q35➡ | GATE CSE 2015 Set-1 An algorithm performs (log N)1/2 find operations, N insert operations, (log N)1/2 delete operations, and (log N)1/2 decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations? |
| i ➥ Unsorted array |
| ii ➥ Min-heap |
| iii ➥ Sorted array |
| iv ➥ Sorted doubly linked list |
Show Answer With Best Explanation
Answer: I
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Time Complexity | Help-Line |
| Q36➡ | GATE CSE 2015 Set-1 The graph shown below 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, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is _______.  |
Show Answer With Best Explanation
Answer: 69
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Minimum Spanning Tree | Help-Line |
| Q37➡ | GATE CSE 2015 Set-2 Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3 -SAT reduces in polynomial time to Q2. Then which one of following is consistent with the above statement? |
| i ➥ Q1 is in NP, Q2 in NP hard |
| ii ➥ Q1 is in NP, Q2 is NP hard |
| iii ➥ Both Q1 and Q2 are in NP |
| iv ➥ Both Q1 and Q2 are NP hard |
Show Answer With Best Explanation
Answer: I
Explanation: Upload Soon
| More Discussion | Explanation On YouTube | Complexity | Help-Line |
| Q38➡ | |