\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{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Problem Set 1\\ Due Thursday, Feb 5, in Recitation}
\end{center}
\begin{quote}
The world can be divided into those who love New York City and those
who don't. Those who love New York tend to be unusually lively people.
They have to be. Characteristically, they are ambitious, curious,
intellectually vigorous, culturally alive. Such people give New
York City institutions great dynamism and some eccentricity.
\\ James Hester 1924-2015, NYU President
\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,300,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 length 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 length $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 Bonus Question:}
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
\end{document}