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

% Fancy headers and footers
\headrule
\firstpageheader{CS166\\Spring 2021}{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: Very Dynamic Prefix Parity}

On Problem Set Two, you designed a data structure for the \bi{dynamic prefix parity problem}. This data
structure supports the following operations:
\begin{itemize}
\item \texttt{initialize}($n$), which creates a new data structure representing an array of $n$ bits, all initially zero. This takes time $O(n)$.
\item \textit{ds}.\texttt{flip}($i$), which flips the $i$th bit of the bitstring. This takes time $O(\frac{\log n}{\log\log n})$.
\item \textit{ds}.\texttt{prefix-parity}($i$), which returns the parity of the subarray consisting of the first $i$ bits of the array. (the \textit{parity} is 0 if there are an even number of one bits and 1 if there are an odd number of 1 bits). This has the same runtime as the flip operation, $O(\frac{\log n}{\log\log n})$.
\end{itemize}

Now, consider the very \bi{dynamic prefix parity problem} (or VDDP). In this problem, you don’t begin with
a fixed array of bits, but instead start with an empty sequence. You then need to support these operations:
\begin{itemize}
\item \texttt{initialize}(), which constructs a new, empty VDPP structure.
\item \textit{ds}.\texttt{append}($b$),which appends bit $b$ to the bitstring.
\item \textit{ds}.\texttt{flip}($i$), which flips the $i$th bit of the bitstring.
\item \textit{ds}.\texttt{prefix-parity}($i$), which returns the parity of the subarray consisting of the first $i$ bits of the array
\end{itemize}

Design a data structure for VDPP such that all three operations run in \textit{amortized} time $O(\frac{\log n}{\log\log n})$, where $n$ is the number of bits in the sequence at the time the operation is performed.

Briefly argue correctness, and prove that you meet the required amortized time bounds by defining a potential function $\Phi$ and working out the amortized costs of each operation. 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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 \textit{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 your potential function 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 by defining a potential function $\Phi$ and working out the amortized costs of each operation.

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{questions}
\end{document}
