\documentclass[11pt]{article}
%\usepackage{pstricks,pst-node}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}
\usepackage[dvipsnames]{xcolor}
\usepackage{accents}
%\newcommand{\edgee}[1]{\begin{math}\stackrel{#1}{\longrightarrow}\end{math}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\renewcommand{\r}[1]{ {\color{BrickRed} #1} }
\newcommand{\ub}[1]{\underbar{#1}}
\begin{document}
\setlength{\parskip}{.1 in}
\begin{center}
\LARGE
\textbf{CS 473: Algorithms, Spring 2018}
\\[0.5ex]
\textbf{HW 1 (due Wednesday, January 31th at 8pm)}
\end{center}
\noindent
This homework contains three problems. {\bf Read the instructions for
submitting homework on the course webpage}.
\noindent {\bf Collaboration Policy:} For this home work, each student
can work in a group with up to three members. Only one solution for
each group needs to be submitted. Follow the submission instructions
carefully.
\begin{enumerate}
%----------------------------------------------------------------------
\item We saw in class the FFT algorithm to compute convolutions using
complex numbers. However working with complex numbers is complex and
there are difficult numerical issues involved. Here we will see how
to use modular arithmetic to avoid these. Suppose we have two
integer valued vectors $\bar{a} = (a_0,a_1,\ldots,a_{n-1})$ and
$\bar{b} = (b_0,b_1,\ldots,b_{n-1})$ whose convolution we wish to
compute. We choose a sufficiently large prime number $p$ such that
we can multiply the two polynomials in the field $\mathbb{Z}_p =
\{0,1,2,\ldots,p-1\}$ where all arithmetic is done $\mod p$. This
ensure that the numbers never grow too large. The goal of this
problem is to illustrate this via a simple example which will also
make you work out some of the details of the FFT algorithm. We will
consider $p = 5$. {\bf Do \emph{NOT} submit solutions for the optional
problems for grading. They are here to help you understand DFT better.}
\begin{itemize}
\item There is a number $\omega \in \mathbb{Z}_5$ such that all the powers
$\omega,\omega^2,\ldots,\omega^4$ are distinct (modulo $5$).
Find this $\omega$, and show that $\omega+\omega^2+\ldots+\omega^4 = 0$.
(Interestingly, for any prime modulus there is such a number but finding
it efficiently for a given prime is not easy. If you are interested see \url{http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/cyclicFp.pdf} for six different
proofs of existence of such a number.)
\item [{[\textbf{Optional}]}] Using the matrix form of the DFT, produce the transform of the
sequence $(0,1,2,1)$ modulo $5$; that is, multiply this vector
by the matrix $M_4(\omega)$, for the value of $\omega$ you found
earlier. In the matrix multiplication, all calculations should be
performed modulo $5$.
\item [{[\textbf{Optional}]}] Write down the matrix necessary to perform the inverse DFT.
Show that multiplying by this matrix returns the original sequence.
(Again all arithmetic should be performed modulo 5.)
\item Now show how to multiply the polynomials $x^2 + x + 1$ and $x^3
+ 2x + 1$ using the DFT modulo $5$. {\em Hint:} You might find it helpful to
do the two optional questions above first, to get intuition on how to calculate the
DFT and the inverse DFT matrices.
\item For multiplying two polynomials $\bar{a} =
(a_0,a_1,\ldots,a_{n-1})$ and $\bar{b} = (b_0,b_1,\ldots,b_{n-1})$ with
integer valued coefficients how large should a prime $p$ be such that
computing the multiplication in $\mathbb{Z}_p$ yields the correct answer?
\end{itemize}
\item For any two sets $X$ and $Y$ of integers, the Minkowski sum
$X + Y$ is the set of all pairwise sums $\{x + y \mid x \in X, y \in
Y\}$.
\begin{enumerate}
\item Describe an analyze and algorithm to compute the number of elements
in $X + Y$ in $O(n^2 \log n)$ time where $|X| = |Y| = n$.
\item Describe and analyze an algorithm to compute the number of elements in
$X + Y$ in $O(n + M \log M)$ time, where $M$ is the largest absolute value of
any element of $X \cup Y$. {\em Hint:} Use FFT.
\end{enumerate}
\item A palindrome is any string that is exactly the same as its reversal, like \r{I}, or \r{DEED}, or
\r{RACECAR}, or \r{AMANAPLANACATACANALPANAMA}.
\begin{enumerate}
\item Describe and analyze an algorithm to find the length of the \textit{longest subsequence}
of a given string that is also a palindrome. For example, the longest palindrome
subsequence of \r{\ub{M}A\ub{H}D\ub{Y}NA\ub{M}ICP\ub{RO}G\ub{R}AMZLET\ub{M}ESHOW\ub{Y}OUT\ub{H}E\ub{M}} is \r{MHYMRORMYHM}, so given
that string as input, your algorithm should output the number 11.
\item Describe and analyze an algorithm to find the length of the \textit{shortest supersequence}
of a given string that is also a palindrome. For example, the shortest palindrome
supersequence of \r{TWENTYONE} is \r{\ub{TWENT}O\ub{YO}T\ub{NE}WT}, so given the string \r{TWENTYONE} as
input, your algorithm should output the number 13.
\end{enumerate}
\end{enumerate}
\vspace{1in}
{\bf The remaining problems are for self study. Do \emph{NOT} submit for grading.}
\begin{itemize}
\item See Jeff's notes for additional problems on FFT.
\item Fill out details of the longest palindromic subsequence problem
discussed briefly in lecture.
\item Consider the following problem. Given a string $A$ of length $n$ you
want to find the smallest $k$ such that $A$ can be written as
$A_1 \cdot A_2 \cdots A_k$ where each $A_i$ is a palindrome.
\item There are many nice problems on dynamic programming in the
two books (Dasgupta et al and Kleinberg-Tardos). Do several of them.
\item See Homework 1 from Spring 2016 taught by Jeff Erickson.
All the problems are on dynamic programming.
\url{https://courses.engr.illinois.edu/cs473/sp2016/hw/hw1.pdf}.
\end{itemize}
\end{document}