\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 5}}{}{\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 5
}}
\vspace{0.2in}
(\large{Theory Part})
\vspace{0.2in}
\large{Due: Thur, June 14, 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
with formalizing data structure invariants, as well as heaps and priority queues.
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}
\newpage
\begin{questions}
\newpage
\question{\textbf{ Heaps.}}
Consider the min-heap below and answer the following questions
\begin{center}
\includegraphics[scale=0.6]{Min-heap.eps}
%http://en.wikipedia.org/wiki/File:Min-heap.png
\end{center}
\begin{parts}
\part[2] Show how this heap is stored in the array and briefly summarize the
method for mapping nodes in the heap to indices in the array.
\begin{solution}
\vspace{3in}
\end{solution}
\newpage
\part[2] What is the result of inserting an element with value $0$ into
the heap? Draw your answer as a tree. (You are only required to show the
final tree, but may show intermediate steps to ensure maximum partial
credit).
\begin{solution}
\vspace{3in}
\end{solution}
\part[2] What is the result of a \verb"heap_delmin"
operation on the original tree? Draw your answer as another tree.
(You are only required to show the final tree, but may show intermediate
steps to ensure maximum partial credit).
\begin{solution}
\vspace{3.5in}
\end{solution}
\end{parts}
\newpage
\question{\textbf{ Runtime Complexity.}}
\begin{parts}
\part[2] We have $n$ unsorted elements. What is the worst-case runtime
complexity of building a heap from these elements by inserting them one at
a time to an array? Assume that the array is large enough to hold the final
heap. Justify your answer.
\begin{solution}
\vspace{2.5in}
\end{solution}
\part[3]
Consider our implementation of min-heaps from class(e.g., the {\it
only} heap invariant we have is that a parent is always less than
its two children and that the binary tree is complete). Given a min-heap
of $n$ elements, design and explain an algorithm to find the maximum
element (no code is necessary). What is the worst-case
runtime complexity of your algorithm? \textbf{Hint:} don't think about this
strictly in terms of the interface functions for heaps. Just consider the
structure of the tree and the heap invariant.
\begin{solution}
\vspace{3in}
\end{solution}
\newpage
\part[3] If you insert the numbers $1, \ldots, 63$ (inclusively)
{\bf in any order} into a min-heap, what is the smallest number that
could be a leaf node? Explain your answer.
\begin{solution}
\vspace{4in}
\end{solution}
\end{parts}
\newpage
\question{\textbf{ Priority Queues.}}
\begin{parts}
\part[2]
We can implement a sorting algorithm using a heap. Explain, on an algorithmic
level, how this might work. Analyze the runtime complexity of this algorithm. \\
\textbf{No code is necessary.}
\begin{solution}
\vspace{3in}
\end{solution}
\part[2]
How might you use the priority queue to implement the ordinary LIFO
stack? Recall that the item with minimum priority is always removed
from a priority queue. What is the worst-case runtime complexity of
your \verb"push" and \verb"pop" operations? \\
\textbf{No code is necessary.}
\begin{solution}
\vspace{3in}
\end{solution}
\newpage
\part[2] How might you use the priority queue to implement the
ordinary FIFO queue? What is the worst-case runtime complexity of
your \verb"enqueue" and \verb"dequeue" operations? \\
\textbf{No code is necessary.}
\begin{solution}
\vspace{3in}
\end{solution}
\end{parts}
\end{questions}
\end{document}