Algorithms

Asymptotic notation

The notations O, Omega, Theta, little-o and little-omega with their exact definitions, the limit test, the properties that make them usable, the hierarchy of growth rates from constants to factorials, logarithm and exponent facts, Stirling's approximation and the standard sums, with the usual mistakes.

Analysing loops, time and space

How to find the running time and the space of an algorithm: the machine model, input size, best, worst and average case, rules for sequences, nested and dependent loops, logarithmic and harmonic loops, recursion depth as space, and why a loop up to the value of the input is exponential in the input size.

Solving recurrences: substitution, tree and Master theorem

Solving the recurrences of recursive algorithms: the recursion tree, the substitution method with induction, the Master theorem with its three cases and the logarithmic extension, the recurrences it does not cover, and a table of the standard solutions.

Linear and binary search

Finding a key in a collection: linear search and its best, worst and average cost, binary search on a sorted array with its invariant, the exact worst case floor(log2 n) + 1, why this is optimal, the midpoint overflow, the first-occurrence variant, and why binary search needs both order and random access.

Bubble, selection and insertion sort

The three elementary quadratic sorts: how each works and its invariant, exact comparison and swap counts on best and worst inputs, inversions as the common measure (bubble swaps and insertion shifts both equal the number of inversions), adaptivity, binary insertion sort, and why adjacent-swap sorts need quadratic time on average.

Divide and conquer

The divide and conquer paradigm: split a problem into independent smaller copies, solve them recursively, combine the answers. The recurrence T(n) = aT(n/b) + f(n), what the three Master theorem cases mean for where the work is done, the maximum-and-minimum example (3n/2 - 2 comparisons), correctness by induction, stack depth, and why overlapping subproblems need dynamic programming instead.

Divide and conquer applications

The standard divide and conquer algorithms of the syllabus with their recurrences: fast exponentiation, maximum subarray, counting inversions, Karatsuba multiplication, Strassen matrix multiplication, closest pair of points and linear-time selection by the median of medians; each with the idea, the recurrence, the solution and the points where GATE asks.

Merge sort

Merge sort: split in halves, sort each, merge the two sorted runs. The merge procedure and its invariant, the exact best and worst case comparison counts (n log2 n - n + 1 in the worst case for n a power of two), Theta(n log n) in every case, why it is stable and needs linear extra space on arrays, bottom-up and linked-list versions, and k-way merging.

Quicksort

Quicksort: partition around a pivot, sort the two sides in place. The partition and its invariant, the recurrence for any split, the worst case n(n-1)/2 on sorted input, the balanced best case, the exact average 2(n+1)H_n - 4n comparisons (about 1.39 n log2 n), why any constant-fraction split is still n log n, randomised pivots, the stack depth and the smaller-part-first rule, and behaviour with equal keys.

Heap sort

Heap sort as an algorithm: build a max-heap bottom-up in linear time, then repeatedly swap the maximum to the end and sift down. Why building costs at most 2n comparisons, why the extraction phase makes it Theta(n log n) in every case, its constants against quicksort and merge sort, and its properties (in place, not stable, not adaptive).

Lower bound and linear-time sorts

Why no comparison sort can beat n log n (the decision tree argument with n! leaves), how counting sort, radix sort and bucket sort sort in linear time by using the values of the keys instead of comparisons, their costs Theta(n + k), Theta(d(n + k)) and expected Theta(n), why stability makes radix sort correct, and when each applies.

Stability, in-place and comparison of sorts

The properties that GATE asks about for every sorting algorithm: stable, in place, adaptive, online, the best, average and worst case and the extra space of bubble, selection, insertion, merge, quick, heap and counting sort; why stability matters, how it is lost, how to restore it, and which sort to choose for which situation.

Hashing: functions and collisions

Hash tables as a dictionary with expected constant time: direct addressing, hash functions and the table size, the division and multiplication methods and why the choice of m matters, string hashing, universal hashing, the load factor, why collisions are unavoidable and appear far sooner than expected (the birthday paradox).

Chaining and open addressing

The two ways to resolve collisions: chaining (one linked list per slot) and open addressing (linear probing, quadratic probing, double hashing). Insert, search and delete in each, probe sequences and when they cover the whole table, primary and secondary clustering, why deletion in open addressing needs a tombstone, and how to decide whether a given table could have been produced by a sequence of insertions.

Load factor and expected probes

The expected cost of hashing as a function of the load factor alpha = n/m: chaining (alpha for an unsuccessful and 1 + alpha/2 for a successful search), open addressing under uniform hashing (1/(1 - alpha) and (1/alpha) ln(1/(1 - alpha))), linear probing (the Knuth formulas with the squared denominator), the derivations, measured values, and the expected number of empty slots and colliding pairs.

Greedy method and exchange argument

