\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}

