\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}{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}{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: Order Statistics Trees}

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

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Q{Problem Two: Dynamic Prefix Parity}

Consider the following problem, called the \textbf{\emph{dynamic prefix parity problem}} (DPP). 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. In this problem, you’ll work through a series of smaller milestones that culminates in a theoretically optimal result.

\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{itemize}
	\item You have the luxury of working with a tree where insertions and deletions will never happen; the number of items is specified in \texttt{initialize(n)} and never changes after that. Therefore, provided you can give initial values to any extra information you’re caching at each node, and provided that you can update that information in $\bigo{\log n}$ total time after a flip operation, you can meet the required time bounds.
	\item The order statistics tree works because each node only needed to store information about what was to its left. That worked because rank queries purely care about the node and its left subtree. See if you can use that idea here as well.
	\item A powerful technique we haven’t yet encountered, but which might be useful to you here: consider making your tree such that only the leaf nodes store actual data, with all the internal nodes just serving as a way to join smaller subtrees together and cache relevant data.
	\item When designing an augmented tree, it often helps to first solve the problem on a static array
	using a divide-and-conquer algorithm. So consider doing the following: suppose you had an array of $n$ bits. Could you design a divide-and-conquer algorithm for computing prefix parities that has the recurrence relation $T(n) = 2T(n / 2) + \bigo{1}$? If so, you can often translate your idea into an augmented tree by caching, at each node in the tree, the value that would be returned by running that divide-and-conquer algorithm on the elements in that tree.
\end{itemize}

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

\pagebreak

\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_b n}$, and \texttt{prefix-parity} take time $\bigo{b \log_b n}$. Here, $b$ is a
tunable parameter. Argue correctness and justify your runtime bounds.

Some things to think about as you do this:

\begin{itemize}
	\item In an order statistics tree, we store one piece of information per node, since of a node’s two children we only needed to care about the left child. Now that you have a multiway tree where each node can have multiple children, you may want to store multiple pieces of extra information per node.
	\item In lecture, we saw an algorithm that builds a B-tree from a set of $n$ sorted keys in time $\bigo{n}$, annotating each node with a pointer to its parent. That algorithm can easily be modified to also store, for each node, which child it is of its parent (e.g. first child, third child, etc.) without changing the overall runtime. It can also be modified to build a B-tree with a particular set of $n$ leaves in time $\bigo{n}$. Feel free to use this algorithm as a black box.
\end{itemize}

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

\pagebreak

\part Using the Method of Four Russians, modify your data structure from part (ii) 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 In Fischer-Heun, the Method of Four Russians took the form of “share solutions to subproblems when you can.” Here, 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. 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_x y = \log y / \log x$ 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}

\pagebreak

\end{parts}

Pat yourself on the back when you finish this problem. Isn’t that an amazing data structure? It turns out that this data structure is asymptotically optimal (it can only be improved by reducing constant factors, not its asymptotic runtimes) under the assumption that you have just a single processor and that memory is segmented into individual machine words of size $\bigomega{\log n}$. Understanding how this lower bound works could make for an excellent final project!

\end{questions}
\end{document}
