These notes concern the portion of Assignment 1 concerning pennant forests. We discuss solutions and common pitfalls for parts a and b. Please see the assignment text for the problem statement; it's omission from this page is deliberate.

Part a: show that $\sum_{i=0}^m |P_i| \in [2^m,2^{m+1})$

The size bounds follow immediately from the following structural fact: \begin{equation} \label{eq:structure_1} (\forall m, F, i) \quad height(P_i) \in \{ i-1, i \} \end{equation} and that a pennant with height $h$ contains exactly $2^h$ nodes. \eqref{eq:structure_1} follows from the size constraints on a pennant forest, i.e. \begin{equation} \label{eq:sizing} \forall i \quad i+1 \leq \left| \{ P_i \mid |P_i| \leq i \} \right| \leq i+2 \end{equation}

Alternate proofs

The proof can be done by induction on $m$; in my opinion, that proof reveals a lot less about the nature of a pennant forest.

Unconvincing Arguments

Many students asserted something about pennant forest structure, but these characterizations tended to be much less concise than \eqref{eq:structure_1}, and asserted without specific reference to the pennant forest properties (typically saying something like 'the properties imply the following structure'). Such demonstrations are unconvincing.

Part b: Give an algorithm to transform a heap into a pennant forest

The algorithm

The following structural property about heaps gives everything we need for the algorithm.

Let $H$ be a heap of height $h \geq 2$. Then

at least one subtree of the root is complete,
the complete subtrees has height at least $h-2$, and
the other subtree is a heap.

The algorithm is as follows: Take the tallest complete subtree along with the root to form $P_h$ and recurse on the remainder. (Base cases are heaps of height 0 or 1).

Correctness

It is straightforward to see that the priority condition is respected by collections of pennants output by this algorithm. Much less obvious is whether the sizing conditions (i.e. \eqref{eq:sizing}) hold. We will prove that \eqref{eq:sizing} holds by induction on the height of the input heap.

Fix a heap $H$ of height $h$. Let the pennant subtracted from $H$ before the recursive call be called the pivot and denoted $P$. Let $F$ denote the result of the recursive call.

We can assume (by an appropriately formulated inductive hypothesis) that $F$ is forest on $h$ pennants. It must still be argued that merging $P$ with $F$ is a pennant forest (i.e. that no properties of $F$ were disturbed, and the new constraint, applying to pennants of height $h$, is respected by in the merge.

Note that $height(P)$ is either $h$ or $h-1$. If $height(P) = h$, there is nothing to prove; if $height(P) = h-1$, we must show (at least!) that there are not three pennants of height $h-1$ in $F \cup P$. The following structural fact will suffice:

Let $F = \{P_i\}_{i=0}^m$ be a pennant forest. Then $height(P_{m-1}) < m$.

Parts c-f

The rest of the assignment was generally well done. Some students oversimplified the task of generating a heap from a pennant forest or vice-versa by assuming regularity of the pennant forest (i.e. that $|P_i| = 2^i$) or that the heap was a complete binary tree.

CSC 265 Fall 2013