\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}{3}
\newcommand*{\psetdescription}{Amortization}
\newcommand*{\duedate}{Tuesday, May 4th}
\newcommand*{\duetime}{2:30 PM Pacific}

% Fancy headers and footers
\headrule
\firstpageheader{CS166\\Spring 2021}{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
\newcommand{\bi}[1]{\textit{\textbf{#1}}}
\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: Stacking the Deque}

A \bi{deque} (\bi{d}ouble-\bi{e}nded \bi{que}ue, pronounced ``deck") is a data structure that acts as a hybrid between a stack and a queue. It represents a sequence of elements and supports the following six operations:
\begin{itemize}
	\item \textit{deque}.\texttt{push\_front}($x$), which adds $x$ to the front of the sequence.
	\item \textit{deque}.\texttt{push\_back}($x$), which adds $x$ to the back of the sequence.
	\item \textit{deque}.\texttt{front}(), which returns (but does not remove) the front element of the sequence.
	\item \textit{deque}.\texttt{back}(), which returns (but does not remove) the last element of the sequence.
	\item \textit{deque}.\texttt{pop\_front}(), which removes and returns the front element of the sequence.
	\item \textit{deque}.\texttt{pop\_back}(), which removes and returns the last element of the sequence.
\end{itemize}

Your goal in this problem is to a deque using three stacks such that each operation runs in amortized time
$O(1)$, under the assumption that each operation on a stack takes time $O(1)$. You may not use any auxiliary
or helper data structures other than these stacks. You’ll do this in two steps. First, you’ll code up an implementation of your three-stack queue. Next, you’ll write up an analysis of the three-stack queue to explain
why, indeed, each operation takes amortized time $O(1)$.

\begin{parts}
\part This one is all coding! Make sure to submit your implementation on \texttt{myth}.

\part Give a brief description of your data structure in plain English, the way you’d write up a solution to a non-coding question. Then, define a potential function $\Phi$ and use the potential method to argue that the amortized cost of each of the six operations on your three-stack deque is $O(1)$.

We’re expecting your amortized analysis to be written up in a manner similar to the formal analyses we did in lecture of the two-stack queue, dynamic array, and B-tree construction algorithm. 
\begin{solution}
	Your solution goes here!
\end{solution}

\end{parts}





\end{questions}
\end{document}
