\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 MIDTERM A}\end{center}
\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}
Maximum Score 140. Do all problems.
\ben
\item (20) Give an algorithm {\tt HORSE} with the following property.
The input is two arrays $A[1\cdots N]$, $B[1\cdots N]$, both
arrays in increasing order. The output is an array $C[1\cdots (2N)]$
which has all the values of the arrays $A,B$ and is in increasing
order. How long does your algorithm take. (Brief reason please!)
\item (20) Illustrate the operation of {\tt COUNTINGSORT} on the
array
\[ A = (2,1,2,1,0,0,0,1) \]
with $n=8$ and $k=2$.
Pictures and some well chosen words, please. (You do not need
every detailed step but you must make clear the main steps.)
\item (20) For the following algorithms let $T(N)$ denote the total number of times the
step after the
{\tt WHILE} step is reached.
For the first
algorithm give (five points) an {\em exact} formula for $T(N)$. For the second algorithm first
(ten points) give $T(N)$ as a precise sum. Then (five points)
Find $T(N)$ is the form $T(N)=\Theta(g(N))$ for a standard $g(N)$.
Reasons please!
\ben
\item
X=1
\\ WHILE X $<$ N
\\ \hsa do X=2*X
\item
FOR I=1 TO N
\\ \hsa X=1
\\ \hsa WHILE $X^2 \leq I$
\\ \hsb $X++$
\een
\item (10) In hashing, what are collisions? Describe one
method (your choice!) for dealing with them.
\item (20) Let $A$ is a max-heap with heapsize $N$. Describe a
program called here
{\tt BIGGULP(A,i,key)} that replaces $A[i]$ by
a value $key$ which is bigger than $A[i]$ and then
restores the heap property. How long does {\tt BIGGULP}
take? How long does {\tt BIGGULP} take in the special
case when $i=1$?
\item (15) You want to sort five elements $a,b,c,d,e$ using
seven paired comparisons. {\em Assume} that your question is
``Is $a