Start learning →

GATE CSE Algorithms — practice questions — page 2

Explore 60 free Algorithms questions in GATE CSE Computer Science. Open each question or exercise to read its content, reference answers and available explanation.

Practise Algorithms with Quill →

Algorithms questions and exercises with answers

Showing questions 31–60 of 60.

Per the lecture's guidance, choose Kruskal over Prim whenRead the answer and worked solution →Per the standard DP solution for LCS of two strings of length m and n, the running time isRead the answer and worked solution →If only the LCS LENGTH is needed (not the actual subsequence string), the DP table can be stored inRead the answer and worked solution →The 0/1 knapsack recurrence (max value using first i items, capacity c) isRead the answer and worked solution →The standard DP solution for matrix-chain multiplication runs inRead the answer and worked solution →The number of distinct parenthesisations of n matrices isRead the answer and worked solution →BFS finds the shortest path from a source in an unweighted graph becauseRead the answer and worked solution →On a sparse graph (E far less than V²), the adjacency list representationRead the answer and worked solution →Choose BFS over DFS whenRead the answer and worked solution →Dijkstra's algorithm requires thatRead the answer and worked solution →Dijkstra's algorithm using a binary min-heap runs inRead the answer and worked solution →The running time and space of Floyd-Warshall on a graph with V vertices and E edges isRead the answer and worked solution →Topological sort is well-defined forRead the answer and worked solution →Which set inclusion is established (i.e., proven, not open)?Read the answer and worked solution →The first problem proved to be NP-complete wasRead the answer and worked solution →An NP-hard problem differs from an NP-complete one because NP-hard problemsRead the answer and worked solution →Which sorting methodRead the answer and worked solution →Linear or binary searchRead the answer and worked solution →Order the binary searchRead the answer and worked solution →Type the algorithm termRead the answer and worked solution →Count the passesRead the answer and worked solution →Pop the sorting methodsRead the answer and worked solution →One word is wrongRead the answer and worked solution →Selection or insertionRead the answer and worked solution →Which one does not belongRead the answer and worked solution →Does it need sorting firstRead the answer and worked solution →Spot the false statementRead the answer and worked solution →Which ones belongRead the answer and worked solution →Knock out the true statementsRead the answer and worked solution →Sorting and searching bingoRead the answer and worked solution →

Worked practice questions

Per the lecture's guidance, choose Kruskal over Prim when

  1. the graph has negative edge weights
  2. the source vertex is fixed in advance
  3. you need shortest paths from a single source
  4. the graph is sparse and the edge list is natural
Show answer and solution

Correct answer: D. the graph is sparse and the edge list is natural

On sparse graphs Kruskal's O(E log V) wins because sorting a small edge list is cheap. On dense graphs (E close to V²) Prim with a Fibonacci heap gives O(V²), beating Kruskal's O(V² log V). Negative weights and source vertices are irrelevant for MST shortest-path-from-source is Dijkstra, a different algorithm.

Open this question →

Per the standard DP solution for LCS of two strings of length m and n, the running time is

  1. O(m + n) using two pointers
  2. O(m log n) with a sorted table
  3. O(2^(m+n)) since both characters must be tried
  4. O(mn) by filling an m × n DP table
Show answer and solution

Correct answer: D. O(mn) by filling an m × n DP table

Each cell of the m × n DP table is computed in O(1) by checking three neighbours and applying the recurrence. Total: O(mn). The two-pointer O(m+n) approach gives merge-style scanning but not LCS. The 2^(m+n) figure is the naive recursion before memoisation DP collapses it to polynomial.

Open this question →

If only the LCS LENGTH is needed (not the actual subsequence string), the DP table can be stored in

  1. O(min(m, n)) space using two rolling rows
  2. O(mn²) space because of duplicate paths
  3. O(1) space because length is just an integer
  4. O(m + n) space using a stack of indices
Show answer and solution

Correct answer: A. O(min(m, n)) space using two rolling rows

Each cell depends only on the row above and the cell to the left in the current row. So keep two rolling rows the older one can be discarded once it's been used to compute the newer. O(min(m, n)) space if you orient rows along the shorter string. You can't get O(1) because you do need the current and previous row reconstructing the actual LCS does need the full table.

Open this question →

How to practise

  1. Choose a Algorithms question and try to work out your answer.
  2. Open the question to check the correct answer and read its worked solution.
  3. Continue in the app for bite-sized lessons, explanations and review with Quill. You can start without creating an account.

More Computer Science topics

Database Management SystemsCompiler DesignOperating SystemsComputer NetworksTheory of ComputationDiscrete Mathematics