\documentclass[12pt]{exam}
\usepackage[utf8]{inputenc} % For UTF8 source encoding.
\usepackage{amsmath} % For displaying math equations.
\usepackage{amsfonts} % For mathematical fonts (like \mathbb{E}!).
\usepackage{upgreek} % For upright Greek letters, such as \upvarphi.
\usepackage{wasysym} % For additional glyphs (like \smiley!).
% For document margins.
\usepackage[left=.8in, right=.8in, top=1in, bottom=1in]{geometry}
\usepackage{lastpage} % For a reference to the number of pages.
% TODO: Enter your name(s) here :)
\newcommand*{\authorname}{[Your name goes here]}
\newcommand*{\psetnumber}{4}
\newcommand*{\psetdescription}{Amortized Efficiency}
\newcommand*{\duedate}{Tuesday, May 19th}
\newcommand*{\duetime}{2:30 PM Pacific}
% Fancy headers and footers
\headrule
\firstpageheader{CS166\\Spring 2020}{Individual Assessment \psetnumber\\\psetdescription}{Due: \duedate\\at \duetime}
\runningheader{CS166}{Individual Assessment \psetnumber}{\authorname}
\footer{}{\footnotesize{Page \thepage\ of \pageref{LastPage}}}{}
% Exam questions.
\newcommand{\Q}[1]{\question{\large{\textbf{#1}}}}
\qformat{} % Remove formatting from exam questions.
% Useful macro commands.
\newcommand*{\ex}{\mathbb{E}}
\newcommand*{\bigtheta}[1]{\Theta\left( #1 \right)}
\newcommand*{\bigo}[1]{O \left( #1 \right)}
\newcommand*{\bigomega}[1]{\Omega \left( #1 \right)}
\newcommand*{\prob}[1]{\text{Pr} \left[ #1 \right]}
\newcommand*{\var}[1]{\text{Var} \left[ #1 \right]}
% Custom formatting for problem parts.
\renewcommand{\thepartno}{\roman{partno}}
\renewcommand{\partlabel}{\thepartno.}
% Framed answers.
\newcommand{\answerbox}[1]{
\begin{framed}
\hspace{\fill}
\vspace{#1}
\end{framed}}
% MZ
\makeatletter
\@namedef{ver@framed.sty}{9999/12/31}
\@namedef{opt@framed.sty}{}
\makeatother
\usepackage{minted}
\printanswers
\setlength\answerlinelength{2in} \setlength\answerskip{0.3in}
\begin{document}
\title{CS166 Individual Assessment \psetnumber: \psetdescription}
\author{\authorname}
\date{}
\maketitle
\thispagestyle{headandfoot}
\begin{questions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem One: Palos Altos}
The order of a tree in a Fibonacci heap establishes a lower bound on the number of nodes in that tree (a tree of order $k$ must have at least $F_{k+2}$ nodes in it). Surprisingly, the order of a tree in a Fibonacci heap does \emph{not} provide an upper bound on how many nodes are in that tree.
Prove that for any natural numbers $k > 0$ and $m$, there’s a sequence of operations that can be performed on an empty Fibonacci heap that results in the heap containing a tree of order $k$ with at least $m$ nodes (that is, the tree of order $k$ contains at least $m$ nodes). Illustrate the sequence of operations you get with $k = 2$ and $m = 8$ and show the resulting tree. You don’t need to draw out each step, but should provide enough detail to convince us (and yourself!) that your sequence indeed produces the correct tree.
\begin{solution}
Your solution goes here!
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\Q{Problem Two: Building B-Trees}
Suppose you have a sorted sequence of keys $x_1 < x_2 < \dots < x_n$ from which you’d like to construct a B-tree of order $b$. To do so, you could insert each key into an empty tree one at a time. If you were to do this, though, you'd find that you were doing a lot of unnecessary work traversing the tree top-down, since each search is guaranteed to terminate in the rightmost leaf. (Make sure you see why this is, but you don’t need to prove this.) This top-down searching would mean that the runtime of inserting the keys would be $\Omega(n \log_b n)$.
There's a much faster way to build a B-tree from scratch. Maintain a pointer to the rightmost leaf node in the B-tree, and annotate each node in the B-tree with the number of keys it contains. Then, insert each key, one at a time and in sorted order, using the following procedure:
\begin{enumerate}
\item Place the key in the next free slot in the rightmost leaf.
\item If the rightmost leaf overflows, split that leaf and propagate any further splits higher up in the tree using the usual node-splitting procedure.
\end{enumerate}
Prove that the amortized cost of inserting each element this way is $O(1)$ in two ways, first using the banker's method and second using the potential method. This shows that the cost of building a B-tree from a sorted sequence using this algorithm is $O(n)$, independent of the order of the B-tree.
For the banker's method, if an operation places down credits, tell us where those credits are placed, and if an operation spends credits, tell us which specific credits it spends and why the credits you’re spending are guaranteed to be there. For the potential method, clearly define what your potential $\Phi$ is in terms of the shape of the B-tree and explain why your potential begins at zero and is nonnegative.
Although B-trees are typically stored on-disk and analyzed in terms of disk reads and writes, for the purposes of this problem please analyze this algorithm in terms of the total number of operations performed, not the number of block transfers.
\begin{solution}
Your solution goes here!
\end{solution}
\end{questions}
\end{document}