Practice Test Geeks(GATE) Graduate Aptitude Test in Engineering Practice Test
← All GATE Flashcard Decks

Algorithms and Data Structures Flashcards

7 cards from real GATE practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.

Read the first 7 Algorithms and Data Structures flashcards as text

  1. What is the time complexity of the Floyd-Warshall algorithm for computing all-pairs shortest paths in a graph with V vertices?

    Answer: O(V³)

    Floyd-Warshall uses three nested loops—one for each possible intermediate vertex and one for each pair of source/destination vertices—resulting in O(V³) time.

  2. The 0/1 Knapsack problem with n items and capacity W, solved using dynamic programming, has time complexity:

    Answer: O(n × W)

    The DP table has n rows and W+1 columns, and each of the n×W cells is filled in O(1) time, giving O(n × W) total.

  3. Dijkstra's single-source shortest path algorithm produces incorrect results when the graph contains:

    Answer: Negative weight edges

    Dijkstra's greedy strategy assumes that once a node's distance is finalized it cannot improve, which breaks when negative edges allow a longer path to have a shorter total weight.

  4. What is the time complexity of Prim's Minimum Spanning Tree algorithm when implemented with a binary min-heap?

    Answer: O(E log V)

    Each of the E edges triggers at most one decrease-key operation costing O(log V), and extracting V vertices costs O(V log V), giving O(E log V) overall.

  5. Which of the following is a capability of the Bellman-Ford shortest path algorithm that Dijkstra's algorithm lacks?

    Answer: Detects negative weight cycles

    Bellman-Ford performs V−1 relaxation passes; if a V-th pass still reduces some distance, a negative weight cycle is detected.

  6. What is the recurrence relation that correctly describes the number of comparisons C(n) in Merge Sort?

    Answer: C(n) = 2C(n/2) + n

    Merge Sort splits into two subproblems of size n/2 (cost 2C(n/2)) and then merges the two halves in O(n) comparisons, giving C(n) = 2C(n/2) + n.

  7. Which algorithmic paradigm is used to efficiently solve the Longest Common Subsequence (LCS) problem?

    Answer: Dynamic Programming

    LCS exhibits optimal substructure and overlapping subproblems, so dynamic programming fills a 2D table in O(m×n) time rather than recomputing subproblems recursively.