constituents

• \(V\) a vector space
• \((u,v)\), an ordered pair of vectors in \(V\) (its not commutative!)

requirements

We define \(\langle u, v \rangle \in \mathbb{F}\) as the inner product of \((u,v)\) in that order!. It carries the following properties:

1. positivity: \(\langle v, v\rangle \geq 0, \forall v \in V\)
2. definiteness: \(\langle v, v\rangle = 0\) IFF \(v = 0\)
3. additivity in the first slot: \(\langle u+v, w\rangle = \langle u, w \rangle + \langle v, w \rangle\)
4. homogeneity in the first slot: \(\langle \lambda u, v \rangle = \lambda \langle u, v \rangle\)
5. conjugate symmetry: \(\langle u,v \rangle = \overline{\langle v,u \rangle}\)

additional information

Inner Product Space

An Inner Product Space is a vector space with a well-defined inner product. For instance, \(\mathbb{F}^{n}\) has the canonical inner product named Euclidean Inner Product (see below, a.k.a. dot product for reals). The existence of such a well-defined inner product makes \(\mathbb{F}^{n}\) an Inner Product Space.

insertion sort is an algorithm that solves the sorting problem.

constituents

a sequence of \(n\) numbers \(\{a_1, \dots a_{n}\}\), called keys

requirements

Insertion sort provides an ordered sequence \(\{a_1’, \dots a_{n}’\}\) s.t. \(a_1’ \leq \dots \leq a_{n}’\)

implementation

I don’t know why, but it seems like CLRS’ implementation is back-to font. But perhaps I’m just mistaken.

void insertion_sort(int length, int *A) {
    for (int j=1; j<length; j++) {
        int key = A[j];

        // insert the key correctly into the
        // sorted sequence, when appropriate
        int i = j-1;

        while (i > 0 && A[i] > key) { // if things before had
                                      // larger key
            // move them
            A[i+1] = A[i]; // move it down
            // move our current value down
            i -= 1;
        }

        // put our new element into the correct palace
        A[i+1] = key;
    }
}

additional information

proof

We use loop invariant method to show that our algorithm is correct. Our invariant is that the array \(A[0, \dots, j-1]\) is sorted \(\forall j 0 \dots L+1\).

an integer (\(\mathbb{Z}\)) is the natural numbers, zero, and negative numbers: …,-4,-3,-2,-1,0,1,2,2,3

representing integers

• what are the limitations of computational arithmetic
• how to perform efficient arithmetic
• how to encode data more compactly and efficiently

See also computer number system

The integrating factor \(\rho(x)\) is a value that helps undo the product rule. For which:

\begin{equation} log(\rho(x)) = \int P(x)dx \end{equation}

for some function \(P(x)\).

Separating the \(\rho(x)\) out, we have therefore:

\begin{equation} e^{\int P dx} = \rho(x) \end{equation}

Why is this helpful and undoes the product rule? This is because of a very interesting property of how \(\rho(x)\) behaves.