\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{url}

\title{CS140 - Assignment 5\\\small{Due: Sunday,  Oct. 9 at 11:59pm}}
\author{}
\date{}


\begin{document}
\maketitle

\vspace{-.5in}

\begin{center}
\includegraphics[scale=0.6]{figures/math.jpg}
\footnotesize{http://www.smbc-comics.com/index.php?db=comics\&id=1872}
\end{center}

\noindent You may (and are encouraged) to work with a partner on this assignment.  \textbf{However, if you decide to work with a partner on this assignment, it must be someone that you haven't previously partnered with on an assignment.} If you're looking for a partner, post on slack (or email me).  Please do this sooner than later!\\





\begin{enumerate}

\setcounter{enumi}{-1}

\item \emph{Optional:} We're about a third of the way through the course and I wanted to checkin and see how things are going.  I've gotten some feedback the group assignments, but I'd also love to get individual feedback on things.  If you want (it's anonymous), take 5 minutes and let me know how things are going:

\url{https://forms.gle/yVdT3MEfRCUw7gWF8}
  
\item \textbf{[20 points]} More Balanced Binary Search Trees
 
Red-black trees maintain a set of five properties; in class we showed
that maintaining those properties guarantees that the height of a
red-black tree with $n$ nodes is never more than $2\log(n+1)$.
Consider another balanced binary search tree which maintains the
following invariant: for any node $x$, the heights of the left and
right subtrees of $x$ differ by at most $1$.  We'll call these 1off
trees.

\begin{enumerate}
\item {[14 points]} Prove by strong induction on the height of the tree that a 1off
  tree with height $h$ has at least $f(h)$ nodes, where $f(h)$ is the
  $h$th Fibonacci number.  (Recall that $f(n) = f(n-1)+f(n-2)$ and
  that $f(0) = f(1) = 1$.)
\item {[3 points]} Use the previous part to show that a 1off tree with height $h$ has
  at least $2f(h-2)$ nodes.
\item {[3 points]} Finally show that a 1off tree with $n$ nodes has $O(\log n)$ height.
\end{enumerate}


\item \textbf{[18 points]} Stacks and queues

Assume you're given an implementation
of a stack that supports {\tt push} and {\tt pop} in $O(1)$ time.  Now you'd
like to implement a queue using these stacks.

\begin{enumerate}
\item {[10 points]} Explain how you can efficiently implement a queue 
  using two of these stacks.  (``Efficiently'' means in a way that
  allows you to do the next part of the problem.)
\item {[8 points]} Prove that 
  the amortized cost of each {\tt enqueue} and {\tt dequeue} operation 
  is $O(1)$ for your stack-based queue by using the
  the aggregate amortized analysis technique.
\end{enumerate}
\end{enumerate}
\end{document}
