Algorithms — GATE CS Complete Guide
From asymptotic analysis to NP-completeness — every algorithm concept tested in GATE CS, explained with worked examples.
Last updated: April 2026 | GATE CS 2024–2026 syllabus
Why Algorithms?
- 10–14 marks combined with Data Structures — the single highest-weight area in GATE CS.
- Questions test analysis (recurrences, Master theorem) as much as algorithm mechanics.
- Dynamic programming and graph algorithms appear almost every year.
- NP-completeness: at least 1–2 marks on reductions and problem classification.
- Greedy correctness proofs (exchange argument) are a common trap for unprepared students.
GATE Weightage
| Topic | Avg Marks | Frequency |
|---|---|---|
| Dynamic Programming | 2–3 | Every year |
| Graph Algorithms | 2–3 | Every year |
| Asymptotic Analysis & Recurrences | 1–2 | Very high |
| Sorting Algorithms | 1–2 | High |
| NP-Completeness | 1–2 | High |
| Greedy Algorithms | 1 | Moderate |
| Divide & Conquer | 1 | Moderate |
Topic Pages
| # | Topic | Key Concepts |
|---|---|---|
| 1 | Asymptotic Analysis | Big-O, Θ, Ω, Master theorem, recurrences |
| 2 | Sorting Algorithms | Comparison sorts, linear sorts, stability, lower bound |
| 3 | Divide & Conquer | MergeSort, QuickSort, Binary Search, Strassen |
| 4 | Dynamic Programming | LCS, LIS, Knapsack, Matrix chain, Floyd-Warshall |
| 5 | Greedy Algorithms | Activity selection, Huffman, Kruskal, Prim, Dijkstra |
| 6 | Graph Algorithms | Shortest paths, MST, SCC, flow networks |
| 7 | NP-Completeness | P vs NP, reductions, NP-hard, NP-complete problems |
| 8 | Formula Sheet | All complexities, recurrences, key results |