\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(s) go(es) here]}
\newcommand*{\psetnumber}{4}
\newcommand*{\psetdescription}{Amortized Efficiency}
\newcommand*{\duedate}{Tuesday, May 19}
\newcommand*{\duetime}{2:30 PM Pacific}
% Fancy headers and footers
\headrule
\firstpageheader{CS166\\Spring 2020}{Problem Set \psetnumber\\\psetdescription}{Due: \duedate\\at \duetime}
\runningheader{CS166}{Problem Set \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]}
\newcommand*{\RMQ}{\textrm{RMQ}}
\newcommand*{\RMQcomplexity}[2]{\left< #1, #2 \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
\usepackage{amsthm}
\usepackage{amssymb}
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\newcommand{\bi}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{stmaryrd}
\usepackage{pgfplots}
\pgfplotsset{compat=1.15}
\makeatletter
\@namedef{ver@framed.sty}{9999/12/31}
\@namedef{opt@framed.sty}{}
\makeatother
\usepackage{minted}
\usepackage{mathtools}
\usepackage{alltt}
\printanswers
\setlength\answerlinelength{2in} \setlength\answerskip{0.3in}
\begin{document}
\title{CS166 Problem Set \psetnumber: \psetdescription}
\author{\authorname}
\date{}
\maketitle
\thispagestyle{headandfoot}
\begin{questions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem One: 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 four operations:
\begin{itemize}
\item \textit{deque}.\texttt{add-to-front}($x$), which adds $x$ to the front of the sequence.
\item \textit{deque}.\texttt{add-to-back}($x$), which adds $x$ to the back of the sequence.
\item \textit{deque}.\texttt{remove-front}(), which removes and returns the front element of the sequence.
\item \textit{deque}.\texttt{remove-back}(), which removes and returns the last element of the sequence.
\end{itemize}
Design a deque implemented on top of three stacks. Each operation should run in amortized time $O(1)$. For the purposes of this problem, do not use any auxiliary data structures except for these stacks. Briefly argue correctness. Then, perform two different amortized analyses to show that you meet the runtime bounds, one using the banker's method and one using the potential method. 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 those credits are guaranteed to be there. For the potential method, clearly define your potential $\Phi$ and explain why your potential begins at zero and is nonnegative.
\begin{solution}
Your solution goes here!
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\Q{Problem Two: Meldable Heaps with Addition}
Meldable priority queues support the following operations:
\begin{itemize}
\item \texttt{new-pq}(), which constructs a new, empty priority queue;
\item $pq$.\texttt{insert}($v$, $k$), which inserts element $v$ with key $k$;
\item $pq$.\texttt{find-min}(), which returns an element with the least key;
\item $pq$.\texttt{extract-min}(), which removes and returns an element with the least key; and
\item \texttt{meld}($pq_1, pq_2)$, which destructively modifies priority queues $pq_1$ and $pq_2$ and produces a single priority
queue containing all the elements and keys from $pq_1$ and $pq_2$.
\end{itemize}
Some graph algorithms also require the following operation:
\begin{itemize}
\item $pq$.\texttt{add-to-all}($\Delta k$), which adds $\Delta k$ to the keys of each element in the priority queue.
\end{itemize}
Design a data structure that supports \texttt{new-pq}, \texttt{insert}, \texttt{find-min}, \texttt{meld}, and \texttt{add-to-all} in amortized time $O(1)$ and \texttt{extract-min} in amortized time $O(\log n)$. Briefly argue correctness, then do an amortized
analysis with either the banker’s method or the potential method to prove runtime bounds. Some hints:
\begin{enumerate}
\item As a warmup, get all these operations to run in worst-case time $O(\log n)$ by starting with an \textit{eager} binomial heap and making appropriate modifications. Your ultimate data structure will likely be based on lazy binomial heaps, but starting eager may give you some useful insights for later.
\item Try to make all operations have worst-case runtime $O(1)$ except for \texttt{extract-min}. Your implementation
of \texttt{extract-min} will probably do a lot of work, but if you've set it up correctly the
amortized cost will only be $O(\log n)$. This means, in particular, that you will only propagate the
$\Delta k$'s through the data structure in \texttt{extract-min}.
\item If you only propagate $\Delta k$'s during an \texttt{extract-min} as we suggest, you'll run into some challenges
trying to \texttt{meld} two lazy binomial heaps with different $\Delta k$'s. To address this, we recommend that
you change how \texttt{meld} is done to be even lazier than the lazy approach we discussed in class. You
might find it useful to construct a separate data structure tracking the \texttt{meld}s that have been done
and then only actually combining together the heaps during an \texttt{extract-min}.
\item Depending on how you've set things up, to get the proper amortized time bound for \texttt{extract-min},
you may need to define a potential function or place credits both in terms of the structure of the lazy binomial
heaps and in terms of the auxiliary data structure hinted at by the previous point.
\end{enumerate}
In your writeup, don’t just describe the final data structure all at once. Instead, walk us through the design.
Explain why each piece is there, why it’s needed, and how the whole structure comes together. Briefly argue correctness, and prove that you meet the required amortized time bounds.
\begin{solution}
Your solution goes here!
\end{solution}
\end{questions}
\end{document}