\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{1}
\newcommand{\ABGABEDATUM}{on 26. October~2018, 10:00, in the
respective TA's mailbox}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Problem \arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Problem set on

\smallskip
\noindent
\large
\textbf{Algorithms, Data Structures and Data Abstraction}\hfill WS 18/19 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Due} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Recurrences}{10 Points}

Solve the following recurrences.
Provide a proof for the correctness of your solution
(e.g., using induction).
\begin{enumerate}
  \item
    \[
       T(1) = 0; \quad T(n) = 
       T\Bigl(\left\lfloor \frac{n}{2}\right\rfloor\Bigr) +
                 T\Bigl(\left\lceil \frac{n}{2} \right\rceil\Bigr) + n, 
		 \text{ for } n > 1.
    \]
    You may assume that $n$ is a power of $2$.
  \item 
    \[
      S(1) = 1; \quad S(n) = \sum_{i=1}^{n-1} i \cdot S(i), 
        \text{ for } n > 1.
    \]
\end{enumerate}


\AUFGABE{The Arithmetic-Geometric-Mean Inequality}{10 Points}


Let $x_1, x_2, \dots, x_n \geq 0$. Prove the 
inequality
\[
P(n): x_1 x_2 \dots x_n
\leq\left(\frac{x_1 + \dots + x_n}{n}\right)^n,
\]
using the following steps:
\begin{enumerate}
  \item Argue that $P(2)$ holds.

     \emph{Hint}: $(x_1 - x_2)^2 \geq 0$.
  \item
     Show that if $P(n)$ holds, then so does $P(n-1)$.

     \emph{Hint}: Given $x_1, \dots, x_{n-1}$, you need to choose 
     $x_n$ so that the value on the right hand side does not change.

   \item Prove that $P(2)$ and $P(n)$ imply $P(2n)$.
   \item Argue that $P(n)$ holds for all $n \geq 1$.
\end{enumerate}

\AUFGABE{Elementary Algebraic Manipulations}{10 Points}

Find pairs of equivalent expressions and prove the
equivalences using simple algebraic manipulations.
Show the individual steps of each transformation,
and indicate the rules that you apply.
\[
 \log_a\Bigl(n^{\log_b a}\Bigr), \sqrt[b]{\frac{a^n}{a^m}},
 b^{n \log a}, \log_b n, a^{\frac{n-m}{b}}, n(\log a + \log b),
 \log(a^nb^n),a^{(\log b^n)}.
\]

\AUFGABE{The Inverse FFT (voluntary)}
{10 Extra Points}

\begin{enumerate}
\item Show with a proof technique of your choice that
for all $x \neq 1$ and for all $n \geq 0$, we have
\[
\sum_{i=0}^{n} x^i = \frac{x^{n+1}-1}{x-1}.
\]
\item Let $n+1$ be a power of $2$, and let
$\omega \in \mathbb{C}$ be a 
\emph{complex} primitive $(n+1)$th root of unity
(i.e., $\omega^{n+1} = 1$ and $\omega^k \neq 1$, for
$k=1, \dots, n$).
Let $p(x) = a_0 + a_1 x + \dots + a_{n} x^{n}$
be a polynomial of degree $n$.

In class, we saw how to compute the 
values $p(\omega^0),
p(\omega^1), \dots, p(\omega^{n})$ quickly.
Let $A = (a_{ij})$ be the $(n+1) \times (n+1)$ matrix
with $a_{ij} = \omega^{(i-1)(j-1)}$.

Show how to express the computation of
$p(\omega^0),
p(\omega^1), \dots, p(\omega^{n})$
as the multiplication of 
$A$ with a suitable vector, i.e., give a column vector
$v \in \mathbb{C}^{n+1}$ with
\[
\left(\begin{matrix} p(\omega^0) \\ p(\omega^1) \\ \vdots \\ p(\omega^{n}) 
\end{matrix} \right)= A\cdot v.
\]
\item
  Let $B = (b_{ij})$ be the $(n+1) \times (n+1)$ matrix with
  $b_{ij} = \frac{1}{n+1}\omega^{-(i-1)(j-1)}$.
  Show that $B \cdot A = I$, where $I$ 
  is the matrix that has $1$s on the diagonal and
  $0$s everywhere else (the \emph{identity matrix}). 
  In particular, we have
  $B \cdot A \cdot w = w$, for all $w \in \mathbb{C}^{n+1}$.

  \emph{Hint:} Use (a) and note that $\omega$
      is an $(n+1)$th root of unity.

\item Let now $p(x)$ be polynomial of degree $n$,
  so that we know only the values
  $p(\omega^0)$, $p(\omega^1), \dots, p(\omega^{n})$.
  Describe a method to find the coefficients of 
  $p(x)$ in 
  $O(n \log n)$ operations.

  \emph{Hint:} By (c), we must multiply $B$
    with a suitable column vector.
    Show that this corresponds to the evaluation of a
    suitable polynomial at the positions
    $\omega^{-0}, \omega^{-1}, \dots, \omega^{-n}$.
    Now proceed as in class in order to achieve this in
    $O(n \log n)$ operations.

 \item 
    Let $p(x)$ and $q(x)$ be two polynomials of degree $n$,
    given by their coefficients.
    Sketch a method to compute in 
    $O(n\log n)$ operations the product polynomial
    $r(x) = p(x) \cdot q(x)$
    in coefficient representation.

    (\emph{Careful}: The product polynomial has degree $2n$.)
\end{enumerate}
\end{description}
\end{document}
