
\documentstyle[11pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagestyle{empty}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0.0in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\topmargin}{-0.25in}
\setlength{\textheight}{9.0in}
\setlength{\baselineskip}{1.3\baselineskip}
\setlength{\parindent}{0in}

\newcommand\qed{\hspace*{\fill} {\large$\Box$}}
\newcommand\set[1]{\left\{#1\right\}}
\newcommand\ang[1]{\left\langle #1 \right\rangle}
\newcommand\brac[1]{{\left[ {#1} \right]}}
\newcommand\card[1]{\left| #1 \right|}
\newcommand\inR{{~\in_{\rm R}~}}

\newenvironment{header}[2]{\begin{center} {\Large\bf Data Structures -
          Assignment no. #1} \\ \medskip {\small Date due: #2}
       }{\end{center} \bigskip}

\begin{document}

\vspace{-7ex}
{\em \hfill \footnotesize DS98a}

\vspace{0.3in}
\begin{header}{2}{8/12/97}
\end{header}

\vspace{0.6in}


\def\lim{\mathop{\rm lim}\nolimits }
\def\true{ {\small\bf TRUE } }
\def\false{ {\small\bf FALSE } }



\begin{enumerate}
  \item In the following sections, find the order of the fuction
    $T(n)$, which is given as a recurrence. The boundary conditions
    are omitted.
    \begin{enumerate}
      \item $T(n)=T(n-a)+T(a)+1$ (where $a$ is some constant).
      \item $T(n)=T(cn)+T((1-c)n)+1$ (where $0<c<1$ is some constant).
      \item $T(n)=T(\sqrt n)+1$
      \item $T(n)=4T({n\over 2})+n$
      \item $T(n)=4T({n\over 2})+n^2$
      \item $T(n)=4T({n\over 2})+n^3$
    \end{enumerate}
    
  \item A given data-structure is said to have {\bf{amortized
          complexity}} $O(f(n))$ for each operation, if after
    initiation of the structure, the time needed for any sequence of
    $n$ consecutive operations on the structure, $T(n)$, satisfies
    ${T(n)\over n}=O(f(n))$. In other words, the average time for each
    operation, over a sequence of $n$ operations, does not exceed
    $f(n)$ times a constant factor.
    
    Implement a queue, using two stacks and $O(1)$ additional memory,
    such that the amortized complexity of each operation is $O(1)$.
    
  \item Implement a data-structure which supports the operations of an
    array (i.e. writing or reading a given entry, for entries
    $1,2,\ldots ,n$), and in addition supports the operation {\small
       SET\_ALL}$(u)$, which assigns the value $u$ to all the entries
    of the structure. The complexity of {\bf each} operation should be
    $O(1)$. There are no time limitations for the initiation of the
    structure.
    
  \item You are given an array, $A$, of numbers, and another number
    $x$. Write an algorithm which finds the index of an entry in $A$
    where $x$ appears. If $x$ does not appear in $A$ the algorithm
    should return $-1$.
    \begin{enumerate}
      \item The complexity should be $O(\log n)$, where $n$ is the
        length of $A$.
      \item If $x$ appears in $A[i]$, the complexity should be $O(\log
        (\min\set{i,n-i}))$. If $x$ does not appear in $A$ the
        algorithm should take $O(\log n)$ time.
    \end{enumerate}
    
  \item You are given a data structure $S$, which contains $n$ numbers
    $S[1],S[2],\ldots,S[n]$. $S$ supports only one operation -
    {\small GET\_BIT}$(i,j)$, which returns the $j$'th bit of the
    binary representation of $S[i]$ (counting from right to left). The
    operation takes $O(1)$ time.
    
    Suppose $S$ is known to contain exactly one of each of the numbers
    $0,1,\ldots,2^u-1$ for some $u$, except for one of these numbers
    which does not exist in $S$ at all (so $n=2^u-1$). $S$ is not
    necessarily sorted. Write an efficient algoritm which finds which
    is the missing number (compute the efficiency with respecet to
    $n$).
\end{enumerate}     

\end{document}