\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{\topsep}{0in}
\setlength{\textheight}{9in} \setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}


%\documentstyle[11pt]{article}
%\usepackage{fullpage}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\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}~}}


\begin{document}



\title{Data Structures - Assignment no. 7, May 10, 2006}

\date{}

\maketitle


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

\vspace{-1.5cm}

 {\small {\bf Remarks:
\begin{itemize}
     \item Please write your exercises in pen, or in clearly visible pencil. Please write \textbf{very} clearly.
     \item For every question where you are required to write
     pseudo-code, also explain your solution in words.
\end{itemize} }}



\begin{enumerate}

\item Find the order of growth for the following recursively
    given functions, using the Master Method.
  \begin{enumerate}
  \item $T(n) = 4T(n/2)+n$
  \item $T(n) = 4T(n/2)+n^2$
  \item $T(n) = 4T(n/2)+n^3$
  \item Explain why $T(n) = 2T(n/2)+n log^2n $ cannot be solved using the Mater Method.
  \end{enumerate}

  \item Find the order of growth for the following recursively
    given functions. Explain your answer.

  \begin{enumerate}
  \item $T(n) = T(n-a) + T(a) + n $ where $ a \geq 1 $ is constant.
  \item $T(n) = T(cn) + T((1-c)n) + n $ where $ 0 < c < 1 $ is a constant.
  \item \textbf{(Corrected 11/5/06)} $T(n) = T(2cn) + T((1-c)n) + n $
where $ 0 < c < 1/2 $ is a constant.
  \item $T(n) = 2T(n/2)+n log^2n $ (Hint: The approach to solving this is
  similar to the approach to solving $T(n) = 2T(n/2)+n$).
  \end{enumerate}

\item You are given an array of length $n$. You are told that there
is a value that appears in it exactly $n/2$ times, another value
that appears exactly $n/4$ times, another that appears exactly $n/8$
times, and so on. (note that you are not told what these values
are). Describe an algorithm for sorting this array that runs in time
$O(n)$.

\item \textbf{(Modified 15/5/06)} Show how to modify the Hash Table data structure, such that
all operations (find, insert and delete) take $O(\log n)$ time in
the worst-case. All operations should still take $O(1)$ time in
expectation. This question refers to the hash table data structure
that you learned in class, using universal hashing and chaining.
This does not refer to perfect hashing.

\item \textbf{(Modified 10/5/06)} Let $H$ be a Hash Table with $3n$ cells.
(where each cell has room only for a single element, that is,
without chaining). In case you insert into $H$ an element that
causes a collision, the element is inserted into an auxiliary linked
list, $L$. Suppose we insert $2n$ different elements into this Hash
Table. What is the expected length of $L$ after this sequence of
insertions?

\end{enumerate}

\end{document}
