\documentclass[10pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{fullpage}

\setlength{\textwidth}{6.5in} \setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in} \setlength{\headsep}{0.0in}
%\setlength{\topsep}{0in}
\setlength{\textheight}{9in} \setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}


\begin{document}

\title{Data Structures - Assignment no. 2, March 7, 2007}

\date{}

\maketitle

\def\lim{\mathop{\rm lim}\nolimits }
\def\true{ {\small\bf TRUE } }
\def\false{ {\small\bf FALSE } }
{\bf Remarks:
\begin{itemize}

\item Write both your name and your ID number very clearly on the
top of the exercise. Write your exercises in pen, or in clearly
visible pencil. Please write \emph{very} clearly.

\item Recall that 80\% of the theoretical exercises must be submitted. The
exercises can and must be worked on and submitted alone.

    \item  Give correctness and
        complexity proofs for every algorithm you write.
     \item For every problem, find the most
     efficient algorithm. A non efficient algorithm will be
     considered as an incomplete answer.
     \item For every question where you are required to write
     pseudo-code, also explain your solution in words.
\end{itemize}}

\normalsize

\begin{enumerate}

\item In the lecture you learned how to implement a deque using
two stacks (and a temporary stack during split) such that the
amortized time of each operation is $O(1)$. Recall that when one
stack ran out of elements, our implementation performs the
operation \textsc{split} which moves half of its elements into the
other stack. Now we ask you to describe and write pseudo-code for
a similar implementation, where the operation \textsc{split} moves
one third of the elements of the non-empty stack to the empty
stack. Prove that the cost of $m$ operations is still $O(m)$.

%\item Let us once again change the doubling method that you learned in
%class. This time, suppose that the size of the array is currently $s$ and
%it gets full. Then the algorithm creates a new array of size
%$s+\sqrt{s}$, copies the old array to the new array, and continues. How
%much time can a sequence of $m$ operations take in the worst-case? Prove
%your answer.

\item Insert the numbers 10,1,9,6,0,6.5 into the top tree, in order from left
to right. Which of the three depicted trees is the final result?
Only give a final answer, do not explain.

\begin{figure}[h]
\begin{center}
\scalebox{0.35}{\includegraphics{original.eps}}
\end{center}

\begin{center}
\scalebox{0.35}{\includegraphics{falsea.eps}}
\scalebox{0.35}{\includegraphics{correct.eps}}
\end{center}
\text{\hspace{+6cm}(a) \hspace{+4cm} (b)}
\begin{center}
\scalebox{0.35}{\includegraphics{falseb.eps}}
\end{center}
\text{\hspace{+9cm}(c)}
\end{figure}


\item You are given a binary search tree, where each node
contains a pointer \textsc{left} to its left child, a pointer
\textsc{right} to its right child, a pointer \textsc{parent} to
its parent, and  a key \textsc{key}. The keys are integers that
can be positive, negative or zero. Describe a procedure that
performs the following operation, and then write pseudo-code for
it: The operation is given a pointer to the root of the tree, and
needs to output the number of nodes who have the property that the
sum of the keys in the node's sub-tree is positive. The procedure
should take $O(n)$ time, where $n$ is the number of nodes in the
tree.\\ \underline{Hint:} Recursion may help.

\item \textbf{De-amortization.} In the lecture you learned the
``doubling'' method that allows to implement a stack using an array
without placing a limit on the size of the stack, such that the amortized
complexity of each operation is $O(1)$. The method is that every time the
array gets full, a new array is allocated whose size is twice the size of
the old array, and the old array is copied to the new array.

In this question we ask you to \emph{de-amortize} the doubling technique.
Specifically, give an implementation of a stack using an array, such that
the size of the stack can increase as much as needed (obviously, the array
should increase its size once in a while), but the running time of each
operation should be $O(1)$ \emph{in the worst case}. We assume that for
any value $k$, you can allocate an array of size $k$ in one time unit.
However, this array is initialized with arbitrary values: copying the old
array to the new array still takes time linear in the length of the old
array.\\
\underline{Hint:} The data structure should maintain two arrays
simultaneously.


\item \textbf{Challenge question. Not to be submitted.} In this
question you will implement a redundant counter. A redundant
counter is a binary-like counter, stored in an infinite array of
``bits'', which supports the operation $increment()$ which adds
$1$ to the value of the counter. Instead of bits, the digits of
the counter are 0, 1, and 2, but the counter is still binary: for
example, ``2012'' represents $2 \times 2^3 + 0 \times 2^2 + 1
\times 2^1 + 2 \times 2^0$. Thus, every number has more than one
possible representation.

\begin{enumerate}

\item Implement a redundant counter as above, such that each
$increment()$ operation changes only $O(1)$ ``bits'' \emph{in the
worst case}.

\item Improve the implementation so that you can perform an
increment operation in $O(1)$ time in the worst case. You are
allowed to store a pointer that can point to a location in the
array.

\item  If you solved this and you still want a challenge, try to
design a redundant binary counter that supports both increment and
decrement operations, both in time $O(1)$. This time you might
want to allow even more possible digits, for example $-1,0,1,2$.

\end{enumerate}

\end{enumerate}


\end{document}
