Entropy and Information Gain
The entropy of a dataset \(S\) with classes \(C\) is:
\[H(S) = -\sum_{c \in C} p_c \log_2(p_c)\]
where \(p_c\) is the proportion of examples belonging to class \(c\). Entropy is maximised when classes are equally distributed and zero when all examples belong to a single class.
The information gain of splitting dataset \(S\) on attribute \(A\) is:
\[\text{IG}(S, A) = H(S) - \sum_{v \in \text{Values}(A)} \frac{|S_v|}{|S|} H(S_v)\]
Placeholder page for the moment.
Introduction
You type “translate lorem ipsum” into Google’s search bar and press Enter. Roughly 200 milliseconds later, ten blue links and a translation widget appear on your screen. In that fifth of a second, your keystrokes triggered a cascade of protocols, each handing off to the next like relay runners passing a baton across the planet. A name was resolved, a connection negotiated, encryption established, a request dispatched, routed through a dozen machines, answered, and rendered — all before you could blink twice.
Chaturanga: The Birth of Chess
An ancient Indian chess piece, reflecting the game’s origins as chaturanga
Divide-and-Conquer Recurrences
Many divide-and-conquer algorithms follow the same pattern: split the input into smaller pieces, solve each piece recursively, and combine the results. This shared structure means their running times satisfy recurrences of the same shape.
A divide-and-conquer recurrence has the form:
\[T(n) = aT\!\left(\left\lceil n/b \right\rceil\right) + \Theta(n^d)\]
where:
- \(a \geq 1\) is the number of subproblems (the branching factor),
- \(b > 1\) is the factor by which the input shrinks at each level,
- \(n^d\) is the cost of the divide and combine step.
Three forces compete: the branching factor \(a\) creates more work at each level, the shrinkage factor \(b\) makes each subproblem cheaper, and the non-recursive cost \(n^d\) sets the price of splitting and merging. The Master Theorem tells us which force wins.
Hermann Ebbinghaus and the Science of Memory
Hermann Ebbinghaus