Algorithms
Algorithms carries the largest single weight in the technical part. It tests asymptotic analysis, recurrence solving, the greedy/divide-and-conquer/dynamic-programming paradigms, and graph algorithms. Marks come from recognising which paradigm applies and from precise complexity accounting.
Analysis toolkit
- O is an upper bound, Ω a lower bound, Θ a tight bound; a function can be O(n²) without being Θ(n²).
- Master theorem for T(n) = aT(n/b) + f(n): compare f(n) with n^(log_b a). If f is polynomially smaller, T = Θ(n^(log_b a)); if polynomially larger (and regular), T = Θ(f(n)); if equal up to a log factor, multiply by log n.
Paradigms
- Greedy: activity selection, Huffman coding, Kruskal and Prim - correct only when the greedy-choice property holds.
- DP: optimal substructure plus overlapping subproblems - 0/1 knapsack, LCS, matrix-chain multiplication, Floyd–Warshall.
- Divide and conquer: merge sort Θ(n log n) always; quicksort Θ(n log n) average but Θ(n²) worst.
Graphs
- BFS gives shortest paths in unweighted graphs; DFS gives components and cycle detection.
- Dijkstra with a binary heap is O((V+E) log V) and fails on negative edges; Bellman–Ford is O(VE) and detects negative cycles.
Worked example
Solve T(n) = 2T(n/2) + n log n. Here a = 2, b = 2, so n^(log₂2) = n, and f(n) = n log¹ n. This is the extended equal case with k = 1, giving T(n) = Θ(n log² n) - not Θ(n log n).
Traps that cost marks
- Applying the master theorem when f(n) is not polynomially comparable to n^(log_b a).
- Forgetting that quicksort and heapsort are not stable.