Back to Study Material GATE Exam

Design and Analysis of Algorithms

Design and Analysis of Algorithms (DAA) carries approximately 8 to 12 marks in GATE CS and tests your ability to understand why algorithms work, not just h...

Design and Analysis of Algorithms

Algorithmic Paradigms: Divide and Conquer, Greedy, and Dynamic Programming

Design and Analysis of Algorithms (DAA) carries approximately 8 to 12 marks in GATE CS and tests your ability to understand why algorithms work, not just how they work. The three main paradigms are divide and conquer, greedy algorithms, and dynamic programming. Understanding each paradigm deeply allows you to analyse novel algorithms in the exam even if you have not seen them before.

Divide and conquer splits the problem into independent subproblems, solves each recursively, and combines the results. The paradigm is most effective when the subproblems are smaller by a constant factor (not a constant additive amount) and the combine step is efficient. Classic examples include merge sort, quick sort, binary search, and Strassen's matrix multiplication. The time complexity is analysed using the Master Theorem or the recursion tree method.

Greedy algorithms make locally optimal choices at each step with the hope that this leads to a globally optimal solution. The critical insight is that a greedy algorithm is correct only when the greedy choice property and the optimal substructure property hold. The greedy choice property states that a globally optimal solution includes the locally optimal choice. Optimal substructure states that the optimal solution to the problem contains optimal solutions to subproblems.

Classic greedy algorithms: activity selection (select the maximum number of non-overlapping intervals by always choosing the interval that ends earliest), Huffman coding (build the optimal prefix-free binary code by always merging the two lowest-frequency nodes), Dijkstra's algorithm (always relax the vertex with the smallest tentative distance), Prim's and Kruskal's MST algorithms.

Dynamic programming (DP) solves problems with overlapping subproblems and optimal substructure by storing the results of subproblems to avoid recomputation. The two DP formulation approaches are top-down (memoisation: recurse and cache results) and bottom-up (tabulation: fill a table iteratively from smallest subproblems). Classic DP problems tested in GATE: longest common subsequence, longest increasing subsequence, 0/1 knapsack, matrix chain multiplication, and all-pairs shortest paths using Floyd-Warshall.

The skill of recognising which paradigm applies to a given problem is itself tested in GATE. Greedy works when subproblems are independent and the greedy choice is safe. DP is needed when subproblems overlap and each depends on others. Divide and conquer is suited for independent subproblems of roughly equal size.

NP-Completeness and Computational Complexity

Computational complexity theory studies which problems can be solved efficiently and which cannot. This topic carries 2 to 4 marks in GATE CS and requires precise knowledge of definitions and reductions.

The class P contains decision problems solvable in polynomial time by a deterministic algorithm. The class NP contains decision problems whose solutions can be verified in polynomial time. Every problem in P is also in NP because a polynomial-time algorithm is also a polynomial-time verifier. The central unsolved question is whether P equals NP.

An NP-hard problem is at least as hard as every problem in NP. Formally, a problem X is NP-hard if every problem in NP can be polynomial-time reduced to X. An NP-complete problem is in NP and is NP-hard. If any NP-complete problem is solvable in polynomial time, then P equals NP.

The first NP-complete problem proven was 3-SAT (Boolean satisfiability with clauses of exactly 3 literals) by Cook's theorem. Other NP-complete problems include independent set, vertex cover, clique, Hamiltonian cycle, travelling salesman decision version, subset sum, and 3-coloring. GATE has asked you to identify whether specific problems are in P or NP-complete.

Polynomial-time reductions are the tool for proving NP-hardness. To prove problem Y is NP-hard, show that a known NP-hard problem X can be reduced to Y in polynomial time. If X is easy to solve using a solver for Y, then Y must be at least as hard as X.

Important reductions for GATE: 3-SAT reduces to independent set, independent set reduces to vertex cover (complement relationship: if S is an independent set, then V minus S is a vertex cover), clique reduces to independent set (complement graph), and SAT reduces to 3-SAT.

Approximation algorithms are used when exact polynomial-time algorithms are unlikely to exist. A 2-approximation for vertex cover works by repeatedly selecting any uncovered edge, adding both its endpoints to the cover, and removing all edges covered by these vertices. This always produces a vertex cover at most twice the optimal size.

GATE questions on this topic typically ask you to classify a given problem as P, NP-complete, or NP-hard, or to determine whether a given reduction correctly establishes NP-hardness. Study the reductions carefully rather than memorising conclusions blindly.

Dynamic Programming: Problem Formulation and GATE Questions

Dynamic programming problems require you to define a state, write a recurrence relation, identify the base case, and determine the order of computation. Mastering this four-step process allows you to solve both standard DP problems and variations encountered in GATE.

Longest Common Subsequence (LCS): given two sequences X of length m and Y of length n, find the length of their longest common subsequence. State: LCS[i][j] is the length of the LCS of X[1..i] and Y[1..j]. Recurrence: if X[i] equals Y[j], LCS[i][j] = LCS[i-1][j-1] + 1; otherwise LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]). Base case: LCS[i][0] = 0 and LCS[0][j] = 0. Time: O(mn), Space: O(mn) or O(min(m,n)) with space optimisation.

0/1 Knapsack: given n items each with weight w[i] and value v[i], and a knapsack of capacity W, maximise total value without exceeding capacity. State: K[i][w] is the maximum value achievable using the first i items with capacity w. Recurrence: if w[i] is greater than w, K[i][w] = K[i-1][w]; otherwise K[i][w] = max(K[i-1][w], v[i] + K[i-1][w-w[i]]). Time: O(nW), Space: O(nW).

Matrix Chain Multiplication: given n matrices, find the optimal parenthesisation to minimise scalar multiplications. State: M[i][j] is the minimum cost to multiply matrices i through j. Recurrence: M[i][j] = min over k from i to j-1 of (M[i][k] + M[k+1][j] + p[i-1] times p[k] times p[j]), where p[i] gives matrix dimensions. Time: O(n cubed), Space: O(n squared).

Coin change (minimum coins): given denominations and a target amount, find the minimum number of coins. State: dp[i] is the minimum coins for amount i. Recurrence: dp[i] = 1 + min over each coin c of dp[i - c], for i - c greater than or equal to 0. Base case: dp[0] = 0.

Worked GATE example: what is the length of the LCS of "ABCBDAB" and "BDCABA"? Building the LCS table systematically gives a length of 4 (one LCS is "BCBA"). GATE may ask for the length or the number of distinct LCS sequences.

For exam success, practise filling DP tables by hand. Understanding the fill order (usually bottom-up, row by row) prevents index errors. Always verify your recurrence with a small example before applying it to the full problem.