\documentclass[11pt]{article}
%\usepackage{pstricks,pst-node}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}
%\newcommand{\edgee}[1]{\begin{math}\stackrel{#1}{\longrightarrow}\end{math}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\begin{document}
\setlength{\parskip}{.1 in}
\begin{center}
\LARGE
\textbf{CS 473: Algorithms, Fall 2016}
\\[0.5ex]
\textbf{HW 1 (due Tuesday, September 6th 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 = 7$.
\begin{itemize}
\item There is a number $\omega \in \mathbb{Z}_7$ such that all the powers
$\omega,\omega^2,\ldots,\omega^6$ are distinct (modulo $7$).
Find this $\omega$, and show that $\omega+\omega^2+\ldots+\omega^6 = 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 Using the matrix form of the DFT, produce the transform of the
sequence $(0,1,1,1,5,2)$ modulo $7$; that is, multiply this vector
by the matrix $M_6(\omega)$, for the value of $\omega$ you found
earlier. In the matrix multiplication, all calculations should be
performed modulo $7$.
\item 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 7.)
\item Now show how to multiply the polynomials $x^2 + x + 1$ and $x^3
+ 2x - 1$ using the DFT modulo $7$.
\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{itemize}
\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{itemize}
\item Describe an efficient algorithm that given two strings $A =
a_1a_2\ldots a_n$ and $B = b_1b_2\ldots b_m$ outputs the smallest
integer $k$ such that $A$ can be written as the concatenation of $k$
strings $A_1\cdot A_2 \cdots A_k$ (here $\cdot$ stands for string
concatenation) and likewise $B$ can be written as $B_1\cdot B_2
\cdots B_k$ with the condition that the string $A_i\cdot B_i$ is a
palindrome for $1 \le i \le k$. For example if $A = abac$ and $B =
caba$ then $k=1$ is possible by setting $A_1 = A$ and $B_1 = B$
since $A_1\cdot B_1 = A \cdot B$ is a palindrome. Another example is
$A = abc$ and $B = d$ in which case $k=4$ is achieved by writing $A = a
\cdot b \cdot c \cdot \varepsilon$ and $B = \varepsilon \cdot
\varepsilon \cdot \varepsilon \cdot d$. Here $\varepsilon$ is the
empty string which satisfies the property that for any string $C$,
$C\cdot \varepsilon = \varepsilon \cdot C = C$.
\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}