\documentclass[11pt,twoside]{article}

\usepackage{xspace}
\usepackage{amssymb}

\newcommand{\coursenumber}{CS 6104}
\newcommand{\coursetitle}{Symbolic Computation}
\renewcommand{\docdate}{\textup{May 28, 1996}}
\newcommand{\duedate}{June 3, 1996}
\newcommand{\doctitle}{\textit{Mathematica\/} \textup{Homework (Corrected)}}

\newcommand{\firstpageheading}[1]{
\vbox to 0pt{\vskip -#1
\hbox to \hsize{\sl \vbox to 8.5pt{}\doctitle\hfill\docdate\hfill \rm 1}\vss}
\nointerlineskip
\vspace*{-15pt}
}

\addtolength{\textwidth}{1.50in}
\addtolength{\textheight}{1.00in}
\addtolength{\evensidemargin}{-1.25in}
\addtolength{\oddsidemargin}{-0.25in}
\addtolength{\topmargin}{-.50in}

% Some new macros

\newcommand{\Grobner}{Gr\"obner\xspace}
\newcommand{\Mathematica}{\emph{Mathematica\/}\xspace}

\begin{document}

\pagestyle{myheadings}
\markboth{\hfill\docdate\hfill\doctitle}{\doctitle\hfill\docdate\hfill}

\firstpageheading{50pt}

\thispagestyle{empty}

\begin{center}
\Large\bf\doctitle\\
\smallskip
\Large\bf\coursenumber: \coursetitle\\
\end{center}

This assignment is worth 5\% of the course grade
and is due in class on \duedate.
Preferably, you should submit your solutions in \LaTeX\ 
by email to \verb,cs6104@ei.cs.vt.edu,.
Your \Mathematica packages can be submitted within the \LaTeX\ 
file or as separate files.
Alternately, you can submit an ascii solution by email.
As a last resort,
you can turn in a paper solution.
Explain your solution to each problem.

Help is available by email as well as during my office hours.
It is especially helpful to request clarification or hints by email
to \verb,cs6104@ei.cs.vt.edu,,
so I can send the response to everyone.

\paragraph{Problem 1.}
It is possible (even traditional)
to define the natural numbers $\Bbb{N}=\{0,1,2,\ldots\}$
using the successor function,
which we would think of as being ``plus 1.''
Using \Mathematica patterns,
you can define functions \verb,succ, and \verb,add,
to be successor and addition, respectively.
For example,
5 is just \verb,succ[succ[succ[succ[succ[0]]]]],.

Develop the appropriate \Mathematica patterns
so that \verb.add[x,0]. returns \verb,x,,
\verb.add[0,y]. returns \verb,y,,
and \verb.add[x,y].
returns the appropriately nested applications of \verb,succ,.
For example,
\begin{verbatim}
add[succ[succ[succ[0]]],succ[succ[0]]]
\end{verbatim}
should return our earlier representation of 5.

Now extend your construction to include negative integers
by adding a function \verb,neg,.
The canonical representation of $-2$
would then be \verb,neg[succ[succ[0]],.
Extend \verb,add, to work correctly on all integers.

All of your functions should be implemented purely
by means of pattern matching.
Submit your \Mathematica source along with your discussion
of what you did.

For an additional challenge,
implement integer multiplication
without using the builtin machine multiplication.
(This is definitely optional.)

\paragraph{Problem 2.}
We can define a monoid $M$ using a finite set of generators $\Sigma$
and a finite set of relations $R \subset \Sigma^*$.
Multiplication in $M$ is defined by string concatenation,
with the empty string $\lambda$ being the identity element.
The elements of $R$ are thought of as being ``equivalent'' to $\lambda$.
Suppose a string $w\in \Sigma^*$ can be written $w=uxv$,
where $x\in R$.
Then both $w$ and $uv$ represent the same element of $M$.

For example,
$\Sigma=\{a,b\}$ and $R=\{ ab, ba\}$
gives a monoid
in which there is one equivalence class for each integer $i$;
the $i$th equivalence class corresponds to strings in which
the number of $a$'s minus the number of $b$'s equals $i$.

Show how to coerce the \Mathematica \verb,Times, and \verb,Power,
functions to implement a monoid.
(This requirement is deliberately vague so you will experiment
to find a good way to do it.)
In particular,
reduction by the elements in $R$ should be done by pattern matching.
If we have
\begin{verbatim}
R = { a^2 b c^2, c d}
\end{verbatim}
then
\begin{verbatim}
a^4 b c^3 d 
\end{verbatim}
should reduce to
\begin{verbatim}
a^2
\end{verbatim}

Submit your \Mathematica source for representing a monoid.
Explain how to use your package to represent a particular monoid.

\paragraph{Problem 3. (Optional)}
A linear recurrence for the sequence $a_0,a_1,a_2,\ldots$
of the form
\begin{eqnarray*}
a_n & = & c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_p a_{n-p},
\end{eqnarray*}
where $p, c_1, c_2, \ldots, c_p$ are constants,
and with values $a_0,a_1,\ldots,a_{p-1}$ given explicitly,
can be solved by the method of characteristic roots\footnote{See
\emph{Applied Combinatorics} by Fred S.~Roberts or
your favorite combinatorics book.}.
The Fibonacci sequence can be defined by such a recurrence,
where $p=2$;
call such a recurrence \emph{quadratic.}
The result of applying the solution method is a polynomial in $n$
of degree $p$ that evaluates to $a_n$.

Develop a \Mathematica function \verb,solverecurrence,
that will take a quadratic recurrence and return a \emph{function}
that is the polynomial
that will evaluate to the values in the sequence specified by the recurrence.
You may assume that the characteristic polynomial has distinct roots,
if you wish.
For example,
after the assignment
\begin{verbatim}
fib = solverecurrence[a[n]==a[n-1]+a[n-2],a[0]==0,a[1]==1]
\end{verbatim}
the function \verb,fib, should evaluate
to the Fibonacci sequence $0,1,1,2,3,5,8,\ldots$
and should be a polynomial.
In particular,
\verb,fib[4], should return \verb,3,, and
\verb,fib[6], should return \verb,8.,
Also try the recurrence 
\begin{eqnarray*}
a_n & = & 5 a_{n-1} -6 a_{n-2}\\
a_0 & = & 1\\
a_1 & = & 1.
\end{eqnarray*}
What polynomial does your package obtain for this recurrence?

For a greater challenge,
extend \verb,solverecurrence, to arbitrary $p\geq1$.
If \Mathematica is unable to find a closed form
for the roots of the characteristic equation,
you may want to generate some reasonable warning.

Submit your \Mathematica source along with your discussion
of your solution.

\end{document}
