\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}{2}
\newcommand*{\psetdescription}{Balanced Trees}
\newcommand*{\duedate}{Thursday, April 22}
\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
\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{Deterministic Skiplists}

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 randomized data structure 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}

\pagebreak

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

\pagebreak

\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 Give two explanations as to why a lookup on a 2-3-4 skiplist takes worst-case $\bigo{\log n}$ time. First, do so purely by making reference to the rules you came up with in part (ii) and without referencing 2-3-4 trees. Second, do so by using the isometry from 2-3-4 trees to 2-3-4 skiplists.

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

\pagebreak

\part Show the effect of inserting the value 8 into the skiplist given in the assignment handout.

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

\pagebreak

\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.


Fun fact: Here, we started with a deterministic balanced tree (2-3-4 trees) and derived a deterministic
skiplist. You can also run this process in reverse by starting with a randomized skiplist and deriving a randomized balanced binary search tree (the \textbf{\emph{zip tree}}). This could make for a great final project topic!
\end{questions}
\end{document}
