Algorithms
Algorithms tests asymptotic analysis, recurrences, sorting, divide-and-conquer, greedy method, dynamic programming, and graph algorithms. ISRO favors questions where a correct recurrence or invariant determines the answer.
Core rules and concepts
- Master theorem for T(n)=aT(n/b)+f(n): compare f(n) with n^(log_b a). If polynomially smaller, T(n)=Θ(n^(log_b a)); if equal, multiply by log n; if polynomially larger and regular, T(n)=Θ(f(n)).
- Greedy algorithms need an exchange argument or matroid structure; 0/1 knapsack is not solved optimally by value/weight greedy, while fractional knapsack is.
- Dynamic programming requires optimal substructure and overlapping subproblems; define the state and recurrence before filling the table.
- Dijkstra requires nonnegative edge weights; Bellman–Ford handles negative edges and detects negative cycles in V−1 relaxation rounds.
- Comparison sorting has Ω(n log n) lower bound; counting and radix sort escape it only under bounded-key assumptions.
Worked example
0/1 knapsack with capacity 5 and items (weight, value): (2,3), (3,4), (4,5). Let dp[j] be the best value for capacity j. Process item 1: dp[2..5]=3. Item 2: for j=5, max(3,4+dp[2])=7; for j=3, 4. Item 3: j=5 gives max(7,5+dp[1])=7; j=4 gives max(3,5)=5. The optimum is 7, using items 1 and 2 with total weight 5. Greedy by value/weight would pick item 1 then item 2 as well here, but that coincidence is not a proof.
Traps that cost marks
Applying the master theorem without checking regularity; assuming Dijkstra works with negative edges; confusing stable sort with in-place sort; and forgetting that DP table dimensions and initialization encode the problem’s constraints.