%Template based off AMS Dept HW class file v0.05 by Eric Harley
\documentclass{article}

\usepackage{verbatim}
\usepackage{graphicx}
\usepackage{amssymb,amsmath,amsthm,amsfonts,mathtools}
\usepackage{hyperref}
\usepackage{fullpage}
\usepackage{url}
\usepackage{listings}
\usepackage[utf8]{inputenc}
\usepackage{boxedminipage}
\usepackage{enumerate}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}

\newenvironment{problem}{%
  \bigskip\noindent\begin{boxedminipage}{\columnwidth}%
}{\end{boxedminipage}}

\newenvironment{solution}{%
  \begin{trivlist}\item[]%
}{%
  \mbox{}\penalty10000\hfill\ensuremath{\scriptscriptstyle\blacksquare}%
  \end{trivlist}%
}

\begin{document}

\begin{flushright}
Your name\\
CS 261, Spring 2021\\
Homework 6\\
Due Monday, May 10
\end{flushright}

\begin{problem}
\textbf{1.} Some text-base user interfaces (including several variations of the Linux shell) can perform "command-line completion": if you type enough characters of a command name to uniquely identify that command, you can hit a special key (such as the tab key) and automatically extend what you've typed to become the full command name. For instance one might type ``pdfl'' followed by a tab, and see ``pdflatex'' on the command line.

\smallskip
Suppose you have a binary search tree data structure whose keys are commands, and that this search tree can be accessed using only the operations described on the "binary search operations" slide. Describe how to use these operations to find the command-line completion of a given partial command name. The algorithm you describe should either return the completion of the given command, or an error condition indicating that there is not a unique completion (either there is no command that matches, or there is more than one match).
\end{problem}

\begin{solution}
% YOUR SOLUTION TO PROBLEM 1 GOES HERE
\end{solution}

\begin{problem}
\textbf{2.} If $x$ is the minimum of a set of $n$ items, and these items are inserted into a search tree in random order without rebalancing, then the probability that $x$ is the root of the tree is $1/n$: it can only be root if it is inserted first. What is the probability that it is one of the children of the root?
\end{problem}

\begin{solution}
% YOUR SOLUTION TO PROBLEM 2 GOES HERE
\end{solution}

\begin{problem}
\textbf{3.} The version of B-trees described in the lecture notes defines a block as being ``too full'' when it has $\ge b$ keys, and ``too empty'' when it has $<b/2$ keys. These definitions are used on the ``Updates'' slide of the lecture notes, to determine when we need to merge and split blocks.

\smallskip
Suppose we modify this definition so that a block is defined as too empty when it has $<b/3$ keys, but otherwise we use the same update operations. This modification uses more memory (because blocks can be emptier) but it has the advantage that there are very few merges and splits of blocks: on average, the number of merges and splits is smaller than the number of insertions and deletions by a factor proportional to $b$.

\smallskip
Describe a potential function that can be used to prove that, with this modified definition of too empty, the amortized number of merges or splits per insertion or deletion is $O(1/b)$. To do this, your potential function should have the property that it can increase by only $O(1/b)$ in each insertion or deletion operation, and that it decreases by at least one unit for every merge or split that the update operations perform.

\end{problem}

\begin{solution}
% YOUR SOLUTION TO PROBLEM 3 GOES HERE
\end{solution}

\begin{problem}
\textbf{4.} Give an example of a set of ordered keys, and a sequence of operations on those keys, for which the smallest arborially satisfied set cannot come from the access pattern of a static search tree. Include in your answer a smallest arborially satisfied set for your example.
\end{problem}

\begin{solution}
% YOUR SOLUTION TO PROBLEM 4 GOES HERE
\end{solution}

\end{document}
