ALG · GATE CS 2027
11 topics and 24 sheets. Open a topic for its sheets and the topics it depends on.
O, Omega, Theta, little-o and little-omega with their constants, limit test and properties; the growth ladder with logs, powers, exponentials and factorials; comparing functions by logarithms; counting loop iterations exactly; worst, best and average case; space and recursion stack; recurrences by substitution, recursion tree and the master theorem with its cases and its limits.
Linear search counts, binary search with exact probe counts, first and last occurrence, lower and upper bound, rotated sorted arrays, interpolation and ternary search, and the comparison lower bound for searching.
Insertion, selection and bubble sort with exact comparisons and swaps, inversions, merge sort, quicksort with Lomuto and Hoare partitions and pivot cases, heap sort, counting, radix and bucket sort, the n log n comparison lower bound and a master comparison table.
Division and multiplication hash functions, simple uniform hashing, chaining with load factor and expected costs, open addressing with linear, quadratic and double hashing, primary and secondary clustering, expected probes, deletion with tombstones and full insertion traces.
The divide, conquer and combine pattern and its recurrences: binary search, merge sort, quicksort, maximum and minimum in 3n/2 - 2 comparisons, fast exponentiation, Karatsuba and Strassen counts, inversion counting, maximum subarray and closest pair.
Greedy choice and optimal substructure with exchange arguments; activity selection, fractional knapsack, job sequencing with deadlines, Huffman coding with average code length, optimal merge pattern, and counterexamples where greedy fails.
Overlapping subproblems and optimal substructure, memoisation and tabulation; LCS, edit distance, 0/1 knapsack, subset sum, coin change counting and minimum coins, matrix-chain multiplication and longest increasing subsequence, each with its table, fill order and cost.
BFS and DFS on adjacency lists and matrices, BFS levels, DFS discovery and finish times, edge classification, topological sort, connected and strongly connected components, cycle detection, bipartite testing, articulation points and bridges.
Cut and cycle properties, Kruskal with union-find, Prim with a priority queue, uniqueness conditions, effect of changing weights, counting spanning trees and how an MST differs from a shortest-path tree.
Relaxation, Dijkstra and why negative edges break it, Bellman-Ford with negative-cycle detection, shortest and longest paths in a DAG, Floyd-Warshall, BFS for unweighted graphs and a complexity table by representation and data structure.
The wrong turns that cost marks, recognition cues and routines for each question pattern, and a last-day sheet of bounds, counts and checks.
Formal definitions of O, Omega, Theta, little-o and little-omega with their constants c and n0; the limit test and when it is inconclusive; reflexive, symmetric, transpose and transitive properties; sum and product rules; the growth ladder from constants through logarithms, powers, exponentials and factorials; Stirling's formula and log n!; comparing functions by taking logarithms, with an ordering of eight functions checked by script and the crossover that makes small-n checks misleading; log bases versus exponent bases.
Exact iteration counts for the loop shapes that appear in code questions (dependent bounds, doubling, halving, squaring, square-root bounds, harmonic and logarithmic inner loops, geometric nests, triple nests), each checked by simulation at n = 16 and n = 1000; the sums they reduce to; worst, best and average case with the linear search example; input size measured in bits and why that makes trial division exponential; space complexity, auxiliary versus total, and recursion stack depth for common algorithms.
The master theorem for T(n) = aT(n/b) + f(n) with its three cases, the regularity condition and the extended case-2 form for polylog factors; the recurrences it does not cover; the recursion-tree method shown on the uneven split T(n/3) + T(2n/3) + n; substitution with the lower-order-term trick; change of variables for square roots; unrolling subtract-and-conquer recurrences; and a table of 20 solved recurrences, each checked numerically by script.
Linear search counts; iterative binary search with its loop invariant and exact worst-case probe count, average successful and unsuccessful probes; first and last occurrence, lower and upper bound and counting duplicates, with traces; search and minimum in a rotated sorted array and why duplicates break it; interpolation search and its uniform-key assumption; ternary and exponential search; the comparison lower bound for searching a sorted array. All traces come from a script with 0-based indices.
Insertion, selection and bubble sort as code-level procedures, traced pass by pass on one array with every state, comparison and swap counted by script; exact best and worst counts; inversions and why insertion shifts and bubble swaps both equal the inversion count; the exact comparison count of insertion sort; the number of bubble passes; stability with a counterexample for selection sort; adaptivity, online behaviour and counts on sorted, reversed and equal inputs.
Merging two sorted lists with best and worst comparison counts; merge sort's exact worst-case count, number of merges, space and stability, with the solved GATE CS 2026 Set 2 Q.32; quicksort with the Lomuto partition traced step by step and the Hoare partition traced on the same array; pivot choices and the inputs that make quicksort quadratic, including equal keys; best, average and worst recurrences; the exact expected comparison count with a random pivot; unbalanced but constant splits; stack depth; quickselect.
Heap sort as build-max-heap followed by n - 1 extractions, traced on five keys, with its cost, instability and in-place behaviour; counting sort traced with prefix sums and a right-to-left scan that keeps it stable; LSD radix sort traced digit by digit with its cost in digits and base; bucket sort with its uniform-input assumption and worst case; the decision-tree argument for the comparison lower bound with exact values of ceil(lg n!) for n up to 12, and which sorts escape it.
A master table of bubble, selection, insertion, merge, quick, heap, counting, radix and bucket sort with best, average and worst time, extra space, stability, in-place and adaptive behaviour and the exact comparison or swap counts; a second table of measured comparison and swap counts for eight keys in sorted, reversed, all-equal and mixed order; recognition cues for choosing a sort; stability and in-place definitions; and commonly confused facts.
Direct addressing versus hashing; the load factor; division and multiplication hash functions with worked values and the reason to avoid powers of two; universal hashing; the simple uniform hashing assumption; separate chaining with its insert, search and delete costs, expected comparisons for successful and unsuccessful search and the worst case; the solved GATE CS 2026 Set 2 Q.30 drawn as a chained table; collision probabilities, expected empty slots and colliding pairs; chaining compared with open addressing.
Linear, quadratic and double hashing probe sequences and the conditions for visiting every slot; one key set inserted three ways into an 11-slot table with every probe counted; primary and secondary clustering; expected probes under uniform hashing and for linear probing at three load factors; deletion with tombstones and what goes wrong without them; quadratic probing coverage with a prime table size; the solved GATE CS 2026 Set 1 Q.24. Every table comes from a script.
The divide, conquer and combine pattern and when it beats a direct method; a master table of recurrences and solutions; simultaneous maximum and minimum with the pairwise count ceil(3n/2) - 2 against the halving recursion (which loses for some n); second largest; fast exponentiation with its exact multiplication count; Karatsuba and Strassen multiplication counts; counting inversions during merge sort; maximum subarray by divide and conquer and by Kadane's scan; closest pair of points. All counts by script.
The greedy-choice property and optimal substructure, with the exchange argument used to prove a greedy rule; activity selection by earliest finish with a full trace and the rules that fail (shortest first, earliest start) shown by counterexamples; fractional knapsack by value per weight and why the same rule fails for 0/1 knapsack; job sequencing with deadlines and unit times using the latest free slot; coin systems where greedy change is and is not optimal. Every greedy answer is compared with brute force by script.
Prefix-free codes and why decoding is unambiguous; Huffman's algorithm with a min-priority queue, traced on six symbols with the resulting tree, codes, weighted cost and average code length, compared with a fixed 3-bit code and checked against every valid set of code lengths; properties of Huffman trees (full, Kraft equality, the two rarest symbols as deepest siblings, longest possible code); tie-breaking and why the cost never changes; encoding a word; the optimal merge pattern for sorted files with its record-move total.
Optimal substructure and overlapping subproblems; memoisation versus tabulation with the exact call count of naive Fibonacci; a four-step routine for designing any DP and its cost formula; longest common subsequence with its recurrence, a filled table with arrows and traceback for GATE and GREAT, tie rules and space saving; longest common substring as a different DP; edit distance with its recurrence, base cases and a filled table, plus its relation to LCS when only insertions and deletions are allowed.
0/1 knapsack with its recurrence and a fully filled table, the one-array version and why the capacity loop runs downward, unbounded knapsack by running it upward; why O(nW) is pseudo-polynomial; subset sum as a boolean table with every reachable sum per row and the subsets that hit the target; counting coin combinations versus ordered sequences and how the loop order decides which one you get; minimum number of coins with unreachable amounts. All tables are produced by script.
Matrix-chain multiplication: the cost of one product, the interval recurrence, the m and s tables filled by chain length for four matrices with the optimal parenthesisation read from s, every order's cost compared, the Catalan count of parenthesisations, and time and space; longest increasing subsequence by the quadratic DP and by the n log n tails method with a full trace, why the tails array is not itself a subsequence, and the link to LCS; a summary of DP problems with states, recurrences and costs.
Breadth-first and depth-first search with their data structures, the order rule for neighbours, costs on adjacency lists and matrices, BFS levels and fewest-edge paths traced on six vertices, the level rule for non-tree edges; DFS discovery and finish times, the parenthesis and white-path theorems, classification of tree, back, forward and cross edges by colour and by time intervals, drawn on one DFS forest; what changes for undirected graphs; counting components from a DFS forest with the solved GATE CS 2024 Set 1 Q.60.
Topological sort by decreasing DFS finish time and by Kahn's in-degree method, traced on one DAG; counting topological orders and the exact condition for a unique order; cycle detection in directed and undirected graphs; connected components; strongly connected components with Kosaraju's two passes and Tarjan's one-pass method, traced on eight vertices, and the condensation DAG; bipartite testing by BFS two-colouring; articulation points and bridges from DFS low values with a traced example checked by brute force.
Spanning trees and the minimum spanning tree; the cut property and the cycle property with their exact conditions; Kruskal with union-find, traced edge by edge on a six-vertex graph and drawn with the acceptance order; Prim with a priority queue on the same graph and its cost for array, binary-heap and Fibonacci-heap queues; when the MST is unique and a test for it; effects of adding, scaling or squaring weights with the solved GATE CS 2025 Set 2 Q.37; counting spanning trees; MST versus shortest-path tree.
Relaxation and predecessor pointers; Dijkstra's algorithm traced vertex by vertex on a five-vertex graph with the distance table after each extraction and the shortest-path tree drawn, its cost with an array, binary heap and Fibonacci heap, and a small graph where one negative edge makes it wrong; Bellman-Ford with V - 1 rounds traced under a fixed edge order, early stopping, negative-cycle detection and its dynamic programming recurrence; what shortest paths mean when a negative cycle is reachable.
Shortest and longest paths in a DAG by relaxing in topological order, traced with a negative edge; Floyd-Warshall's recurrence, the matrices after every intermediate vertex for a four-vertex graph with a negative edge, in-place updates, negative-cycle detection on the diagonal and path recovery; Warshall's transitive closure; BFS for unweighted graphs; a complexity table of every shortest-path method by representation and data structure; a decision flow for choosing one; weight changes and their effect.
Thirty-two common mistakes across the Algorithms syllabus, each stated as the tempting belief, the correct rule and a short reminder with the page that explains it: asymptotic notation and the master theorem, loop counts, searching, every sort's cost and stability, hashing and probing, divide and conquer, greedy versus dynamic programming, traversal edge classes and topological orders, minimum spanning trees and shortest paths with negative edges and weight changes.
Twenty question shapes across the Algorithms syllabus, each with the recognition cue, the first step and method to apply, and the assumption or slip that most often changes the answer: recurrences, growth ordering, loop counts, sorting traces and exact counts, merge and partition traces, searching boundaries, hashing traces and probe estimates, greedy correctness, DP tables, traversal statements, topological orders, MST and shortest-path traces and weight changes; plus a three-step routine for any question.
A one-page summary of the pack for the last evening: the master theorem with its conditions, recurrences to know, the growth ladder, sorting costs and stability, exact comparison counts, hashing costs, greedy rules that work, DP recurrences and costs, traversal facts, MST and shortest-path algorithms with their weight conditions and costs, and the numbers worth remembering. Every value repeats one computed on an earlier sheet.
Engineering MathematicsData StructuresDatabase Management SystemsProgramming in CComputer Networks
