Advanced Algorithms for GATE CS: Greedy, DP and Graph Techniques with Worked Examples

You have finished basic data structures and asymptotic notation, but advanced Algorithms questions still feel unpredictable. The difficulty is rarely memorising code. It is recognising whether a problem needs divide and conquer, a provably safe greedy choice, dynamic programming, or a graph algorithm before a plausible wrong method traps you.

Choose divide and conquer, a provably safe greedy method, dynamic programming, or a graph algorithm based on the problem's structure.

The Advanced Algorithms map: four paradigms, one decision skill

Divide and conquer, greedy methods, dynamic programming, and graph algorithms each have characteristic problems and techniques.

Paradigm selection is the common thread. A greedy rule may look convincing yet return value 7 on a knapsack instance where DP finds 10. The difference is not implementation. It is whether the local choice has a proof behind it.

Divide and conquer: read a recurrence, not the code

Translate the algorithm description into a recurrence before naming its complexity.

For T(n) = 2T(n/2) + n, we have a = 2, b = 2, and log_b a = log_2 2 = 1. Since f(n) = n = n^1, Master theorem case 2 gives:

T(n) = Θ(n log n).

For T(n) = 8T(n/2) + n^2, log_2 8 = 3. The recursive term grows as n^3, which is polynomially larger than n^2, so case 1 gives:

T(n) = Θ(n^3).

Keep three classics ready. Merge sort follows the first recurrence and takes Θ(n log n). Binary search has T(n) = T(n/2) + 1 = Θ(log n). Quicksort is Θ(n log n) on average, but a fixed first-element pivot on an already sorted array creates splits of sizes 0 and n - 1, producing Θ(n^2) time.

Greedy algorithms: when a local choice is safe

Greedy works when the problem has the greedy-choice property: some locally best choice can be included without destroying a global optimum. Minimum spanning trees, Huffman coding, activity selection, and fractional knapsack are exam-safe examples. The proof matters because the same instinct fails for 0/1 knapsack.

Run Kruskal on vertices A, B, C, D, E with edges AB=1, BD=2, BC=3, AC=4, CD=5, DE=6, CE=7. They are already in increasing order.

1. Accept AB, then BD, then BC. None creates a cycle.

2. Reject AC because A, B, C already form a connected path, so adding it closes cycle A-B-C.

3. Reject CD because C and D are already connected through B.

4. Accept DE, which brings E into the tree.

5. Reject CE, which would now close a cycle.

The MST is {AB, BD, BC, DE} and its weight is 1 + 2 + 3 + 6 = 12. The count check also passes: five vertices require exactly four tree edges.

Dynamic programming: 0/1 knapsack from table to traceback

DP fits when optimal substructure exists and the same subproblems overlap. For capacity W = 8, take A (weight 2, value 3), B (3, 4), C (4, 5), and D (5, 6).

Use dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + v_i) when item i fits. Filling rows from A through D gives:

Thus dp[4][8] = 10. For the traceback, compare it with dp[3][8] = 9. The value changed when D entered, so take D and move to capacity 8 - 5 = 3. At dp[3][3], C was not taken because the value equals dp[2][3] = 4. Move up, then observe that dp[2][3] = 4 differs from dp[1][3] = 3, so take B. The chosen items are B and D, with weight 3 + 5 = 8 and value 4 + 6 = 10.

Graph shortest paths: choose by edge conditions and scope

Why reject Dijkstra when negative edges appear? Consider S→X=2, S→Y=5, and Y→X=-4. Dijkstra initially finalises X at cost 2 because it is closer than Y. After Y is finalised, the route S→Y→X has cost 5 + (-4) = 1, but X has already been settled. The algorithm therefore misses the true shortest path.

Traps that flip answers

Greedy on 0/1 knapsack. In the same example, the value-to-weight ratios are A 3/2 = 1.5, B 4/3 ≈ 1.33, C 5/4 = 1.25, and D 6/5 = 1.2. Ratio order selects A and B, reaching weight 5 and value 7. Neither C nor D then fits. DP returns 10 with B and D, so ratio ordering is valid for fractional knapsack, not the 0/1 version.

Forcing the Master theorem. A recurrence such as T(n) = T(n/3) + T(2n/3) + n has unequal subproblem sizes, so the standard Master theorem does not apply. Use a recursion tree or another suitable method. Logarithmic factors such as n log n also require the version of the theorem that explicitly covers them, or a recursion-tree derivation.

Assuming an MST is unique. Distinct edge weights guarantee a unique MST. Tied weights can permit several MSTs with the same total, although ties do not automatically make the MST non-unique. Check the actual cut and cycle choices before selecting an MSQ option.

How GATE and interviews test Advanced Algorithms

GATE can frame these ideas as a NAT asking for an MST weight or knapsack value, an MSQ about complexity statements, or an MCQ asking which paradigm applies. Recent official notifications and brochures have specified the paper pattern and syllabus scope, so confirm those changing particulars on the official GATE website rather than relying on an old summary.

Interviews ask the same ideas conversationally: why greedy fails, how to improve an O(n^2) approach to O(n log n), or how to trace a knapsack table on a whiteboard. Placement tests often turn those patterns into timed MCQs.

For connected practice, revisit the binary trees and binary search trees deep-dive, then use the GATE CS subject weightage guide to balance Algorithms against the rest of your preparation.

The short version and the next step

• Write the recurrence before analysing divide and conquer.

• Use greedy only when its local choice is provably safe.

• Switch to DP when optimal substructure and overlapping subproblems make repeated work reusable.

• Know which shortest-path algorithm matches the edge conditions and required scope.

• Sanity-check every method on small numbers, especially the knapsack gap between 7 and 10.

For structured coverage, continue with the Zero to Hero complete CS course. Use the GATE Test Series for timed practice across these paradigms, and keep the sorting algorithms comparison as a companion revision read.