  Most commonly used \emph{adaptive} algorithms for univariate real-valued
function approximation and global minimization lack theoretical guarantees. Our
new locally adaptive algorithms are guaranteed to provide answers that satisfy
a user-specified absolute error tolerance for a cone, $\mathcal{C}$, of
non-spiky input functions in the Sobolev space $W^{2,\infty}[a,b]$. Our
algorithms automatically determine where to sample the function---sampling more
densely where the second derivative is larger. The computational cost of our
algorithm for approximating a univariate function $f$ on a bounded interval
with $L^{\infty}$-error no greater than $\varepsilon$ is
$\mathcal{O}\Bigl(\sqrt{{\left\|f"\right\|}_{\frac12}/\varepsilon}\Bigr)$ as
$\varepsilon \to 0$. This is the same order as that of the best function
approximation algorithm for functions in $\mathcal{C}$. The computational cost
of our global minimization algorithm is of the same order and the cost can be
substantially less if $f$ significantly exceeds its minimum over much of the
domain. Our Guaranteed Automatic Integration Library (GAIL) contains these new
algorithms. We provide numerical experiments to illustrate their superior
performance.
