Algorithm X.1: Linear interpolation

Input: two points $(x_1, y_1)$ and $(x_2, y_2)$.
Output: a linear polynomial $y = a_1 x + a_0$.

Given the points $(x_1, y_1)$ and $(x_2, y_2)$ with $x_1 \ne x_2$, describe an algorithm for evaluating an arbitrary point $x$ along the line interpolating (passing through) the two given points.

Algorithm X.2: Quadratic interpolation

Input: three points $(x_1, y_1)$, $(x_2, y_2)$ and $(x_3, y_3)$.
Output: a quadratic polynomial $y = a_2 x^2 + a_1 x + a_0$.

Given the points $(x_1, y_1)$, $(x_2, y_2)$ and $(x_3, y_3)$ with all three $x$-values different, describe an algorithm for evaluating an arbitrary point $x$ along the quadratic polynomial interpolating (passing through) the three given points.

You may or may not have been exposed to quadratic interpolation in secondary school; however, it is reasonably straight-forward: if the polynomial $ax^2 + bx + c$ passes through the three points, then all three of the equations:

$ax_1^2 + bx_1 + c = y_1$,
$ax_2^2 + bx_2 + c = y_2$,
$ax_3^2 + bx_3 + c = y_3$

must be true. This, you will note, is a system of three linear equations in three unknowns; for example, if the points were $(-1, 3)$, $(2, 0)$, $(4, 1)$, then these linear equations would be

$a\cdot (-1)^2 + b\cdot (-1) + c = 3$,
$a\cdot 2^2 + b\cdot 2 + c = 0$,
$a\cdot 4^2 + b\cdot 4 + c = 1$

or

$ a - b + c = 3$,
$ 4a + 2b + c = 0$,
$16a + 4b + c = 1$

You can solve this system of three linear equations in three unknowns for $a$, $b$ and $c$, and in this case, the interpolating polynomial is $0.3x^2 - 1.3x + 1.4$.