\documentclass{article}
\usepackage{amsmath,amssymb,amsthm,latexsym,paralist}

\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem*{solution}{Solution}
\newtheorem*{resources}{Resources}

\newcommand{\name}[1]{\noindent\textbf{Name: #1}}
\newcommand{\honor}{\noindent On my honor, as an Aggie, I have neither
  given nor received any unauthorized aid on any portion of the
  academic work included in this assignment. Furthermore, I have
  disclosed all resources (people, books, web sites, etc.) that have
  been used to prepare this homework. \\[1ex]
 \textbf{Signature:} \underline{\hspace*{5cm}} }

 \newcommand{\checklist}{\noindent\textbf{Checklist:}
\begin{compactitem}[$\Box$] 
\item Did you add your name? 
\item Did you disclose all resources that you have used? \\
(This includes all people, books, websites, etc. that you have consulted)
\item Did you sign that you followed the Aggie honor code? 
\item Did you solve all problems? 
\item Did you submit (a) the pdf file of your homework?
\item Did you submit (b) a hardcopy of the pdf file in class? 
\end{compactitem}
}



\newcommand{\problemset}[1]{\begin{center}\textbf{Problem Set
      #1}\end{center}}
\newcommand{\duedate}[2]{\begin{quote}\textbf{Due dates:} Electronic
    submission of the pdf file of this homework is due on
    \textbf{#1} on ecampus, a signed paper copy of the pdf file is due
    on \textbf{#2} at the beginning of class. \end{quote} }

\newcommand{\N}{\mathbf{N}}
\newcommand{\R}{\mathbf{R}}
\newcommand{\Z}{\mathbf{Z}}


\begin{document}
\problemset{3}
\duedate{2/14/2019 before noon}{2/14/2019}
\name{ (put your name here)}
\begin{resources} (All people, books, articles, web pages, etc. that
  have been consulted when producing your answers to this homework)
\end{resources}
\honor

\newpage
Make sure that you describe all solutions in your own words. Read chapters 30 and 16 in our textbook. 

\begin{problem} 
\begin{compactenum}[(a)]
\item (10 points) Suppose that you are given a polynomial 
$$ A(x) = \sum_{k=0}^{n-1} a_k x^k.$$ 
The input to the FFT of length $n$ is given by an array containing the coefficients
$(a_0,\ldots, a_{n-1})$. Describe the output of the FFT in terms of
the polynomial $A(x)$. 

\item (15 points) Let $\omega$ be a primitive $n$th root of unity. 
The fast Fourier transform implements the multiplication with
  the matrix 
$$ F = (\omega^{ij})_{i,j\in [0..n-1]}.$$
Show that the inverse of the $F$ is given by 
$$ F^{-1} = \frac{1}{n}  (\omega^{-jk})_{j,k\in [0..n-1]}$$
[Hint: $x^n-1= (x-1)(x^{n-1}+\cdots + x + 1),$ so any power
$\omega^\ell\neq 1$  must be a root of $x^{n-1}+\cdots + x + 1$.  ]  
Thus, the inverse FFT, called IFFT, is nothing but the FFT using
$\omega^{-1}$ instead of $\omega$, and multiplying the result with
$1/n$. 
\item (10 points) Describe how to do a polynomial multiplication using the FFT and
  IFFT for polynomials $A(x)$ and $B(x)$ of degree $\le n-1$. Make
  sure that you describe the length of the FFT and IFFT needed for
  this task. 
\item (15 points) How can you modify the polynomial multiplication algorithm based
  on FFT and IFFT to do multiplication of long integers in base 10?
  Make sure that you take care of carries in a proper way. 
\end{compactenum}
\end{problem}
\begin{solution}
\end{solution}

\begin{problem} (20 points) You overhear a conversation where someone
  mentions that Morgenstern proved an $\Omega(n\log n)$ lower bound on
  the fast Fourier transform and someone else mentions that a group of
  MIT researchers found in 2012 a faster than fast Fouier transform
  that is $o(n\log n)$. These two comments seem to contradict each
  other. Do your research and find out what Morgenstern really proved
  and under what circumstances the MIT algorithm can improve on the
  FFT.
\end{problem}

\begin{problem} Solve the following two problems on matroids.
\begin{compactenum}
\item (10 points) Solve exercise 16.4-3 on page 443 of [CRLS]. 
\item (20 points)
Solve exercise 16.4-4 on page 443 of [CLRS]. 
\end{compactenum}
\end{problem}
\begin{solution}
\end{solution}


Discussions on ecampus are always encouraged, especially to clarify
concepts that were introduced in the lecture. However, discussions of
homework problems on ecampus should not contain spoilers. It is okay to
ask for clarifications concerning homework questions if needed. 
\medskip



\goodbreak
\checklist
\end{document}
