constituents

Assume keys are distinct.

• node: elements in the tree
• key: each node has a key, which tags the node and is the key being sorted on
• root: the node with no parents
• leaves: the nodes with two nil children
• height: number of edges root to leaf (i.e. if there is a tree root-leaf directly, then the height is 1)

Every node has 2, possibly-null, children. Every node has a parent except for the root.

1. we first go identify some natural subproblems…
2. suppose you could solve the subproblems magically, can you solve the big problem?

Then go about thinking about the recurrence relation, etc.

Tips

• use some small examples by hand
• leverage existing algorithms
• use some analysis to guess what the structure of the solution is

constituents

a binary search tree

requirements

• every node is colored red or black
• root node is black
• NIL children are black node
• children of red nodes are black nodes
• for all nodes x, all parts from x to NIL have the same number of black nodes
• for all nodes, all paths from x to nil have the same number of black nodes

additional information

intuition

1. black nodes are balanced — “every path from root to nil would have the same black nodes”
2. red nodes are “spread out” so they don’t mess things up too much

Its weaker than perfect balance, and its not too weak to break things.

constituents

• samples \(x,z \in \mathcal{D}\)
• \(d\) input dimensions, \(p\) featured dimensions
• feature map: \(\phi: \mathbb{R}^{d} \to \mathbb{R}^{p}\)
• kernel: \(k\qty(x,z) = \langle\phi\qty(x), \phi\qty(z)\rangle\)

requirements

train

Compute \(k\qty(x^{(i)}, x^{(j)})\) for all \(i,j \in 1 … n\). Set \(\beta_{j} = 0\) for all \(j\). Iterate:

\begin{equation} \beta_{i} = \beta_{i} + \alpha \qty[y^{(i)} - \sum_{j=1}^{n} \beta_{j} k\qty(x^{(i)}, x^{(j)})] \end{equation}

test

Given \(x\), compute \(\theta^{T} \phi\qty(x)\) such that:

\begin{align} \theta^{T}\phi\qty(x) &= \sum_{i=1}^{n} \beta_{i} \phi\qty(x^{(i)})^{T} \phi\qty(x) \\ &= \sum_{i=1}^{n} \beta k\qty(x^{(i)}, x) \end{align}