\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Assignment 7}
\\ Due April 9 in Recitation.
\end{center}
\begin{quote}
We are surrounded by ideas and objects infinitely more ancient than
we imagine and yet at the same time everything is in motion.
-- Tielhard
\end{quote}
\ben
\item Determine an LCS of $10010101$ and $010110110$ using the algorithm studied.
\item Write all the parenthesizations of $ABCDE$.
Associate them in a natural way with (setting $n=5$) the
terms $P(i)P(n-i)$, $i=1,2,3,4$ given in the recursion for $P(n)$.
\item Let $x_1,\ldots,x_m$ be a sequence of distinct real numbers.
For $1\leq i\leq m$ let $INC[i]$ denote the length of the longest
increasing subsequence ending with $x_i$. Let $DEC[i]$ denote the
length of the longest decreasing subsequence ending with $x_i$.
{\tt Caution:} The subsequence must {\em use} $x_i$. For example,
$20,30,4,50, 10$. Now $INC[5]=2$ because of $4,10$ -- we do
{\em not} count $20,30,50$.
\ben
\item Find an efficient method for finding the values $INC[i]$,
$1\leq i\leq n$.
(You should find $INC[i]$ based on the previously found $INC[j]$,
$1\leq j< i$. Your algorithm should take time $O(i)$ for each
particular $i$ and thus $O(n^2)$ overall.)
\item Let $LIS$ denote the length of the longest increasing
subsequence of $x_1,\ldots,x_m$. Show how to find $LIS$ from
the values $INC[i]$.
Your algorithm, {\em starting with} the $INC[i]$,
should take time $O(n)$.
Similarly, let $DIS$ denote the length of the longest
decreasing subsequence of $x_1,\ldots,x_m$. Show how to find $DIS$ from
the values $DEC[i]$.
\item Suppose $ia$ or $DIS>b$. (Idea: Assume not
and look at the pairs $(INC[i],DEC[i])$.) Paul Erd\H{o}s was a great twentieth
century mathematician, whose work remains highly influential in many areas.
\een
\item Find an optimal parenthesization of a matrix-chain product whose sequence
of dimensions is $5,10,3,12,5,50,6$.
\item Some exercises in logarithms:
\ben
\item Write $\lg(4^n/\sqrt{n})$ in simplest form. What is its
asymptotic value.
\item Which is bigger, $5^{313340}$ or $7^{271251}$? Give reason.
(You can use a calculator.)
\item Simplify $n^2\lg(n^2)$ and $\lg^2(n^3)$.
\item Solve (for $x$) the equation $e^{-x^2/2}=\frac{1}{n}$.
\item Write $\log_n2^n$ and $\log_nn^2$ in simple form.
\item What is the relationship between $\lg n$ and $\log_3n$?
\item Assume $i< n$. How many times need $i$ be doubled before
it reaches (or exceeds) $n$?
\item Write $\lg[n^ne^{-n}\sqrt{2\pi n}]$ precisely as a sum in
simplest form. What is it asymptotic to as $n\ra \infty$? What
is interesting about the bracketed expression?
\een
\een
\begin{quote}
There is a theory which states that if ever anybody discovers exactly what
the Universe is for and why it is here, it will instantly disappear and be
replaced by something even more bizarre and inexplicable. There is another
theory which states that this has already happened.
\\ Douglas Adams
\end{quote}
\end{document}