\documentclass[12pt]{exam}
\newcommand{\hwnumber}{6}
\newcommand{\hwname}{Huffman}

%%% begin hw-packages-and-macros.tex
\usepackage{amsmath}
\usepackage[left=1in, right=1in, top=1in, bottom=1in]{geometry}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{tikz}
\usetikzlibrary{shapes}
\usepackage{fancybox}
\usepackage{color}
\usepackage[all]{xy}
\usepackage{wrapfig}
\usepackage{fancyvrb}
\usepackage[T1]{fontenc}
\usepackage{listings}
\usepackage{hyperref}

\newcommand{\fillinlistings}{
    \lstset{ %
    language=C, numbers=left, numberstyle=\footnotesize, stepnumber=1,
    numbersep=4pt, showspaces=false, showstringspaces=false, tabsize=4,
    breaklines=true, breakatwhitespace=false,
    basicstyle=\normalsize\fontfamily{fvm}\selectfont, columns=flexible,
    mathescape=true, escapeinside={(*}{*)},
    morekeywords={alloc, allocarray, assert},
    otherkeywords={@requires, @ensures, @loop_invariant, @assert}
    }
}
\newcommand{\normallistings}{
    \lstset{ %
    language=C, numbers=left, numberstyle=\footnotesize, stepnumber=1,
    numbersep=4pt, showspaces=false, showstringspaces=false, tabsize=4,
    breaklines=true, breakatwhitespace=false,
    basicstyle=\footnotesize\fontfamily{fvm}\selectfont, columns=flexible,
    mathescape=true, escapeinside={(*}{*)},
    morekeywords={alloc, allocarray, assert},
    otherkeywords={@requires, @ensures, @loop_invariant, @assert}
    }
}

\newcommand{\semester}{Spring 2013}

\newcommand{\Cnought}{C$0$}
\newcommand{\modulo}{\ \texttt{\%}\ }
\renewcommand{\lshift}{\ \texttt{<<}\ }
\renewcommand{\rshift}{\ \texttt{>>}\ }
\newcommand{\cgeq}{\ \texttt{>=}\ }
\newtheorem{task}{Task}
\newtheorem{ectask}{Extra Credit Task}
\newtheorem{exercise}{Exercise}

