\documentclass[12pt]{exam}
\usepackage{amsmath}
\usepackage[left=1in, right=1in, top=1in, bottom=1in]{geometry}
\usepackage{graphicx}
\newcommand\Cnought{C$_0$}
\newcommand\modulo{\ \texttt{\%}\ }
\newcommand\lshift{\ \texttt{<<}\ }
\newcommand\rshift{\ \texttt{>>}\ }
\newcommand\cgeq{\ \texttt{>=}\ }
\newcommand{\answerbox}[1]{
\begin{framed}
\hspace{5.65in}
\vspace{#1}
\end{framed}}
\pagestyle{head}
\headrule \header{\textbf{15-122 Assignment 6}}{}{\textbf{Page
\thepage\ of \numpages}}
\pointsinmargin \printanswers
\setlength\answerlinelength{2in} \setlength\answerskip{0.3in}
\begin{document}
\addpoints
\begin{center}
\textbf{\large{15-122 : Principles of Imperative Computation
\\ \vspace{0.2in} Summer 1 2012
\\ \vspace{0.2in} Assignment 6
}}
\vspace{0.2in}
(\large{Theory Part})
\vspace{0.2in}
\large{Due: Monday, June 18, 2012 in class}
\end{center}
\vspace{0.5in}
\hbox to \textwidth{Name:\enspace\hrulefill}
\vspace{0.2in}
\hbox to \textwidth{Andrew ID:\enspace\hrulefill}
\vspace{0.2in}
\hbox to \textwidth{Recitation:\enspace\hrulefill}
\vspace{0.5in}
\noindent The written portion of this week’s homework will give you some practice
working with binary search and AVL trees.
You can either type up your solutions or write them
\textit{neatly} by hand, and you should submit your work in class on the
due date just before lecture begins. Please remember to \textit{staple}
your written homework before submission.
\vspace{0.2in}
\begin{center}
\gradetable[v][questions]
\end{center}
\newpage
\begin{questions}
\pagebreak
\question{\textbf{Treaps}}
Famous Fred Hacker is a huge fan of both binary search trees and heaps.
Given an ordered sequence of $a_1 <
a_2 < ... < a_n$, there are many different binary search trees that
can be produced out of them. Now, suppose we introduce an additional
requirement on the BST: it
has to satisfy the min-heap order property, producing a treap.
More precisely, we assign a priority $p_i$ to each node $a_i$ and
insist that the tree:
\begin{itemize}
\item is a BST with respect to the key values $a_i$
\item has the min-heap order property with respect to the priorities $p_i$
\end{itemize}
\begin{parts}
\part[3] Draw a treap over elements $a < b < c < d$ if we assign
priorities 4,1,2,3 to $a,b,c,d$ respectively?
\begin{solution}
\vspace{2.5in}
\end{solution}
\part[3] What treap do we get if we assign priorities 3,4,1,2 to $a,b,c,d$ respectively?
\begin{solution}
\vspace{2.5in}
\end{solution}
\end{parts}
\newpage
\question{\textbf{Binary Search Trees}}
\begin{parts}
\part[4] Famous Fred Hacker enjoys climbing trees, but he is afraid to do so if
the tree has height greater than 0. Recall that the height of a binary tree is
the maximum number of nodes (inclusive) in the path from the root to a leaf.
For example, a binary tree of just one node has height 1. Write a recursive
function
\[
\texttt{int bst\_height(bst B)} \\
\]
that returns the height of a binary search tree. This function itself
should not be recursive, but you will need to write a helper function that
\emph{is} recursive. See the BST code developed in lecture for examples of
wrapper functions and recursive helper functions.
\begin{solution}
\vspace{6in}
\end{solution}
\newpage
\end{parts}
%
%\newpage
\question{\textbf{AVL Trees}}
\begin{parts}
\part[4] Famous Fred Hacker also likes mudkips.
Draw the AVL tree that results after successively inserting the following keys
in the order shown
\begin{verbatim}
7 12 10 16 4 2
\end{verbatim}
into an initially empty tree, maintaining and restoring the invariants of a BST
and the additional balance invariant required for an AVL tree after every
insert. Your answer should show the tree after each key is successfully
inserted.
\begin{solution}
\vspace{7in}
\end{solution}
\part
Famous Fred Hacker has a propensity for coming up with ingenious algorithms,
but he has a poor sense of balance. One day, he was walking across the street
and tripped. We want to show that the height of an AVL tree storing $n$ keys is
$O(\log n)$. For this purpose we count the minimum number of nodes $n$ in an
AVL tree of height $h$.
\begin{subparts}
\subpart[3] Fill in the table below:
\begin{center}
\begin{tabular}{|c|c|}
\hline \hspace{2mm} h \hspace{2mm} & \hspace{2mm} n \hspace{2mm} \\[5pt]
\hline 0 & 1 \\[5pt]
\hline 1 & 2 \\[5pt]
\hline 2 & \\ [5pt]
\hline 3 & \\ [5pt]
\hline 4 & \\ [5pt]
\hline
\end{tabular}
\end{center}
\vspace{0.1in}
\subpart[3] Recall that the Fibonacci numbers $F$ are defined by
$$
F(n) = F(n-1) + F(n-2)
$$
$$
F(0) = 0, F(1) = 1
$$
How is the minimum number of nodes $n = T(h)$ in an AVL tree of height $h$
related to the Fibonacci numbers?
\begin{solution}
\vspace{0.2in}
$T(h) = $
\vspace{3.2in}
\end{solution}
\end{subparts}
\end{parts}
\end{questions}
\end{document}