\documentclass[10pt]{article}
\usepackage{a4wide}
\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{amssymb}
%\usepackage{axodraw}
%\usepackage{epsfig}
%\addtolength{\topmargin}{-65pt}

% Stefan's abbreveations
\def\l{\langle}
\def\r{\rangle} 
\def\g{\gamma}
\def\bq{\begin{eqnarray*}}
\def\eq{\end{eqnarray*}}
\def\bs{\begin{small}}
\def\es{\end{small}}
\newcounter{exercise}
\setcounter{exercise}{1}

\begin{document}

\begin{center}
\section*{Problem sheet 1}
\end{center}

\subsection*{1. Lagrange interpolation formula}
Let $x_0$, $x_1$, ..., $x_n$ be $(n+1)$ pairwise distinct points and let there be given
$(n+1)$ arbitrary numbers $y_0$, $y_1$, ..., $y_n$. Further define 
the fundamental Lagrange polynomials by
\bq
l^n_i(x) & = & \frac{(x-x_0)...(x-x_{i-1})(x-x_{i+1})...(x-x_n)}
{(x_i-x_0)...(x_i-x_{i-1})(x_i-x_{i+1})...(x_i-x_n)}.
\eq
(a) Show that 
\bq
p_n(x) & = & \sum\limits_{i=0}^n y_i l^n_i(x)
\eq
is the unique polynomial $p_n(x)$ of degree $n$ such that
\bq
p_n(x_i) = y_i, & & \;\;\;\mbox{for}\;\; i=0,1,...,n.
\eq
Hint: You may first show that $l^n_i(x_j)$ equals 1 
if $i=j$ and zero if $i \neq j$.\\
\\
(b) Let $\Pi(x)=(x-x_0)(x-x_1)...(x-x_n)$ and 
show that
\bq
p_{(2n+1)}(x) & = & 
\sum\limits_{i=0}^n \left[ f(x_i) \left( 1 -\frac{\Pi''(x_i)}{\Pi'(x_i)} (x-x_i) \right) 
+ f'(x_i) (x-x_i) \right] \left( l_i^n(x) \right)^2
\eq
is the unique polynomial of degree $(2n+1)$ for which
\bq
& & p_{(2n+1)}(x_i) = f(x_i), \;\;\; p_{(2n+1)}'(x_i) = f'(x_i), \;\;\;\mbox{for}\;\; i=0,1,...,n.
\eq

\subsection*{2. Orthogonal polynomials}
Let $P_0(x)$, $P_1(x)$, ... be a set of orthonormal polynomials, e.g.
\bq
\int\limits_a^b dx \; w(x) P_i(x) P_j(x) & = & \delta_{ij},
\eq
let $x_1$, $x_2$, ..., $x_{n+1}$ be the zeros of $P_{n+1}(x)$ and $w_1$, $w_2$, ..., $w_{n+1}$
the corresponding Gaussian weights given by
\bq
w_j & = & \int\limits_a^b dx \; w(x) l^{n+1}_j(x).
\eq
Show that for $i,j<n+1$
\bq
\sum\limits_{k=1}^{n+1} w_k P_i(x_k) P_j(x_k) & = & \delta_{ij},
\eq
e.g. the $P_0$, $P_1$, ..., $P_n$ are orthonormal on the zeros of $P_{n+1}$.
This equation can be useful to check the accuracy with which the zeros and weights of $P_{n+1}$ have been determined numerically.

\subsection*{3. Monte Carlo integration}
The Monte Carlo estimate for the $d$-dimensional integral
\bq
\label{basicMCintegral}
I & = & \int dx f(x) = \int d^du f(u_1,...,u_d)
\eq
is given by
\bq
E & = & \frac{1}{N} \sum\limits_{n=1}^N f(x_n).
\eq
In order to discuss the error estimate for finite $N$, we first introduce
the variance $\sigma^2(f)$ of the function $f(x)$:
\bq
\sigma^2(f) & = & \int dx \left( f(x) - I \right)^2
\eq
Show that
\bq
\label{variance}
\int dx_1 ... \int dx_N \left(
\frac{1}{N} \sum\limits_{n=1}^N f(x_n) - I \right)^2
& = & \frac{\sigma^2(f)}{N},
\eq
e.g. the variance with which the Monte Carlo estimate differs from the true value is given by
$\sigma^2(f)/N$.\\
Hint: You may want to introduce an auxiliary
function $g(x)=f(x)-I$ and show $\int dx g(x) = 0$ first.

\subsection*{4. Pseudo-random numbers}
Pseudo-random numbers were in the early days often generated by a 
multiplicative linear congruential generator according to the prescription
\bq
s_{i} & = & ( a s_{i-1} + c ) \;\mbox{mod}\; m
\eq
Consider the simple multiplicative linear congruential
generator with $a=5$, $c=1$, $m=16$ and $s_0=1$. Write down the first twenty numbers
generated with this method. How long is the period? Write down the sequence
also in the binary representation and look at the lowest
order bits.

\subsection*{5. Gray code}
The Gray code representation for a number $n$ is a binary representation such that
the representations for $n$ and $n+1$
differ in only one bit.
The Gray code representation  can be obtained from the binary representation according to
\bq
\label{graycode}
... g_3 g_2 g_1 & = & ... b_3 b_2 b_1 \oplus ... b_4 b_3 b_2
\eq
where $\oplus$ deontes the bitwise exclusive-or operation (
$0 \oplus 0 = 1 \oplus 1 = 0$, $0 \oplus 1 = 1 \oplus 0 = 1$).
Find the Gray code representation for $n=0,1,...,7$.\\

\end{document}