The greedy method: build a solution by always making the choice that looks best now. The two properties that make it correct (greedy-choice property and optimal substructure), the exchange argument and greedy stays ahead as proof methods, the shortest-processing-time rule as a first proof, the coin-change example that shows greedy failing for some coin systems, and a list of the greedy algorithms of the syllabus.

Activity selection and fractional knapsack

Three classic greedy algorithms with their proofs: activity selection (earliest finish first, why earliest start and shortest first fail), the fractional knapsack (best value per unit weight first, why the same rule fails for 0/1 knapsack), and job sequencing with deadlines and profits; also interval partitioning (minimum number of rooms equals the maximum overlap). Running times and worked GATE-style instances.

Huffman coding

Optimal prefix codes: variable-length codes, the prefix property and the Kraft inequality, Huffman's algorithm (repeatedly merge the two least frequent symbols, with a min-heap in O(n log n)), the cost as the sum of the weights of the internal nodes, a worked tree and code table, why the greedy choice is optimal, decoding, tie-breaking, extreme shapes of the tree, and the entropy bounds.

Dynamic programming and memoization

Dynamic programming: solve a problem by solving overlapping subproblems once and remembering the answers. Optimal substructure and overlapping subproblems, memoization (top-down) against tabulation (bottom-up), how to find the state and the recurrence, the running time as the number of states times the work per state, reconstructing the solution, saving space, and the contrast with divide and conquer and greedy. Fibonacci numbers and a grid path as worked examples.

LCS, edit distance, knapsack and matrix chain

The four classic dynamic programs of the syllabus: longest common subsequence, edit distance, 0/1 knapsack and matrix chain multiplication. For each: the state, the recurrence, the table filled step by step, how to recover the solution, the running time and space, and the standard facts GATE asks (table sizes, pseudo-polynomial time, Catalan number of parenthesisations).

DP on sequences: LIS and coin change

Two dynamic programs on a line: the longest increasing subsequence (the quadratic table and the n log n tails array with binary search) and coin change (the fewest coins, the number of ways, and why the order of the loops decides whether orders are counted). The recurrences, tables filled step by step, running times, why greedy fails for coin change, and the standard traps.

BFS and DFS

The two basic graph searches. Breadth-first search with a queue (distances in edges, shortest paths in unweighted graphs, levels) and depth-first search with colours and discovery and finish times (parenthesis and white-path theorems), both in O(V + E) with adjacency lists and O(V^2) with a matrix; applications: reachability, connected components, bipartiteness, cycle detection; the traps in marking and in the order of neighbours.

DFS edge types, topological sort and SCC

What a depth-first search of a directed graph reveals: the four kinds of edges (tree, back, forward, cross) decided by colours and times, that a directed graph has a cycle exactly when there is a back edge, topological sorting of a DAG by decreasing finish time and by Kahn's algorithm (and when the order is unique), and strongly connected components by Kosaraju's two searches.

Spanning trees and the cut property

Spanning trees and minimum spanning trees: definition, V - 1 edges, how many spanning trees a graph has (Cayley's n^(n-2)), the cut property and the cycle property that make greedy choices safe, the generic MST algorithm, uniqueness when weights are distinct, invariance of the MST under order-preserving changes of weights, the bottleneck property, and the difference from shortest-path trees.

Kruskal and Prim

The two classic minimum spanning tree algorithms: Kruskal (sort the edges, add each edge that joins two different trees, with union-find using union by rank and path compression) and Prim (grow one tree by the cheapest edge leaving it, with an array in O(V^2) or a binary heap in O(E log V)); their correctness from the cut property, running times, how they compare, and traces on a 7-vertex graph.

Dijkstra's algorithm

Single-source shortest paths with non-negative weights: relaxation and the triangle inequality, Dijkstra's algorithm (repeatedly finish the unfinished vertex with the smallest distance and relax its edges), why it is correct and why a negative edge breaks it, running times O(V^2) with an array, O((V + E) log V) with a binary heap and O(E + V log V) with a Fibonacci heap, path reconstruction, and the difference from BFS and from Prim.

Bellman-Ford

Single-source shortest paths when edge weights may be negative: relax every edge V - 1 times, why V - 1 passes suffice (a shortest path has at most V - 1 edges), the early stop when a pass changes nothing, detection of negative cycles by one more pass, running time O(VE), why undirected negative edges are negative cycles, and when to use it instead of Dijkstra.

Floyd-Warshall

All-pairs shortest paths by dynamic programming: D[i][j] after iteration k is the shortest path using only the vertices 0 to k as intermediates; the three nested loops and why k must be the outer one, O(V^3) time and O(V^2) space, negative edges and negative cycles (a negative diagonal), path reconstruction with a predecessor matrix, transitive closure (Warshall), and the comparison with running Dijkstra or Bellman-Ford from every vertex.