\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 Thursday, November 7 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. The centennial of his birth was observed with
a conference in his native Budapest last summer.
\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$?
The bracketed formula is a sterling formula. What is it called?
It is the asymptotics of a well known function! Which one?
\een
\een
\begin{quote}
She guessed at it all, what might live, moving purposefully or
drifting aimlessly, under the deep water around her, but she
didn't think too much about any of it. It was enough to be
aware of the million permutations possible around her, and
take comfort in knowing she would not, and really could not,
know much at all.
\\ Dave Eggers, The Circle
\end{quote}
\end{document}