\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}{Tuesday, May 7th}
\newcommand*{\duetime}{2:30 pm}
% Fancy headers and footers
\headrule
\firstpageheader{CS166\\Spring 2019}{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: Dynamic Overlap (8 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: 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 Briefly explain how to encode a multiway tree as a skiplist. Include illustrations as appropriate.
\begin{solution}
Your solution goes here!
\end{solution}
\uplevel{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 effect they 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}
\uplevel{Going forward, we'll call a skiplist that obeys the rules you came up with in part (ii) a \textbf{\emph{2-3-4 skiplist}}.}
\part Briefy explain why a lookup on a 2-3-4 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 2-3-4 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 2-3-4 skiplist or how to implement split or join on 2-3-4 skiplists as well.
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem Four: Dynamic Prefix Parity (10 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 these operations:
\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 \textit{parity} of the subarray consisting of the first \textit{i} bits of the subarray. (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?) However, it's possible to do significantly better than this.
\begin{parts}
\part Let's begin with an initial version of the data structure. Describe how to use augmented binary trees to solve dynamic prefix parity such that \texttt{initialize} runs in time $\bigo(n)$ and both \texttt{flip} and \texttt{prefix-parity} run in time $\bigo{\log n}$. Argue correctness and justify your runtime bounds.
\begin{solution}
Your solution goes here!
\end{solution}
\part Explain how to revise your solution from part (i) of this problem so that instead of using augmented \textit{binary} trees, you use augmented \textit{multiway} trees. Your solution should have \texttt{initialize} take time $\bigo{n}$, \texttt{flip} take time $\bigo{\log_k n}$, and \texttt{prefix-parity} take time $\bigo{k \log_k n}$. Here, $k$ is a tunable parameter representing the number of keys that can be stored in each node in the multiway tree. Argue correctness and justify your runtime bounds.
We didn't explicitly discuss the idea of augmenting multiway trees in lecture, but we hope that the generalization isn't too tricky, especially since your tree never changes shape.
\begin{solution}
Your solution goes here!
\end{solution}
\part Using the Method of Four Russians, modify your data structure from part (i) so that \texttt{initialize} still runs in time $\bigo{n}$, but both \texttt{flip} and \texttt{prefix-parity} run in time $\bigo{\log n / \log \log n}$.
This last step is probably the trickiest part. Here are some hints:
\begin{itemize}
\item It might help to think of the Method of Four Russians as a “divide, precompute, and conquer” approach. That is, break the problem down into multiple smaller copies of itself, precompute all possible answers to the smaller versions of those problems, then solve the overall problem by looking up precomputed answers where appropriate. That is, this will be less about explicitly sharing answers to subproblems and more about having the answers to all possible small problems written down somewhere. Do you see how your solution to part (ii) implicitly breaks the bigger problem down into lots of smaller copies?
\item Remember that $\log_k b = \log b / \log k$ thanks to the change-of-basis formula.
\item All basic arithmetic operations are assumed to take time $\bigo{1}$. However, floating-point operations are not considered basic arithmetic operations, nor are operations like "count the number of 1 bits in a machine word" or "find the leftmost 1 bit in a machine word."
\item An array of bits can be thought of as an integer, and integers can be used as indices in array-based lookup structures.
\item Be precise with your choice of block size. Constant factors matter!
\end{itemize}
As usual, argue correctness. Be sure to justify your runtime bounds precisely -- as with the Fischer-Heun structure, your analysis will hinge on the fact that there aren't "too many" subproblems to compute the answers to all of them.
\begin{solution}
Your solution goes here!
\end{solution}
\end{parts}
Pat yourself on the back when you finish this problem. Isn't that an amazing data structure?
\end{questions}
\end{document}