# Today I Learned

Some of the things I've learned every day since Oct 10, 2016

## 192: GIGO

Garbage In, Garbage Out.

To quote my numerical analysis professor John Strain, “If you have a really fancy method and give it garbage data, what you’ll get out is some really fancy garbage.”

## 191: Stability, Instability of Numerical Integration, Differentiation

Numerical integration methods such as use of the composite Simpson’s rule, composite trapezoidal rule, etc., are stable. That is, their round-off error as a result of being performed with machine arithmetic does not depend on the number of sub-intervals the integrating interval is split up into.

By contrast, numerical differentiation methods such as the 2-point, 3-point, and 5-point formulas are unstable, because these formulas involve division by the width of the step-size $h$ used. So at a certain point as $h \rightarrow 0$, round-off error overtakes the increased accuracy of a small step-size and the approximations actually start to get worse.

## 190: A Greedy Scheduling Algorithm

Suppose you have a ‘time’ interval $(a, b)$ with $a, b \in \mathbb{R}$, $a < b$, and that you have a set $E$ of ‘events’ $(s_1, t_1), (s_2, t_2), \dots, (s_n, t_n)$ with $a \leq s_i < t_i \leq b$ for all $i$. And suppose you want to schedule as many events from $E$ into $(a, b)$ as possible. That is, you want to select a subset of non-overlapping members of $E$ of maximum size. The following greedy algorithm does this in an optimal way (optimal solution, not necessarily runtime):

The total runtime is $O(n \log n)$.

## 189: Depth-First, Breadth-First, Uniform Cost, and A* Search Differ Only In Their Fringe

As graph exploration algorithms through search problem state spaces, depth-first, breadth-first, uniform cost, and A* search all have the following general form:

Credit: University of California, Berkeley

They differ only in the type of fringe used. Depth first uses a stack, breadth-first a queue, and both uniform cost and A* use a priority queue. (Uniform cost’s priority is based on the distance from the starting point to a given node, while that of A* is the sum of this distance and the node’s heuristic function.)

## 188: Lagrange Interpolation

Given a real function $f$, a set of $n+1$ points $x_0, \dots, x_n$, and the values $f(x_0), \dots, f(x_n)$ of $f$ at those points, the Lagrange polynomial uses this information to give an $n$-th degree polynomial $P$ which approximates $f$. The formula for $P$ is

$P = L_0 f(x_0) + \cdots + L_n f(x_n)$,

where

$L_k = (\prod_{i \neq k} (x - x_i))/(\prod_{j \neq k} (x_k - x_j))$.

Example: where $n = 1$ and we are given $x_0, x_1, f(x_0), f(x_1)$, the Lagrange polynomial approximating $f$ is

$P = \frac{x - x_1}{x_0 - x_1} f(x_0) + \frac{x - x_0}{x_1 - x_0} f(x_1)$.

Examination of the polynomial should make it clear that it is, in a way, the simplest polynomial where $P(x_k) = f(x_k)$ at each $x_k$.