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.
Ancient Origins: Ethiopia and the Legend of Kaldi
A coffee plantation in Yemen, drawn by Georg Wilhelm Baurenfeind during the Danish Arabia Expedition (1761–1767)
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
Backlinks (2)
1. Wiki /wiki/
Knowledge is a paradox. The more one understand, the more one realises the vastness of his ignorance.