\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}{1}
\newcommand*{\psetdescription}{Range Minimum Queries}
\newcommand*{\duedate}{Tuesday, April 17}
\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]}

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

\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: Sparse Tables with $\bigo{1}$ Queries}

To compute $\RMQ_A(i, j)$ with a sparse table in time $\bigo{1}$, it's necessary to compute in time $\bigo{1}$ the largest $k$ for which $2^k \le j - i + 1$. Explain how to modify the preprocessing step of the sparse table by adding $\bigo{n}$ additional work such that you can answer these queries in time $\bigo{1}$. Feel free to introduce as much additional memory as you think would be necessary.

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

For the purposes of this problem - and, more generally, throughout the world of data structures - we’ll need to pin down what sorts of operations you can perform on an integer that fits into a machine word in time $\bigo{1}$. You can assume that any mathematical or logical operation for which there's a built-in C operator (addition, multiplication, bitwise AND, bitshifts, etc.) take time $\bigo{1}$. You can also assume that the size of the array you’re working with fits into a machine word.

However, you should \textbf{\emph{not}} assume that more complex mathematical operations (logarithms, radicals, etc.) can be computed in time $\bigo{1}$, nor should you assume access to processor-specific bitwise operations (e.g. \texttt{popcount}, \texttt{bsr}, etc.). These assumptions are typically made in the world of data structures.

Importantly, the runtime of your operations should \textbf{\emph{not}} depend on the size of a machine word, and you should not assume that the word size is necessarily 32 or 64 bits.



\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem Two: Area Minimum Queries}

In what follows, if $A$ is a 2D array, we'll denote by $A[i, j]$ the entry at row $i$, column $j$, zero-indexed.

This problem concerns a two-dimensional variant of RMQ called the \textbf{\emph{area minimum query}} problem, or \textbf{\emph{AMQ}}. In AMQ, you are given a fixed, two-dimensional array of values and will have some amount of time to preprocess that array. You'll then be asked to answer queries of the form ``what is the smallest number contained in the rectangular region with upper-left corner $(i, j)$ and lower-right corner $(k, l)$?'' Mathematically, we'll define $AMQ_A((i, j), (k, l))$ to be $\min_{i \le s \le k, j \le t \le l} A[s, t]$. For example, consider the following array:
\[
\begin{array}{|c|c|c|c|c|c|c|}
\hline
31 & 41 & 59 & 26 & 53 & 58 & 97 \\ \hline
93 & 23 & 84 & 64 & 33 & 83 & 27 \\ \hline
95 &  2 & 88 & 41 & 97 & 16 & 93 \\ \hline
99 & 37 & 51 &  5 & 82 &  9 & 74 \\ \hline
94 & 45 & 92 & 30 & 78 & 16 & 40 \\ \hline
62 & 86 & 20 & 89 & 98 & 62 & 80 \\ \hline
\end{array}
\]

Here, $A[0, 0]$ is the upper-left corner, and $A[5, 6]$ is the lower-right corner. In this setting:
\begin{itemize}
\item $AMQ_A((0, 0), (5, 6)) = 2$
\item $AMQ_A((0, 0), (0, 6)) = 26$
\item $AMQ_A((2, 2), (3, 3)) = 5$
\end{itemize}

For the purposes of this problem, let $m$ denote the number of rows in $A$ and $n$ the number of columns.
\begin{parts}

\part Design and describe an $\RMQcomplexity{\bigo{mn}}{\bigo{\min\{m, n\}}}$-time data structure for AMQ.

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

\part Design and describe an $\RMQcomplexity{\bigo{mn \log m \log n}}{\bigo{1}}$-time data structure for AMQ.

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

\end{parts}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem Three: Hybrid RMQ Structures}

Let's begin with some new notation. For any $k \ge 0$, let's define the function $\log^{(k)} n$ to be the function:
\[
	\overbrace{\log \log \log \ldots \log}^{k \textrm{ times}} n
\]

For example:
\[
	\log^{(0)} n = n \qquad \log^{(1)} n = \log n \qquad \log^{(2)} n = \log \log n \qquad \log^{(3)} n = \log \log \log n
\]

This question explores these sorts of repeated logarithms in the context of range minimum queries.
\begin{parts}

\part Using the hybrid framework, show that that for any fixed $k \ge 1$, there is an RMQ data structure with time complexity $\RMQcomplexity{\bigo{n \log^{(k)} n}}{\bigo{1}}$. For notational simplicity, we'll refer to the $k$th of these
structures as $D_k$.

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

(Yes, we know that the Fischer-Heun structure is a $\RMQcomplexity{\bigo{n}}{\bigo{1}}$ solution to RMQ and therefore technically meets these requirements. But for the purposes of this question, let's imagine that you didn't know that such a structure existed and were instead curious to see how fast an RMQ structure you could make without resorting to the Method of Four Russians. \smiley)

\part Although every $D_k$ data structure has query time $\bigo{1}$, the query times on the $D_k$ structures will increase as k increases. Explain why this is the case and why this doesn't contradict your result from part (i).

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

\end{parts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem Four: Implementing RMQ Structures}

This one is all coding, so you don't need to write anything here. Make sure to submit your final implementations on myth.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{questions}
\end{document}