\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 here :)
\newcommand*{\authorname}{[Your name goes here]}

\newcommand*{\psetnumber}{3}
\newcommand*{\psetdescription}{Balanced Trees}
\newcommand*{\duedate}{Thursday, May 3rd}
\newcommand*{\duetime}{2:30 pm}

% Fancy headers and footers
\headrule
\firstpageheader{CS166\\Spring 2018}{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]}

% 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}}

\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: Red/Black and AVL Trees (6 Points)}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem Two: Range Excision (2 Points)}

\begin{parts}

\part Design and describe an algorithm that, given a red/black tree $T$ and two values $k_1$ and $k_2$, deletes all keys between $k_1$ and $k_2$, inclusive, that are in $T$. Your algorithm should run in time $\bigo{\log n + z}$, where $n$ is the number of nodes in $T$ and $z$ is the number of elements deleted. You should assume that it's your responsibility to free the memory for the deleted elements and that deallocating a node takes time $\bigo{1}$.

\begin{solution}
Your solution goes here!
\end{solution}

\end{parts}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem Three: Dynamic Prefix Parities (8 Points)}

Consider the following problem, called the \textbf{\emph{dynamic prefix parity problem}}. Your task is to design a data structure that logically represents an array of $n$ bits, each initially zero, and supports the following operations as efficiently as possible:
\begin{itemize}
	\item $\texttt{initialize}(n)$, which creates a new data structure for an array of $n$ bits, all initially 0;
	\item $ds.\texttt{flip}(i)$, which flips the $i$th bit; and
	\item $ds.\texttt{prefix-parity}(i)$, which returns the parity of the subarray from index 0 to index $i$, inclusive. (The parity of a subarray is zero if the subarray contains an even number of 1 bits and is one if it contains an odd number of 1 bits. Equivalently, the parity of a subarray is the logical XOR of all the bits in that array).
\end{itemize}

It's possible to solve this problem with \texttt{initialize} taking $\bigo{n}$ time such that \texttt{flip} runs in time $\bigo{1}$ and \texttt{prefix-parity} runs in time $\bigo{n}$ or vice-versa (do you see how?), but it's possible to get excellent runtimes for both \texttt{flip} and \texttt{prefix-parity} by being more creative with the approach.

\begin{parts}

\part Let $k \ge 2$ be an arbitrary natural number. Design a data structure that solves the prefix parity problem such that
\begin{itemize}
    \item $\texttt{initialize}(n)$ takes time $\bigo{n}$,
    \item $ds.\texttt{flip}(i)$ takes time $\bigo{\log_k n}$, and
    \item $ds.\texttt{prefix-parity}(i)$ takes time $\bigo{k \log_k n}$.
\end{itemize}

As a hint, start by thinking about how you’d use augmented binary trees to solve this problem, then see if you can generalize your answer to use multiway trees rather than binary trees.

\begin{solution}
Your solution goes here!
\end{solution}

In the course of solving part (i) of this problem, you essentially reduced the large problem of ``solve dynamic prefix parity for an array of size n'' to ``solve dynamic prefix parity for a bunch of smaller arrays of some smaller size.''\footnote{If you didn't notice that – or if you're having trouble with part (i) of this problem -- consider this a free hint from your friendly course staff! \smiley} That sounds a lot like what we did in the Fischer-Heun RMQ data structure, which turned the larger problem of ``solve RMQ on an array of size n'' into ``solve RMQ on a bunch of arrays of a smaller size.'' And just as we used a Four Russians speedup to build a fast solution to RMQ, you can use a Four Russians speedup to boost the performance of your structure from part (i).

\part Modify your data structure from part (i) of this problem so that
\begin{itemize}
	\item $\texttt{initialize}(n)$ takes time $\bigo{n}$,
	\item $ds.\texttt{flip}(i)$ takes time $\bigo{\frac{\log n}{\log \log n}}$, and
	\item $ds.\texttt{prefix-parity}(i)$ takes time $\bigo{\frac{\log n}{\log \log n}}$.
\end{itemize}

Some hints on part (ii) of this problem:
\begin{itemize}
	\item Remember that $\log_k b = \bigtheta{\frac{\log b}{\log k}}$ thanks to the change-of-basis formula.
	\item Think about precomputing a lookup table of all possible array/query pairs for sufficiently small arrays. How might that change how you do prefix-parity queries?
	\item An array of bits can give an integer that can be used as an index in an array-based lookup table.
	\item Be precise with your choice of block size. Constant factors matter!
\end{itemize}

\begin{solution}
Your solution goes here!
\end{solution}

\end{parts}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem Four: Deterministic Skiplists (8 Points)}

Although we've spent a lot of time talking about balanced trees, they are not the only data structure we can use to implement a sorted dictionary. Another popular option is the \textbf{\emph{skiplist}}, a data structure consisting of a collection of nodes with several different linked lists threaded through them.

Before attempting this problem, you'll need to familiarize yourself with how a skiplist operates. We recommend a combination of reading over the Wikipedia entry on skiplists and the original paper ``Skip Lists: A Probabilistic Alternative to Balanced Trees'' by William Pugh (available on the course website). You don't need to dive too deep into the runtime analysis of skiplists, but you do need to understand how to search a skiplist and the normal (randomized) algorithm for performing insertions.

The original version of the skiplist introduced in Pugh's paper, as suggested by the title, is probabilistic and gives \emph{expected} $\bigo{\log n}$ performance on each of the underlying operations. In this problem, you'll use an isometry between multiway trees and skiplists to develop a fully-deterministic skiplist data structure that supports all major operations in \emph{worst-case} time $\bigo{\log n}$.

\begin{parts}

\part There is a beautiful isometry between multiway trees and skiplists. Describe how to encode a skiplist as a multiway tree and a multi-way tree as a skiplist. Include illustrations as appropriate.

\begin{solution}
Your solution goes here!
\end{solution}

To design a deterministic skiplist supporting insertions, deletions, and lookups in time $\bigo{\log n}$ each, we will enforce that the skiplist always is an isometry of a 2-3-4 tree.

\part Using the structural rules for 2-3-4 trees and the isometry between multiway trees and skiplists you noted in part (i) of this problem, come up with a set of structural requirements that must hold for any skip list that happens to be the isometry of a 2-3-4 tree. To do so, go through each of the structural requirements required of a 2-3-4 tree and determine what efect that will have on the shape of a skiplist that's an isometry of a 2-3-4 tree.

\begin{solution}
Your solution goes here!
\end{solution}

Going forward, we'll call a skiplist that obeys the rules you came up with in part (ii) a \textbf{\emph{1-2-3 skiplist}}.

\part Briefy explain why a lookup on a 1-2-3 skiplist takes worst-case $\bigo{\log n}$ time.

\begin{solution}
Your solution goes here!
\end{solution}

\part Based on the isometry you found in part (i) and the rules you developed in part (ii) of this problem, design a deterministic, (optionally amortized) $\bigo{\log n}$-time algorithm for inserting a new element into a 1-2-3 skiplist. Demonstrate your algorithm by showing the effect of inserting the value 8 into the skiplist given in the assignment handout.

\begin{solution}
Your solution goes here!
\end{solution}

\end{parts}

Congrats! You've just used an isometry to design your own data structure! If you had fun with this, you're welcome to continue to use this isometry to fgure out how to delete from a 1-2-3 skiplist or how to implement split or join on 1-2-3 skiplists as well.

\end{questions}
\end{document}