\documentstyle[11pt]{article}
\begin{document}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{center}{\Large\bf FUNDAMENTAL ALGORITHMS FINAL EXAM}\end{center}
\begin{quote}
What is slight can still be great, if it is written in a natural, flowing and
easy style - and at the same time bears the mark of sound composition.
\\ -- letter to Wolfgang Mozart from his father, 1778
\end{quote}
\noindent {\tt Part I:} Do any eight of these problems. I.e., you
must {\bf omit} one problem.
\ben
\item (20) In Kruskal's MST algorithm there are functions $SIZE[v]$ and
$\pi[v]$ (parent). Let the graph have $V$ vertices.
\ben
\item (15) Show that (at {\em any} time in the running of the algorithm) if
$\pi[v]=u$ then $SIZE[u]\geq 2\cdot SIZE[v]$.
\item (5) Consider the loop
\\ WHILE $x\neq \pi[x]$
\\ \hsa $x\leftarrow \pi[x]$ (*Call this LoopStep*)
\\ Give an upper bound, in terms of $V$, on the number of times LoopStep
is applied in this WHILE loop. Reason please!
\een
\item (20) Use the Master Theorem to give, in Thetaland, the asymptotics of
these recursions:
\ben
\item (5) $T(n)= 6T(n/2) + n\sqrt{n}$
\item (5) $T(n)= 4T(n/2)+n^5$
\item (5) $T(n)= 4T(n/2)+7n^2+2n+1$
\item (5) $T(n)=3T(n/2) + 10n$.
\een
\item (20) Let $T$ be a BST. Suppose, in addition to the usual parent,
leftchild, rightchild, ROOT, we
have a function $desc[v]$. This gives, for each node $v$ in the
tree, the total number of descendents of $v$, including $v$ itself.
Now suppose we apply $INSERT[z]$ which adds new vertex $z$ to $T$.
\ben
\item (15)
{\em Update} the values $desc$ in an efficient manner.
({\tt Warning:} It is not sufficient to set $desc[z]=1$. Some
other vertices $v$ will have their value $desc[v]$ changed.
\item (5) Suppose also we have a parameter $SAM$ which is the sum of
all of the values $desc[v]$. Update $SAM$ in an efficient manner.
\een
\item (20) Let $G$ be a DAG [Directed Acyclic Graph]. Suppose $w\in Adj[v]$.
Let $d[x],f[x]$ denote, as usual, the discovery and finishing times for
vertex $x$ when running $DFS[G]$.
\ben
\item (10) Suppose $d[v] < d[w]$. Give {\em with logical argument} the order
in which $d[v],f[v],d[w],f[w]$ will appear.
\item (10) Suppose $d[w] < d[v]$. Give {\em with logical argument} the order
in which $d[v],f[v],d[w],f[w]$ will appear.
\een
\item (20) Here is a segment of {\tt COUNTINGSORT}. We assume
$A[1\cdots N]$ has all $0\leq A[I] \leq K$ and that
$B[1\cdots N]$ and $C[0\cdots K]$ are initially all zeroes.
We assume $K\geq 7$ to avoid trivialities below.
\\ FOR $I=1$ TO $N$; $C[A[I]]++$; ENDFOR (*end part one*)
\\ FOR $I=1$ TO $K$; $C[I]=C[I]+C[I-1]$; ENDFOR (*end part two*)
\\ FOR $I=N$ DOWN TO $1$
\\ \hsa $VALUE = A[I]$
\\ \hsa $PLACE = C[VALUE]$
\\ \hsa $B[PLACE]=VALUE$
\\ \hsa $C[VALUE] = C[VALUE]- 1$
\\ ENDFOR (*end part three*)
\ben
\item (5)
Describe $C[7]$ at the end of part one.
\item (5)
Describe $C[7]$ at the end of part two.
\item (10)
Describe $C[7]$ at the end of part three.
\een
The descriptions should be in terms of the values $A[J]$. They
could be something like: $C[7]$ is the sum of all
values $A[J]$ -- but of course that would be the wrong answer.
The descriptions must be in clear concise {\em words.}
\item (20)
List the parenthesizations of $ABCD$.
Let $P(n)$ denote the number of parenthesizations of $A_1\cdots A_n$.
Give a recursive formula for $P(n)$ and an argument for why it holds.
\item (20) Let $A[1\cdots N], B[1\cdots N], C[1\dots N]$ each be arrays in
increasing order. Assume, for convenience, that all values are distinct.
Give a procedure {\tt TRIDENT} which creates an
array $D[1\cdots (3N)]$ which has the $3N$ values in increasing order.
Pseudocode allowed. {\em Please} include comments describing what is
happening in your procedure.
\item (20) Let $A[1\cdots 127]$ be an array in no particular order. Apply
the following procedure:
\\ \hsa FOR I = 63 DOWN TO 8 (*Warning: Check endvalue!*)
\\ \hsb MAX-HEAPIFY(A,i)
\\ Let $OLDA[1\cdots 127]$ and $NEWA[1\cdots 127]$ below denote the
original and final values of $A$ respectively.
\ben
\item (10) Give the relationship between $NEWA[50]$ and the values in $OLDA$.
\item (5) Give the relationship between $NEWA[5]$ and the values in $OLDA$.
\item (5) Make a very small change in the procedure above to create a well
studied procedure. What is the name of that procedure?
\een
\item (20) Assume modulo $m$ multiplication of two numbers can be done
in one nanosecond. Let $s$ be a positive integer, at most
$10^{100}$, given in binary form. Show how $3^s$ modulo $m$ can
be computed in less than a microsecond.
\een
\noindent {\tt Part II:} Do any {\em three} of these problems. That is, you
must {\bf omit} one problem. Whichever you
choose you {\bf must} give substantial comments describing what
the algorithm is doing and what the various functions represent.
Pseudocode is fine. You must give a (brief!) explanation for
how long the program takes and {\em why} it takes that long.
\ben
\item (20) Describe Dijkstra's Algorithm.
The input is a directed
graph $G$ given by Adjacency List Representation, a source
vertex $s$, and a weight function $w[x,y]\geq 0$ defined for
all edges $(x,y)$ of the graph. The output will be $d[v]$,
the length of the shortest path from $s$ to $v$, and a
parent function $\pi[v]$.
\item (20) Let $G$ be a graph with $N$ vertices and $E$ edges. Let $s$
be a vertex of $G$. Give the algorithm $BFS[G,s]$ for Breadth
First Search.
\pagebreak
\item (20) Give an efficient sorting algorithm (your choice!).
The input is an array $A[1\cdots n]$ of values
and the output should be the same numbers in a sorted array
$B[1\cdots n]$. (You may make no assumption about the
nature of the data.)
\item (20) Give the LCS (longest common subsequence) algorithm. The
input will be
$A[1\cdots N], B[1\cdots N]$ sequences with all values either
zero or one. The output will be the length of the Longest
Common Subsequence. (You are {\em not} being asked to output the
LCS itself!) In this algorithm there will be an array
$c[i,j]$. What will the value $c[i,j]$ represent?
\een
\begin{quote}
No one has yet programmed a computer to be of two minds about a hard problem,
or to burst out laughing, but that may come. \\ -- Lewis Thomas
\end{quote}
\end{document}