\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\ah}{\alpha}
\newcommand{\noi}{\noindent}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\QU}{{\tt QUEUE}}
\newcommand{\PQU}{{\tt POPQUEUE}}
\newcommand{\AQU}{{\tt ADDTOQUEUE}}
\newcommand{\NIL}{{\tt NIL}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Problem Set 1\\
Due Thursday, Sept 12 in Recitation}
\end{center}
\begin{quote}
People wish to learn to swim and at the same time to keep one foot on the
ground. -- Marcel Proust
\end{quote}
\ben
\item Let $A$ is a max-heap with heapsize fifty million, being used
as a priority queue. Suppose {\tt HEAP-INCREASE-KEY(A,400,key)}
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 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 minimiml number of exchanges that can take place.
\item Consider a min-heap $H$ with heapsize $1023$. \footnote{Did you
recognize $1023$ as a special number? Its one less than $1024=2^{10}$.
The binary tree with that many nodes just fills out a row!}
Assume the elements of the
array are distinct. Let $x$ be the third smallest element in the array.
What are the possible positions for $x$. Let $y=H[700]$.
Can $y$ be the largest
element in the array? Can $y$ be the smallest element in the array?
{\tt Not to be submitted:}
Give all $i$ for which
it is possible that $y$ is the $i$-th smallest
element of the array.
\item Using the figures in the text as a model, illustrate the operation of
{\tt BUILD-MAX-HEAP} on the array $A=(5,3,17,10,84,19,6,22,9)$
\item The operation {\tt HEAP-DELETE(A,t)} deletes the item in node $t$
from heap $A$. Give an implementation of {\tt HEAP-DELETE} that runs in
$O(\lg n)$ time for an $n$-element max-heap.
\item Let $A$ be an array of length $127$ in which the values are
distinct and in increasing order. In the procedure
{\tt BUILD-MAX-HEAP(A)} precisely how many times will two elements
of the array be exchanged? Now suppose the values are distinct and
in decreasing order. Again,
in the procedure
{\tt BUILD-MAX-HEAP(A)} precisely how many times will two elements
of the array be exchanged?
\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}