\documentclass[11pt]{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{\textheight}{9in} \setlength{\oddsidemargin}{0in}
%\setlength{\evensidemargin}{0in}

\begin{document}

\title{Data Structures - Assignment no. 1, February 28, 2007}

\date{}

\maketitle

\small

\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 Which of the following statements are true and which are false? Only give an answer, you
do not have to explain:

\begin{enumerate}

\item $40 \log n = O( 8 \log n)$.

\item $2^n/300 = O(n)$.

\item $40n+6=O(2^n-50)$.

\item $40n+6=O(\log n+17)$.

\end{enumerate}


\item A \emph{deque} (double-ended queue) is an ADT (Abstract Data Type) 
that supports the following operations:

\begin{enumerate}

\item Push(x,D): Inserts $x$ at the head of the deque.

\item Pop(D): Removes the element at the head of the
deque and returns it.

\item Inject(x,D): Inserts $x$ at the tail of the deque.

\item Eject(D): Removes the element at the tail of the
deque and returns it.

\item Size(D): Returns the number of elements in the deque.

\item Empty?(D): Returns true if and only if the
deque is empty

\item Make-deque(): Generates an empty deque

\end{enumerate}

Give a description, not in pseudo-code, of an implementation of
this ADT that uses an array of fixed size $N$. Define
precisely the representation of your data
structure. Then describe in pseudo-code the implementations of
$Push(x,D)$, $Size(D)$, and $Eject(D)$. 
You can assume that we never try to
$Pop(D)$ or $Eject(D)$ when $D$ is an empty deque, and that the
size of the deque never exceeds $N$.
All operations should take $O(1)$ time. Note that in order to avoid the 
situation where the deque is almost empty but you can't insert new 
elements, you'd probably have the use the ``circular array'' technique 
that you learned in class. Note that the size of the deque is bounded by 
$N$, so you don't have to use the ``doubling'' method.

\item 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.

\begin{enumerate}

\item Suppose we change the implementation so that the size of the new array
is 4/3 times the size of the old array. What is the time complexity of
a sequence of $m$ operations on the worst-case?
Prove\footnote{Here and in
the future -- we don't care which method you use to prove the
claim, as long as it is correct! Specifically, you can use a bank,
 the potential method, or any other method you
like.} your answer.

\item Suppose we change the implementation so that the size of the new array
is 10 \textbf{plus} the size of the old array. What is the time complexity 
of a sequence of $m$ operations on the worst-case?
Prove your answer.

\end{enumerate}

\item \begin{enumerate}

\item Implement, in pseudo-code, a trenary (base-3) counter: You are given an
infinite array such that each cell can only hold the digits 0,1,2,
and you want the counter to support the operation
\emph{increment()} that increases the value of the counter by 1.

\item Suppose you start from a counter initialized to 0 and you
perform $m$ $increment()$ operations. What is their total cost?
What is the amortized time complexity of increment? Prove
your answer.

\end{enumerate}

\item Let $L$ be a singly-linked list that consists of $n$ elements. Each element contains a
pointer ``next''. Someone possibly made a mistake, and the final
element of the list, instead of having a ``null'' pointer, might
be pointing to an element inside the list. What does the following
pseudo-code do? What is its worst-case time complexity?

\medskip

\begin{tabbing}
xx \= \kill

INPUT: $x$, which is a pointer to the first element of the list\\
$y \leftarrow x.next$\\
IF ($y==NULL$) THEN RETURN ``true''\\
WHILE ($y \neq x$)\\
  \> $y \leftarrow y.next$ \\
  \> IF ($y==NULL$) THEN RETURN ``true'' \\
  \> $y \leftarrow y.next$ \\
  \> IF ($y==NULL$) THEN RETURN ``true'' \\
  \> $x \leftarrow x.next$ \\
END WHILE\\
RETURN ``false''\\
\end{tabbing}

\end{enumerate}
\end{document}

