\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}{Balanced Trees}
\newcommand*{\duedate}{Thursday, May 7}
\newcommand*{\duetime}{2:30 PM Pacific}
% Fancy headers and footers
\headrule
\firstpageheader{CS166\\Spring 2020}{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}}. 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 (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_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}