\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}
\noindent Prof. Spencer
\\ December 16, 2013
\begin{center}{\bf FUNDAMENTAL ALGORITHMS \\ FINAL EXAM A} \end{center}
\begin{quote}
Deep in the human consciousness is a pervasive need for a logical
universe that makes sense. But the real universe is always one step
beyond logic.
\\ -- from {\em Dune} by Frank Herbert
\end{quote}
\noindent Do all problems. Maximal Score: $190$
\\ No notes, book, calculators.
\\ {\tt Note:} (-) indicates an easier problem; (*) indicates a more challenging problem.
\ben
\item (10) When $A$ is a array with heapsize fifty million and
{\tt MAX-HEAPIFY(A,300)}
is called. What is the maximum number of exchanges that can take place.
What is the minimal number of exchanges that can take place.
\item (20) Consider {\tt COUNTING-SORT} on an array $A$
of length $n=1000$ with $k=2$. (That is, all values
are zero, one or two.) Let $C[0\cdots 2]$ be the
auxilliary array of {\tt COUNTING-SORT} and assume it
is all zeroes at the beginning.
Now {\em assume} that the array $A$ consists
of $253$ zeroes, $507$ ones and $240$ twos.
\ben
\item (5) Give the values of the array $C$ after the first
phase of {\tt COUNTING-SORT}. (Note: We do not count
setting $C$ to all zeroes as a phase.)
\item (5) Give the values of the array $C$ after the second
phase of {\tt COUNTING-SORT}.
\item (10) Give the values of the array $C$ at the end of
{\tt COUNTING-SORT}.
\een
You {\em must} give (short) reasons for your answers!
\item (20) Let $A[1\cdots M]$ be an array of distinct real
numbers. For $1\leq I\leq M$ let $INC[I]$ denote
the length of the longest increasing subsequence of
the $A[J]$ that ends with $A[I]$. ({\tt Caution:} The subsequence must {\em use} $A[i]$.
For example, suppose $A$ starts $20,30,4,50, 10$. Now $INC[5]=2$ because of $4,10$ --
we do {\em not} count $20,30,50$.) {\em Assume} that the values $INC[1],\ldots, INC[M-1]$
have {\em already} been determined. \ben
\item (10) Write a procedure (pseudocode is fine) that will
efficiently calculate $INC[M]$.
\item (5) How long, as an asymptotic function of $M$, will your
procedure take? (Quick reason, please!)
\item (5) Illustrate your procedure with $M=5$ and the array
$20,30,4,50, 10$ with the already given values $INC[1]=INC[3]=1$, $INC[2]=2$, $INC[4]=3$.
\een
\item (15) Let $T$ be a binary search tree with height $h$. Assume $ROOT[T]$ is
given and $LEFT[x]$, $RIGHT[x]$, $key[x]$ are given for each node $x$.
{\em Assume} all $key[x]$ are distinct.
Give an efficient algorithm $MUMBAI[w]$ that will return {\em true} if
$key[x]=w$ for some $x$ and otherwise will return {\em false}.
How long does your algorithm take as a function of $h$?
\item (20) Let $G$ be a connected graph on vertex $V$. Assume each edge $e=\{x,y\}$
has a distinct positive weight $w(e)$. Let $S\subset V$ with $S\neq \emptyset$, $S\neq V$.
Let $e=\{x,y\}$ be that edge with $x\in S$, $y\not\in S$ of minimal weight.
Prove (yes, {\em prove!}) that $e$ must belong to the Minimal Spanning Tree.
\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 (10) Assume $d[v]< d[w]$. Argue that $f[w] < f[v]$.
\item (10) Now assume $G$ is a DAG and $d[w]< d[v]$. Argue that $f[w] < f[v]$.
\een
\item (15) Call a positive integer $n$ {\tt PAPER} if it has a prime factor $p$
of the form $p=4k+1$. Call $n$ {\tt ROCK} if it is not {\tt PAPER}.
\ben
\item (5) Show that {\tt PAPER} is in {\bf NP}.
\item (10)(*) Show that {\tt ROCK} is in {\bf NP}.
\een
\item (20) Define $G$ (an undirected graph) on
vertices $\{0,1,\ldots,10000\}$ as follows: Each $x\neq 0,10000$
is adjacent to $x-1$ and $x+1$; $0$ is adjacent to $1$ and $10000$;
$10000$ is adjacent to $0$ and $9999$. (That is, $G$ is a cycle
on $0\cdots 10000$.) Assume an adjacency list
representation, where the lists are in numerical order.
\ben
\item (10) Describe the behavior of $BFS(G,0)$. What will the
Breadth-First tree be? A good picture would be helpful!
\item (10) Describe the behavior of $DFS(G)$. What will the Depth-First
forest look like? A good picture would be helpful!
\een
\item (15)(*) You want to sort five elements $u,v,w,x,y$ using
seven paired comparisons. {\em Assume} that your question is
``Is $u