Algorithms

Sheet 1

Asymptotic Analysis & Recurrences

7 formulas

Key formulas

Master Theorem ☆

\[ T(n) = aT(n/b)+f(n) \]

Master Theorem — Case 1 ☆

\[ f(n)=O(n^{\log_b a-\epsilon}) \Rightarrow T(n)=\Theta(n^{\log_b a}) \]

Master Theorem — Case 2 ☆

\[ f(n)=\Theta(n^{\log_b a}) \Rightarrow T(n)=\Theta(n^{\log_b a}\log n) \]

Master Theorem — Case 3 ☆

\[ f(n)=\Omega(n^{\log_b a+\epsilon}) \Rightarrow T(n)=\Theta(f(n)) \]

if regularity holds

Merge Sort Recurrence ☆

\[ T(n)=2T(n/2)+O(n) \Rightarrow O(n\log n) \]

Binary Search Recurrence ☆

\[ T(n)=T(n/2)+O(1) \Rightarrow O(\log n) \]

Growth-Rate Ordering ☆

\[ \log n < n^{\epsilon} < n < n\log n < n^2 < 2^n < n! \]

Test your recall

Can you recall the master theorem formula?

Reveal formula

\[ T(n) = aT(n/b)+f(n) \]

GATE traps 4 traps

Master theorem doesn't always apply

The Master theorem does NOT apply when f(n) isn't polynomially comparable to n^log_b a (e.g. f(n) = n/log n) -- these need different methods; recognizing when the theorem simply doesn't apply is itself a common trap.

Θ, O, and Ω aren't interchangeable

Theta, O, and Omega are not interchangeable -- an algorithm can be O(n^2) (a valid upper bound) while its tight bound is actually Theta(n log n). GATE frequently tests whether you can tell 'an upper bound holds' apart from 'the tight bound is.'

Memorize the growth-rate ladder

Memorize the growth-rate ordering to sanity-check answers instantly: log n < n^eps < n < n log n < n^2 < 2^n < n! for any constant eps > 0.

Master theorem needs a≥1, b>1

The Master theorem requires a >= 1 and b > 1 in T(n)=aT(n/b)+f(n) -- plugging in a non-conforming recurrence gives a meaningless result.

Sheet 2

Greedy & Dynamic Programming

3 formulas

Core concepts

• Fractional Knapsack (Greedy): sort by value/weight ratio, take greedily -- always optimal
• Activity selection (Greedy): sort by finish time, pick earliest-finishing compatible activity
• Huffman coding (Greedy): always merge the two lowest-frequency nodes

Key formulas

0/1 Knapsack (DP) ☆

\[ dp[i][w] = \max\big(dp[i{-}1][w],\ dp[i{-}1][w{-}wt_i]+val_i\big) \]

O(nW)

Longest Common Subsequence ☆

\[ dp[i][j] = dp[i{-}1][j{-}1]{+}1 \text{ if match, else } \max(dp[i{-}1][j], dp[i][j{-}1]) \]

O(mn)

Dijkstra (Greedy) ☆

\[ O((V{+}E)\log V) \]

non-negative weights only, binary heap

Test your recall

Can you recall the 0/1 knapsack (dp) formula?

Reveal formula

\[ dp[i][w] = \max\big(dp[i{-}1][w],\ dp[i{-}1][w{-}wt_i]+val_i\big) \]

GATE traps 4 traps

0/1 Knapsack is where greedy fails

Greedy is optimal only for problems with the greedy-choice property PLUS optimal substructure (fractional knapsack, activity selection, Huffman, Dijkstra with non-negative weights). 0/1 knapsack is the textbook counterexample where greedy FAILS and DP is required -- GATE loves this exact contrast.

Dijkstra breaks on negative weights

Dijkstra gives WRONG results with negative edge weights -- Bellman-Ford is needed there, a frequently tested 'which algorithm applies' question.

DP needs overlap, not just recursion

DP requires overlapping subproblems AND optimal substructure -- if subproblems don't overlap, plain divide-and-conquer (no memoization) is the correct classification, not DP.

Memoization vs. tabulation coverage

Memoization (top-down) only computes subproblems actually needed; tabulation (bottom-up) computes all of them -- a subtle but occasionally tested time/space tradeoff.

Sheet 3

Graph Algorithms

6 formulas

Core concepts

• MST of a connected graph with V vertices has exactly V-1 edges

Key formulas

BFS/DFS ☆

\[ O(V{+}E) \]

