Back to Study Material GATE Exam

Last Minute Notes Algorithms

Last-minute notes for algorithms focus on precise complexity values and key theorems you must recall instantly during the exam. Read through each section, ...

Last Minute Notes Algorithms

Quick Reference: Sorting, Searching, and Master Theorem

Last-minute notes for algorithms focus on precise complexity values and key theorems you must recall instantly during the exam. Read through each section, cover it, and test recall before moving on.

Sorting complexities (worst case unless stated): bubble sort O(n squared), selection sort O(n squared), insertion sort O(n squared) worst O(n) best, merge sort O(n log n), quick sort O(n squared) worst O(n log n) average, heap sort O(n log n), counting sort O(n+k), radix sort O(d(n+k)), bucket sort O(n) average.

Searching: linear search O(n), binary search O(log n) (requires sorted array), jump search O(sqrt(n)), interpolation search O(log log n) average for uniformly distributed data.

Master Theorem for T(n) = aT(n/b) + n raised to c: if log base b of a is greater than c, then T(n) = Theta(n raised to log base b of a). If log base b of a equals c, then T(n) = Theta(n raised to c times log n). If log base b of a is less than c, then T(n) = Theta(n raised to c). Quick applications: T(n) = 2T(n/2) + n gives Theta(n log n). T(n) = 4T(n/2) + n gives Theta(n squared). T(n) = 2T(n/2) + n squared gives Theta(n squared). T(n) = T(n/2) + 1 gives Theta(log n).

Important recurrence solutions to memorise: Fibonacci recurrence T(n) = T(n-1) + T(n-2) gives T(n) = Theta(phi raised to n) where phi is the golden ratio approximately 1.618. Linear recurrence T(n) = T(n-1) + n gives T(n) = Theta(n squared). Logarithmic recurrence T(n) = T(n/2) + n gives T(n) = Theta(n).

String matching: naive algorithm O(mn) where m is pattern length and n is text length. KMP algorithm O(n + m) using the failure function. Rabin-Karp O(mn) worst case O(n + m) average using rolling hash. Boyer-Moore O(mn) worst case O(n/m) best case. GATE most commonly tests KMP.

Select algorithm (order statistics): finding the kth smallest element using randomised quick select runs in O(n) average time. The deterministic median-of-medians algorithm guarantees O(n) worst-case time.

Strassen's matrix multiplication: multiplies two n by n matrices in O(n raised to log base 2 of 7) = O(n raised to 2.81) time, improving over the naive O(n cubed). The recurrence is T(n) = 7T(n/2) + n squared. GATE has asked for the exponent.

DP Formulas and Greedy Algorithm Checklist

Dynamic programming formulas to keep at your fingertips during last-minute revision. Each formula is presented with the problem definition and key parameters.

Fibonacci (memoised): fib(n) = fib(n-1) + fib(n-2), fib(0) = 0, fib(1) = 1. Memoised version runs in O(n) time and O(n) space. Iterative version uses O(1) space.

Longest Common Subsequence: LCS(i,j) = LCS(i-1,j-1) + 1 if characters match; max(LCS(i-1,j), LCS(i,j-1)) otherwise. Time O(mn), Space O(mn) or O(min(m,n)).

Longest Increasing Subsequence: LIS[i] = 1 + max over all j less than i where A[j] less than A[i] of LIS[j]. Time O(n squared). Binary search variant achieves O(n log n).

Edit Distance (Levenshtein): ED(i,j) = ED(i-1,j-1) if characters match; 1 + min(ED(i-1,j), ED(i,j-1), ED(i-1,j-1)) otherwise. Time O(mn), Space O(mn).

0/1 Knapsack: K(i,w) = K(i-1,w) if item weight exceeds w; max(K(i-1,w), v[i] + K(i-1, w-w[i])) otherwise. Time O(nW), Space O(nW) or O(W).

Matrix Chain Multiplication: M(i,j) = min over k of M(i,k) + M(k+1,j) + p[i-1] times p[k] times p[j]. Time O(n cubed), Space O(n squared).

Floyd-Warshall: dist(i,j,k) = min(dist(i,j,k-1), dist(i,k,k-1) + dist(k,j,k-1)). All-pairs shortest paths in O(V cubed) time.

Greedy algorithm checklist: (1) identify the greedy choice (what local decision looks best right now), (2) verify greedy choice property (making the greedy choice does not rule out an optimal global solution), (3) verify optimal substructure (the subproblem remaining after the greedy choice is also optimally solvable using the same strategy), (4) design the algorithm, (5) prove correctness using exchange argument, (6) analyse time complexity.

Problems where greedy works: activity selection (sort by finish time), fractional knapsack (sort by value/weight), Huffman coding (merge lowest frequencies), Dijkstra (pick minimum distance vertex), Prim's MST (pick minimum weight crossing edge), Kruskal's MST (pick minimum weight edge not forming cycle).

Problems where greedy fails (DP needed): 0/1 knapsack, coin change with arbitrary denominations, longest common subsequence, shortest path with negative edges.

NP-Completeness Quick Facts and Exam Strategy

NP-completeness is a topic where precise definitions matter immensely. Vague understanding leads to wrong answers on GATE questions that test whether specific problems belong to P, NP, NP-hard, or NP-complete.

P: the class of decision problems solvable in polynomial time by a deterministic Turing machine. Examples: sorting, shortest path, MST, primality testing (AKS algorithm).

NP: the class of decision problems where a yes-instance has a polynomial-time verifiable certificate. Every problem in P is in NP. Examples: 3-SAT (certificate: a satisfying assignment), Hamiltonian cycle (certificate: the cycle itself), clique (certificate: the set of vertices).

NP-hard: problems at least as hard as every NP problem under polynomial-time reduction. NP-hard problems may or may not be in NP. The halting problem is NP-hard but not in NP.

NP-complete: problems that are both in NP and NP-hard. These are the hardest problems in NP. If any NP-complete problem is in P, then P equals NP.

Standard NP-complete problems for GATE: Boolean satisfiability (SAT), 3-SAT, vertex cover, independent set, clique, Hamiltonian path, Hamiltonian cycle, travelling salesman decision version, subset sum, graph colouring (k-colouring for k greater than or equal to 3), integer linear programming.

Problems in P (not NP-complete unless P=NP): 2-SAT (solvable in linear time using SCC), 2-colouring (bipartite checking), minimum spanning tree, single-source shortest path (non-negative weights), maximum matching in bipartite graphs (polynomial via network flow).

GATE exam strategy for complexity questions: first check if the problem is a known NP-complete problem or a known polynomial problem. If it is a known problem in disguise (e.g., a graph colouring problem with 3 colours), identify it immediately. If the problem is unfamiliar, look for polynomial-time algorithms (DP, greedy, reduction to flow). If none seem apparent, consider whether it has optimal substructure and overlapping subproblems that would allow DP.

For questions asking to prove NP-completeness, the standard method is to reduce a known NP-complete problem to the new problem in polynomial time. Know at least three reductions cold: SAT to 3-SAT, 3-SAT to independent set, and independent set to vertex cover. These cover most GATE reduction questions.