\documentclass[12pt]{article}

\usepackage{fullpage,amsmath,amsfonts,hyperref}

\begin{document}

\title{Algorithms and Data Structures}
\author{Summer Semester 2025}
\date{For discussion on Wednesday, June 11, 2025}
\maketitle

\begin{enumerate}

\item Give a proof of the index-relationships for an array-based
implementation of a binary tree:
\begin{enumerate}
\item $i(l) = 2 i(p) + 1$ if $l$ is the left child of $p$,
\item $i(r) = 2 i(p) + 2$ if $r$ is the left child of $p$,
\item $i(p) = \lfloor (i(c)-1)/2 \rfloor$ if $p$ is the parent of $c$.
\end{enumerate}

\item (GTG Exercise R-9.2) Suppose you label each position $p$ of a
binary tree $T$ with a key equal to its preorder rank. Under what
circumstances is $T$ a heap?

\item (GTG Exercise R-9.3) What does each remove min call return
within the following sequence of priority queue ADT methods:
\begin{flushleft}
\texttt{add(5,A)}, \texttt{add(4,B)}, \texttt{add(7,F)},
\texttt{add(1,D)}, \verb+remove_min()+, \texttt{add(3,J)},
\texttt{add(6,L)}, \verb+remove_min()+, \verb+remove_min()+,
\texttt{add(8,G)}, \verb+remove_min()+, \texttt{add(2,H)},
\verb+remove_min()+, \verb+remove_min()+?
\end{flushleft}


\item (GTG Exercise R-9.10) At which positions of a heap might the
third smallest key be stored?

\item (GTG Exercise R-9.11) At which positions of a heap might the
largest key be stored?

\item (GTG Exercise R-9.13) Illustrate the execution of the in-place
heap-sort algorithm on the following input sequence: (2, 5, 16, 4, 10,
23, 39, 18, 26, 15).

\item (GTG Exercise R-9.16) Is there a heap $H$ storing seven entries
with distinct keys such that a preorder traversal of $H$ yields the
entries of $H$ in increasing or decreasing order by key? How about an
inorder traversal? How about a postorder traversal? If so, give an
example; if not, say why.

\item (GTG Exercise R-9.18) Show that the sum
\[
  \sum_{i=1}^n \log i
\]
which appears in the analysis of heap-sort, is $\Omega(n \log n)$.

% \item (GTG Exercise C-9.27) Show how to implement the FIFO queue ADT
% using only a priority queue and one additional integer instance
% variable.

% \item (GTG Exercise C-9.28) Professor Idle suggests the following
% solution to the previous problem.  Whenever an item is inserted into
% the queue, it is assigned a key that is equal to the current size of
% the queue. Does such a strategy result in FIFO semantics? Prove that
% it is so or provide a counterexample.



\end{enumerate}
\end{document}