\newcommand{\answerbox}[1]{
\begin{framed}
\hspace{5.65in}
\vspace{#1}
\end{framed}}

\pagestyle{head}

\headrule \header{\textbf{15-122 Homework \hwnumber}}{}{\textbf{Page
\thepage\ of \numpages}}

\pointsinmargin \printanswers

\setlength\answerlinelength{2in} \setlength\answerskip{0.3in}
%%% end hw-packages-and-macros.tex

\begin{document}
\addpoints
\begin{center}
\textbf{\large{15-122 : Principles of Imperative Computation, \semester
\\  \vspace{0.2in} Homework~\hwnumber~Theory [UPDATE 1]
}}

 \vspace{0.2in}

 \large{Due: Thursday, April 4, 2013, at the {\bf beginning} of lecture}
\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 heaps, priority queues, BSTs, and AVL trees,
as well as begin our transition to full C. You can either type
up your solutions or write them \textit{neatly} by hand in the spaces
provided. You should submit your work in class on the due date just
before lecture or recitation begins. Please remember to
\textit{staple} your written homework before submission.
\vspace{0.2in}

\begin{center}
\gradetable[v][questions]
\end{center}

\vspace{0.2in}
\begin{center}
  \Large{You {\it must} use this printout, include this cover sheet,

    and staple the whole thing together before turning it in.
  
    Either type up the assignment using
    \href{http://www.cs.cmu.edu/~rjsimmon/15122-s13/hw/15122-theory6.tex}{15122-theory6.tex},

    or print this PDF and write your answers \textit{neatly} by
    hand.}
\end{center}


\newpage
\begin{questions}





\question{\textbf{Heaps.}}

We represent heaps, conceptually, as trees. For example, consider the min-heap
below.\footnote{Diagram courtesy of \href{http://hamilton.herokuapp.com}{Hamilton (http://hamilton.herokuapp.com)}}

\begin{center}
\includegraphics[scale=0.55]{minheap.png}
\end{center}

\begin{parts}

\part[2] Assume a heap is stored in an array as discussed in class where the root
is stored at index 1.
Using the above min-heap, at what index is the element 
with value 32 stored? At what index is its parent stored?
At what indices are its left and right children stored?

\begin{solution}
\begin{verbatim}
The value 32 is stored at index ___________.

The parent of value 32 is stored at index ____________.

The left child of value 32 is stored at index ____________.

The right child of value 32 is stored at index ____________.
\end{verbatim}
\end{solution}

\part[1] 
Suppose we have a non-empty min-heap of integers of size n and we wish to find the maximum integer in the
heap. Describe precisely where the maximum must be in the min-heap. (You should
be able to answer this question with one short sentence.)

\begin{solution}
\vspace{0.7in}
\end{solution}

\newpage
\part[1]
Using the following C0 definition for a heap of integers (position 0 in the array is not used):

\begin{verbatim}

struct heap_header {
  int limit;   // size of the array of integers
  int next;    // next available array position for an integer
  int[] value;
};
typedef struct heap_header* heap;

\end{verbatim}

Write a C0 function \verb"find_max" that takes a non-empty min-heap and returns the maximum value. Your code should examine only those cells that could possibly hold the maximum.

\begin{solution}
\begin{verbatim}
int find_max(heap H) 
//@requires is_heap(H);
//@requires H->next > 1;
{








}
\end{verbatim}
\end{solution}

\part[1]
What is the worst-case runtime complexity in big-$O$ notation of your \verb"find_max"
function on a non-empty min-heap of $n$ elements from the previous problem?

\begin{solution}
\vspace{0.5in}
\end{solution}

\end{parts}




























\newpage
\question{\textbf{Heaps and BSTs.}}

 Though heaps and binary search trees (BSTs) are very different in
 terms of their invariants and uses, they are both conceptually
 represented as trees. This question asks about three invariants of
 trees: the BST ordering invariant, the heap shape invariant, and the
 heap ordering invariant (for min-heaps, where higher-priority keys
 are lower integer values). For the first part of this question, we
 assume that each element has a single C0 \verb'int' that is used as
 both the BST key and the heap priority.

\begin{parts}

\part[1] Draw a tree with five elements that is a BST and
satisfies the heap shape invariant.

\begin{solution}
\vspace{2.7in}
\end{solution}

\part[1] Draw a tree with at least four elements that is a BST and
satisfies the (min-)heap ordering invariant.

\begin{solution}
\vspace{2.7in}
\end{solution}

\newpage
\part[1] Why is it not a good idea to have a data structure that enforces
both the (min-)heap ordering invariant and the BST ordering invariant? 
(Be brief!)

\begin{solution}
\vspace{.7in}
\end{solution}

\part[3] Maintaining the BST ordering invariant and the heap invariant
on the {\it same} set of values may not be a good idea, but it can be
useful to have a tree structure where each node has two separate
values -- a key used for the BST ordering invariant and a priority
used for the heap ordering invariant. Such trees are called
\textit{treaps}; we will use \verb'string's as keys and \verb'int's as
priorities in this question.

The treap below satisfies the BST ordering invariant, but violates the
heap ordering invariant because of the relationship between the
``e''\!/9 node and its parent. In a heap, we restore the heap shape
invariant using swaps. But in a treap, such a swap would violate the
BST ordering invariant. However, by using the same local rotations we
learned about for AVL trees, it is possible to restore the heap
ordering invariant while preserving the BST ordering invariant.

The heap ordering invariant for the tree below can be restored with
two tree rotations. %After one rotation, the heap ordering invariant
%will again hold except at one place. After a second rotation, the heap
%ordering invariant will be fully restored.
Draw the tree that results from each rotation. You should be drawing two trees.

\begin{solution}

\includegraphics[scale=0.5]{treap1.png}
\vspace{1.7in}
\end{solution}

\end{parts}

















\newpage
\question{\textbf{Priority Queues.}}

\begin{parts}

In a priority queue, each element has a priority value which is represented as 
an integer. As in the previous question, the lower the integer, the higher
the priority. When we call \verb"pq_delmin", we remove the element with
the highest priority.

\part Consider the following ways that we can implement a priority queue.
Using big-$O$ notation, what is the worst-case runtime complexity for each 
implementation to perform \verb"pq_insert" and \verb"pq_delmin" on a priority queue with $n$ elements?

\begin{subparts}

\subpart[1]
Using an \emph{unsorted} array.

\begin{solution}
\vspace{0.1in}

\verb"pq_insert":
\vspace{0.25in}

\verb"pq_delmin":
\vspace{0.1in}
\end{solution}

\subpart[1]
Using a \emph{sorted} array, where the elements are stored from lowest to highest priority.

\begin{solution}
\vspace{0.1in}

\verb"pq_insert":
\vspace{0.25in}

\verb"pq_delmin":
\vspace{0.1in}
\end{solution}

\subpart[1]
Using a heap.

\begin{solution}
\vspace{0.1in}

\verb"pq_insert":
\vspace{0.25in}

\verb"pq_delmin":
\vspace{0.1in}
\end{solution}

\end{subparts}

\part[1] Which implementation in (a) is preferable if the number of 
\verb"pq_insert" and \verb"pq_delmin" operations are relatively balanced?
Explain in one sentence.

\begin{solution}
\vspace{1.0in}
\end{solution}

\newpage
\part[1] 

Under what specific condition does a priority queue behave like a FIFO
queue if it is implemented using a heap? {\it (Warning: if you words
  like ``higher,'' ``lower,'' ``increasing,'' or ``decreasing'' in
  your answer, be clear whether you are talking about priority or
  integer value.)}
\begin{solution}
\vspace{2in}
\end{solution}

\part[1] Under what specific condition does a priority queue behave like a LIFO stack if it is implemented using a heap? 
\begin{solution}
\vspace{2in}
\end{solution}

\end{parts}


























\newpage
\question{\textbf{AVL Trees.}}

\begin{parts}

\part[4] Draw the AVL trees that result after successively
inserting the following keys into an initially empty tree, in the
order shown:

\vspace{0.25in}
\begin{center}
\texttt{98, 88, 54, 67, 23, 72, 39}
\end{center}
\vspace{0.25in}

Show the tree after each insertion and subsequent
re-balancing (if any): the tree after the first element, \verb'98',
is inserted into an empty tree, then the tree after \verb'88' is
inserted into the first tree, and so on for a total of seven
trees. Make it clear what order the trees are in.

Be sure to maintain and restore the BST invariants and the additional
balance invariant required for an AVL tree after each insert.

\begin{solution} 
\vspace{5.7in}
\end{solution}

\part
Recall our definition for the height $h$ of a tree:
\begin{quote}
\textbf{The height of a tree is the maximum length of a path from the root to a leaf. So the empty tree has height 0, the tree with one node has height 1, and a balanced tree with three nodes has height 2.}
\end{quote}
The minimum number of nodes $n$ in a valid AVL tree is related to its
height. The goal of this question is to quantify this relationship.

\begin{subparts}
\subpart[2] Fill in the table below relating the variables $h$ and $n$:
\vspace{0.25in}

\begin{center}
\begin{tabular}{|c|c|}
 \hline   \hspace{2mm} $h$  \hspace{2mm} & \hspace{2mm}  $n$ \hspace{2mm} \\[5pt]
 \hline 0 & 0  \\[5pt]
 \hline 1 & 1  \\[5pt]
 \hline 2 & 2  \\[5pt]
 \hline 3 &    \\[5pt]
 \hline 4 &    \\[5pt]
 \hline 5 &    \\[5pt]
 \hline
\end{tabular}
\end{center}

\vspace{0.25in}
\subpart[2] Recall that the $x$th Fibonacci number $F(x)$ is defined by:
\begin{align*}
F(0) &= 0 \\
F(1) &= 1 \\
F(x) &= F(x-1) + F(x-2), \qquad x > 1
\end{align*}
Using the table in part (i), give an expression for $T(h)$, where
$T(h)=n$. \ You may find it useful to use $F(n)$ in your answer, but
your answer \underline{does not} need to be a closed form expression.

\begin{solution}
\vspace{1in}
\end{solution}

\end{subparts}
\end{parts}

















\newpage
\question{\textbf{Pass by reference}}

\begin{center}
We now begin our transition in 15-122 to full C!
\end{center}

At various points in our C0 programming experience we had to use
somewhat awkward workarounds to deal with {\it functions that need to
return more than one value}. The address-of operator (\verb"&") in C gives us a
new way of dealing with this issue.

\begin{parts}

\part[2]
Sometimes, a function needs to be able to both 1) signal whether it
can return a result, and 2) return that result if it is able to. One
such function that we've seen is \verb'peg_solve'. When a solution is
found, \verb'peg_solve' returns \verb'1' and modifies the
originally-empty stack passed in with the winning moves, and when no
solution is found \verb'peg_solve' simply returns the minimum number
of pegs seen. Parsing also fits this pattern. Consider the
following code:

\vspace{0.1in}
\begin{verbatim}
bool my_int_parser(char *s, int *i);  // Returns true iff parse succeeds

void parseit(char *s) {
  REQUIRES(s != NULL);
  int *i = xmalloc(sizeof(int));
  if (my_int_parser(s, i))
    printf("Success: %d.\n", *i); 
  else
    printf("Failure.\n");
  free(i);
  return;
}
\end{verbatim}
\vspace{0.1in}

Using the address-of operator, rewrite the body of the \verb'parseit'
function so that it does not heap-allocate, free, or leak any memory on the
heap. You may assume \verb"my_int_parser" has been implemented (its prototype
is given above).

\begin{solution} 
\begin{verbatim}
void parseit(char *s) {
  REQUIRES(s != NULL);
\end{verbatim}
\vspace{1.6in}
\begin{verbatim}
  return;
}
\end{verbatim}
\end{solution} 

\newpage
\part[3] In both C and C0, multiple values can be `returned' by bundling 
them in a struct:

\begin{verbatim}
struct bundle { int x; int y; };
struct bundle *foo(int x) {
  ...
  struct bundle *B = xmalloc(sizeof(struct bundle));
  B->x = e1; 
  B->y = e2; 
  return B;
}
int main() {
  ...
  struct bundle *B = foo(e);
  int x = B->x; 
  int y = B->y;
  free(B);
  ...
}
\end{verbatim}

Rewrite the declaration and the last few lines of the function \verb'foo',
as well as the snippet of \verb'main', to avoid heap-allocating, freeing, or
leaking any memory on the heap. The rest of the code (\verb"...") should continue
to behave exactly as it did before.

\begin{solution}
\begin{verbatim}
_______________ foo(___________________________________________) {
  ...

  ________________________________________________________________
 
  ________________________________________________________________

  ________________________________________________________________
}

int main() {
  ...

  ________________________________________________________________
  
  ________________________________________________________________
  
  ________________________________________________________________

  ________________________________________________________________
  ...
}
\end{verbatim}
\end{solution}


\end{parts}



















\end{questions}

\end{document}