\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\ord}{{\tt ord}}
\newcommand{\ah}{\alpha}
\newcommand{\ol}{\overline}
\newcommand{\bq}{\begin{quote}}
\newcommand{\eq}{\end{quote}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\lcm}{{\tt lcm}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\noi}{\noindent}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf FUND ALGORITHMS SAMPLE FINAL \\ SOLUTIONS}
\end{center}
\ben
\item (15) Describe the algorithm {\tt LCS-LENGTH($X$,$Y$)} that takes
as input two sequences $X=(x_1,\ldots,x_n)$ and $Y=(y_1,\ldots,y_m)$
and returns the length of the longest common subsequence. How long
does your algorithm take when both sequences have length $n$?
\So Set $L(i,j)$ to be the length of the LCS of $x_1\cdots x_i$ and
$y_1\cdots y_j$. Initial conditions $L(i,0)=L(0,j)=0$. The recursion
is $L(i,j)=1+L(i-1,j-1)$ if $x_i=y_j$, else $L(i,j)=\max[L(i-1,j),L(i,j-1)]$.
One needs do this in the right order. One way: For $i=1$ to $n$; For $j=1$
to $n$; If $x_i=y_j$ then $L(i,j)=1+L(i-1,j-1)$ else
$L(i,j)=\max[L(i-1,j),L(i,j-1)]$. Time is $O(n^2)$ as a double loop.
\item (5) In a Max-Heap what is the property of the
value at the root?
\So Its the biggest.
\item (5) For $n$ large which is faster: $\Theta(\lg^3n)$ or
$\Theta(\sqrt{n})$ algorithm?
\So $\Theta(\lg^3n)$. Any power of $\lg$ grows slower than any
power of $n$. {\tt Comment:} Some students missed that a fast
algorithm takes a small amount of time, so as $\sqrt{n}$ was
a faster growing function it was a slower algorithm.
\item (15) Given $A[1\cdots N]$ with $0\leq A[I]1$ with $d^2$ dividing $n$.
We call a positive integer $n$ {\tt NOTSQUAREFREE} if there
is an integer $d>1$ with $d^2$ dividing $n$.
\ben
\item (5) Argue {\tt NOTSQUAREFREE} is in {\tt NP}.
\So The oracle gives you $d$, you calculate $d^2$ (time $O(m^2)$, where
we let $m$ be the number of digits of $n$)
and then verify that $d^2$ divides $n$ (time $O(m^2)$).
\item (15) Argue {\tt SQUAREFREE} is in {\tt NP}. (Idea: Have the
oracle give the factorization of $n$.)
\So If $n$ is squarefree it is the product of distinct primes, at most
$\lg n$ of them. The oracle gives you the primes. You get (using AKS)
that each is a prime (time polylog for each so polylog total)
and that the product is $n$. [The checking that the numbers are primes
is needed for a subtle reason. Suppose the number $n=60$. A wily
oracle could give factors $6,10$ and if we didn't check for primality
we would incorrectly say it was squarefree!]
\een
\item (20)
In Depth-First Search each vertex $v$ gets a discovery time
$d[v]$ and a finishing time $f[v]$. Let $G$ be a graph and $v,w$
two distinct vertices for which $w\in Adj[v]$.
\ben
\item Assume $d[v]< d[w]$. Argue that $f[w] < f[v]$.
\So First $v$ is discovered. While doing {\tt DFS-VISIT[v]} $w$
is discovered (as $w\in Adj[v]$). Thus {\tt DFS-VISIT[w]}
is a subrouting of {\tt DFS-VISIT[v]} and so finishes earlier.
\item Now assume $G$ is a DAG and $d[w]< d[v]$. Argue that $f[w] < f[v]$.
\So As $w\in Adj[v]$ and $G$ is a DAG there is no directed path from
$w$ to $v$. Once $w$ is discovered while doing {\tt DFS-VISIT[w]} only
vertices ``downstream" from $w$ are encountered so $v$ is not discovered
so actually we have the stronger result that $f[w]