The algorithms in this appendix are small auxiliary routines used by the tree, bagging, and classification algorithms in Chapter 4.

\begin{algorithm}
\caption{Compute the average of a finite list of numbers in \(\Wset\).}
\begin{algorithmic}
\State \textbf{Input:} a non-empty list $\Wset = \qb{w_{1}, w_{2}, \ldots, w_{n}}$.
\State \textbf{Output:} the average.
\Procedure{Average}{$\Wset$}
    \State $\var{total} \gets 0$
    \State $\var{count} \gets 0$
    \For{$w \in \Wset$}
        \State $\var{total} \gets \var{total} + w$
        \State $\var{count} \gets \var{count} + 1$
    \EndFor
    \Return $\var{total} / \var{count}$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Count how often each value occurs in a finite list.}
\begin{algorithmic}
\State \textbf{Input:} a finite list $\Wset$.
\State \textbf{Output:} a map from values to counts.
\Procedure{Counts}{$\Wset$}
    \State $\var{counts} \gets \text{empty map with default value } 0$
    \For{$w \in \Wset$}
        \State $\var{counts}[w] \gets \var{counts}[w] + 1$
    \EndFor
    \Return $\var{counts}$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Count the number of elements in each set of a map.}
\begin{algorithmic}
\State \textbf{Input:} a map $d$ whose values are finite sets.
\State \textbf{Output:} a map from keys of $d$ to set sizes.
\Procedure{CountingMeasure}{$d$}
    \State $\var{counts} \gets \text{empty map}$
    \For{$k \in \pr{Keys}(d)$}
        \State $\var{counts}[k] \gets |d[k]|$
    \EndFor
    \Return $\var{counts}$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Normalize a finite map of nonnegative weights.}
\begin{algorithmic}
\State \textbf{Input:} a map $p$ with nonnegative values.
\State \textbf{Output:} a probability map.
\Procedure{NormalizeProbabilities}{$p$}
    \State $\var{total} \gets \sum_{k \in \pr{Keys}(p)} p[k]$
    \For{$k \in \pr{Keys}(p)$}
        \State $p[k] \gets p[k] / \var{total}$
    \EndFor
    \Return $p$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Compute uniform probabilities for the sets stored in a map.}
\begin{algorithmic}
\State \textbf{Input:} a map $d$ whose values are finite sets.
\State \textbf{Output:} a probability map.
\Procedure{UniformProbabilities}{$d$}
    \Return $\pr{NormalizeProbabilities}(\pr{CountingMeasure}(d))$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Compute the entropy of a probability mass function.}
\begin{algorithmic}
\State \textbf{Input:} a finite collection $p$ of probabilities.
\State \textbf{Output:} the entropy.
\Procedure{Entropy}{$p$}
    \State $\var{h} \gets 0$
    \For{$x \in p$}
        \If{$x > 0$}
            \State $\var{h} \gets \var{h} - x \log_2 x$
        \EndIf
    \EndFor
    \Return $\var{h}$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Collect all values that occur in a collection of sets.}
\begin{algorithmic}
\State \textbf{Input:} a finite collection $\Cset$ of sets.
\State \textbf{Output:} the union of the sets in $\Cset$.
\Procedure{UniqueValues}{$\Cset$}
    \State $\Uset \gets \varnothing$
    \For{$\Aset \in \Cset$}
        \State $\Uset \gets \Uset \cup \Aset$
    \EndFor
    \Return $\Uset$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Check whether a collection of sets is a partition of a state space.}
\begin{algorithmic}
\State \textbf{Input:} a finite collection $\Cset$ of sets and a state space $\Sset$.
\State \textbf{Output:} a Boolean.
\Procedure{?Partition}{$\Cset, \Sset$}
    \If{$\pr{UniqueValues}(\Cset) \neq \Sset$}
        \Return $\cn{False}$
    \EndIf
    \State $\var{seen} \gets \varnothing$
    \For{$\Aset \in \Cset$}
        \If{$\Aset \cap \var{seen} \neq \varnothing$}
            \Return $\cn{False}$
        \EndIf
        \State $\var{seen} \gets \var{seen} \cup \Aset$
    \EndFor
    \Return $\cn{True}$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Sample at most \(n\) distinct elements from a finite set.}
\begin{algorithmic}
\State \textbf{Input:} a finite set $\Sset$ and a number $n$.
\State \textbf{Output:} a set with at most $n$ randomly selected elements of $\Sset$.
\Procedure{SampleWithoutReplacement}{$\Sset,n$}
    \State $\Sset' \gets \varnothing$
    \While{$|\Sset'| < n \text{ and } \Sset \setminus \Sset' \neq \varnothing$}
        \State $s \gets \pr{RandomElement}(\Sset \setminus \Sset')$
        \State $\Sset' \gets \Sset' \cup \set{s}$
    \EndWhile
    \Return $\Sset'$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Sample \(n\) elements with replacement from a finite list.}
\begin{algorithmic}
\State \textbf{Input:} a finite list $\Sset$ and a number $n$.
\State \textbf{Output:} a list with $n$ randomly selected elements of $\Sset$.
\Procedure{SampleWithReplacement}{$\Sset,n$}
    \State $\Sset' \gets \qb{}$ \Comment{The empty list.}
    \While{$|\Sset'| < n$}
        \State $s \gets \pr{RandomElement}(\Sset)$
        \State $\Sset' \gets \Sset' + \qb{s}$ \Comment{Append $s$; repeats are kept.}
    \EndWhile
    \Return $\Sset'$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Compute the maximum value of a finite list of numbers.}
\begin{algorithmic}
\State \textbf{Input:} a non-empty finite list $(w_1, \ldots, w_K)$.
\State \textbf{Output:} the maximum value.
\Procedure{Max}{$(w_1, \ldots, w_K)$}
    \State $\var{max\_value} \gets w_1$
    \For{$2 \leq k \leq K$}
        \If{$w_k > \var{max\_value}$}
            \State $\var{max\_value} \gets w_k$
        \EndIf
    \EndFor
    \Return $\var{max\_value}$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Compute an index at which a finite list attains its maximum.}
\begin{algorithmic}
\State \textbf{Input:} a non-empty finite list $(w_1, \ldots, w_K)$.
\State \textbf{Output:} an index $k$ such that $w_k$ is maximal.
\Procedure{ArgMax}{$(w_1, \ldots, w_K)$}
    \State $\var{best\_value} \gets \pr{Max}((w_1, \ldots, w_K))$
    \State $\Mset \gets \varnothing$
    \For{$1 \leq k \leq K$}
        \If{$w_k = \var{best\_value}$}
            \State $\Mset \gets \Mset \cup \set{k}$
        \EndIf
    \EndFor
    \Return $\pr{RandomElement}(\Mset)$ \Comment{Break ties randomly.}
\EndProcedure
\end{algorithmic}
\end{algorithm}