How is dynamic programming tested in GATE CS Algorithm questions?

GATE tests classic DP problems including longest common subsequence, 0/1 knapsack, matrix chain multiplication, and optimal BST. Questions focus on recurrence formulation, optimal substructure, and overlapping subproblems.

What greedy algorithm problems appear in GATE CS exam?

GATE tests greedy problems such as activity selection, fractional knapsack, Huffman encoding, Prim's and Kruskal's MST, and Dijkstra's shortest path. The key focus is proving greedy choice property and optimal substructure.

How is the Master Theorem applied in GATE recurrence questions?

The Master Theorem solves recurrences of the form T(n) = aT(n/b) + f(n). GATE tests all three cases of the theorem along with the Akra-Bazzi method and substitution method for recurrences that do not fit the standard form.

What is the divide and conquer paradigm in GATE Algorithm Design?

Divide and conquer breaks a problem into subproblems, solves them recursively, and combines results. GATE tests merge sort, quick sort, binary search, and Strassen's matrix multiplication with focus on recurrence and time complexity.

CS/IT Gate Subject

Aptitude and Reasoning
Engineering Mathematics
C Programming
Data Structure
Design Algorithm Analysis
Operating System
Computer Network
Digital Logic Design
Compiler Design
Database Management System
Theory of Computation

Design Algorithm Analysis GATE previous year questions with answer

Ques 14 Gate 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 ∑^j_k=iA[k]. Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)

(a) is the correct answer.

Ques 15 Gate 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 _________.

(a) is the correct answer.

Ques 16 Gate 2019

There are n unsorted arrays: A₁, A₂, ....,A_n. Assume that n is odd. Each of A₁, A₂, ...., A_n 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 A₁ ,A₂, ....,A_n is ________ .

Ο(n)

Ο(n²)

Ο(n log n)

Ω(n²log n)

(b) is the correct answer.

Ques 17 Gate 2017 Set-1

Consider the following table

Algorithms	Design Paradigms
(P) Kruskal	(i) Divide and Conquer
(Q) Quicksort	(ii) Greedy
(R) Floyed Warshall	(iii) Dynamic Programming

Match the algorithm to design paradigms they are based on:

P-(ii), Q-(iii), R-(i)

P-(iii), Q-(i), R-(ii)

P-(ii), Q-(i), R-(iii)

P-(i), Q-(ii), R-(iii)

(Algorithms) is the correct answer.

Ques 18 Gate 2017 Set-1

Consider the following functions from positives integers to real numbers

10, √n, n, log₂n, 100/n.

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

log₂n, 100/n,10, √n, n,

100/n,10,log₂n, √n, n,

10,100/n, √n,log₂n,n

100/n,log₂n, 10,√n, n,

(Complexity) is the correct answer.

Ques 19 Gate 2017 Set-1

Consider the following intermediate program in three address code

p = a - b
q = p * c
p = u * v
q = p+q

Which one of the following corresponds to a static single assignment from the above code?

p₁ = a - b
q₁ =p₁ * c
p₁= u * v
q₁ =p₁ + q₁

p₃= a - b
q₄= p₃* c
p₄= u * v
q₅ =p₄+ q₄

p₁ = a - b
q₁=p₂ * c
p₃= u * v
q₂= p₄ + q₃

p₁ = a - b
q₁= p * c
p₂= u * v
q₂= p + q

(Addressing Mode) is the correct answer.

Ques 20 Gate 2016 Set-2

Let A₁, A₂, A₃, and A₄ be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5, respectively. The minimum number of scalar multiplications required to find the product A₁ A₂A₃A₄ using the basic matrix multiplication method is______________.

(a) is the correct answer.

Ques 21 Gate 2016 Set-2

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 this BFS traversal, then the maximum possible value of n is ________

(a) is the correct answer.

Ques 22 Gate 2016 Set-2

N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed.

An algorithm performs the following operations on the list in this order: Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key What is the time complexity of all these operations put together

O(Log²N)

O(N)

O(N²)

Θ(N² Log N)

(S) is the correct answer.

Given:
A sorted doubly linked list containing N items.
Pointers are provided directly to the nodes for delete and decrease-key operations.
Sequence of operations:
- Θ(N) delete operations
- O(log N) insert operations
- O(log N) find operations
- Θ(N) decrease-key operations
To find:
The overall time complexity of all these operations put together.
Solution:
Let me analyze the time taken by each operation on a sorted doubly linked list one by one.
First, for the delete operation:
Since a direct pointer to the record to be deleted is given, we just need to update the prev and next pointers of the adjacent nodes.
Time taken for 1 delete = O(1).
Total time for Θ(N) delete operations = Θ(N) × O(1) = O(N).
Next, for the insert operation:
Since it is a linked list, we do not have random access, so we cannot do binary search. We have to scan linearly to find the correct sorted position.
Time taken for 1 insert = O(N).
Total time for O(log N) insert operations = O(log N) × O(N) = O(N log N).
Next, for the find operation:
Again, no random access, so linear search is required to find an element.
Time taken for 1 find = O(N).
Total time for O(log N) find operations = O(log N) × O(N) = O(N log N).
Now, for the decrease-key operation:
A pointer to the record is provided, but decreasing the key value means the node may no longer be in sorted order.
To restore the sorted order, we have to shift the node backwards along the list to its appropriate position.
In the worst case, shifting takes O(N) steps.
Time taken for 1 decrease-key = O(N).
Total time for Θ(N) decrease-key operations = Θ(N) × O(N) = O(N²).
Now adding up the time complexities of all operations:
Total Time = O(N) + O(N log N) + O(N log N) + O(N²)
The O(N²) term clearly dominates the entire sum.
So, the total time complexity is O(N²).
Answer:
(C) O(N²)

Ques 23 Gate 2016 Set-2

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

Greedy paradigm.

Divide-and-Conquer paradigm.

Dynamic Programming paradigm.

neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

(G) is the correct answer.

Given:
Floyd-Warshall algorithm for all-pair shortest paths computation.
To find:
The algorithm design paradigm it is based on.
Solution:
Let me recall how the Floyd-Warshall algorithm works.
It computes the shortest path between all pairs of vertices in a directed, weighted graph.
Let d^(k)[i][j] be the shortest path from vertex i to vertex j using only intermediate vertices from the set {1, 2, ..., k}.
The recurrence relation is:
d^(k)[i][j] = min(d^(k-1)[i][j], d^(k-1)[i][k] + d^(k-1)[k][j])
This shows that the problem exhibits optimal substructure and overlapping subproblems.
We build the solution bottom-up by iteratively increasing the set of allowed intermediate vertices from k = 1 to n.
Therefore, this algorithm directly uses the Dynamic Programming approach.
Answer: (C) Dynamic Programming paradigm.

Total Unique Visitors

Loading......

CS/IT Gate Subject

Design Algorithm Analysis GATE previous year questions with answer

Question Options

Sign in to ExamPrev