Dijkstra's Algorithm ☆

\[ O((V{+}E)\log V) \]

with a binary heap

Bellman-Ford ☆

\[ O(VE) \]

handles negative weights, detects negative cycles

Floyd-Warshall ☆

\[ O(V^3) \]

all-pairs shortest path

MST Algorithms ☆

\[ \text{Prim's: } O(E\log V) \qquad \text{Kruskal's: } O(E\log E) \]

Kruskal's uses Union-Find

Topological Sort ☆

\[ O(V{+}E) \]

only valid for DAGs

Test your recall

Can you recall the dijkstra's algorithm formula?

Reveal formula

\[ O((V{+}E)\log V) \]

Reference table

Algorithm	Time Complexity	Negative Weights?	Notes
BFS	O(V+E)	N/A	Unweighted shortest path
DFS	O(V+E)	N/A	Cycle detection
Dijkstra	O((V+E) log V)	✗	Single-source SP, binary heap
Bellman-Ford	O(VE)	✓	Detects negative cycles
Floyd-Warshall	O(V^3)	✓	All-pairs shortest path
Prim's (MST)	O(E log V)	✓	Grows from one vertex
Kruskal's (MST)	O(E log E)	✓	Sorts edges, Union-Find
Topological Sort	O(V+E)	N/A	Only valid for DAGs

GATE traps 4 traps

Topological sort needs a DAG

Topological sort exists if and only if the graph is a DAG -- if GATE gives a graph WITH a cycle, the expected answer is 'no valid ordering exists,' not an attempted computation.

Prim's and Kruskal's can differ, weight can't

Prim's and Kruskal's can produce DIFFERENT minimum spanning trees when edge weights aren't unique, but the TOTAL weight is always the same -- a subtle, frequently tested fact.

BFS only gives shortest paths unweighted

BFS gives shortest paths only in an UNWEIGHTED graph (by edge count) -- using BFS on a weighted graph and expecting correct distances is a classic error; Dijkstra is needed there.

Kruskal's needs Union-Find, not naive checks

Kruskal's needs Union-Find with path compression and union by rank for its near-linear cycle checks -- a naive cycle check makes it much slower, a common complexity-analysis trap.

Sheet 4

Sorting Algorithms

Core concepts

• In-place: sorts using O(1) or O(log n) extra space, not counting the input array.
• Stable: equal-key records keep their original relative order after sorting.

Reference table

Algorithm	Best	Average	Worst	Space	Stable?	In-place?
Bubble Sort *	\(\Theta(n)\)	\(\Theta(n^2)\)	\(\Theta(n^2)\)	\(O(1)\)	✓	✓
Selection Sort **	\(\Theta(n^2)\)	\(\Theta(n^2)\)	\(\Theta(n^2)\)	\(O(1)\)	✗	✓
Insertion Sort	\(\Theta(n)\)	\(\Theta(n^2)\)	\(\Theta(n^2)\)	\(O(1)\)	✓	✓
Merge Sort	\(\Theta(n \log n)\)	\(\Theta(n \log n)\)	\(\Theta(n \log n)\)	\(O(n)\)	✓	✗
Quick Sort	\(\Theta(n \log n)\)	\(\Theta(n \log n)\)	\(\Theta(n^2)\)	\(O(\log n)\)	✗	✓
Heap Sort	\(\Theta(n \log n)\)	\(\Theta(n \log n)\)	\(\Theta(n \log n)\)	\(O(1)\)	✗	✓
Counting Sort	\(\Theta(n+k)\)	\(\Theta(n+k)\)	\(\Theta(n+k)\)	\(O(n+k)\)	✓	✗
Radix Sort	\(\Theta(d(n+k))\)	\(\Theta(d(n+k))\)	\(\Theta(d(n+k))\)	\(O(n+k)\)	✓	✗
Bucket Sort ***	\(\Theta(n+k)\)	\(\Theta(n+k)\)	\(\Theta(n^2)\)	\(O(n+k)\)	✓	✗

GATE traps

1* Bubble Sort's \(\Theta(n)\) best case needs the early-exit optimization (stop when a pass makes no swaps) - the naive version is always \(\Theta(n^2)\), even on sorted input.

2** Selection Sort is not stable in its standard implementation, since swapping the found minimum into place can reorder equal keys - GATE often tests this exact contrast against Insertion Sort.

3*** Bucket Sort's stability depends entirely on the sort used inside each bucket - it's only stable if that internal sort is stable too.