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

\usepackage{graphicx}
 \usepackage{epstopdf}
 \usepackage{verbatim}
 \DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `basename #1 .tif`.png}

 

\newcommand{\excise}[1]{}
 
\newif\ifremark
\long\def\remark#1{
\ifremark%
   \begingroup%
   \dimen0=\textwidth
   \advance\dimen0 by -1in%
   \setbox0=\hbox{\parbox[b]{\dimen0}{\protect\em #1}}
   \dimen1=\ht0\advance\dimen1 by 2pt%
   \dimen2=\dp0\advance\dimen2 by 2pt%
   \vskip 0.25pt%
   \hbox to \textwidth{%
      \vrule height\dimen1 width 3pt depth\dimen2%
      \hss\copy0\hss%
      \vrule height\dimen1 width 3pt depth\dimen2%
   }%
   \endgroup%                        
\fi}

\begin{document}

\begin{center}
{ \Large \bf CMPU 241 - Analysis of Algorithms\\
   Spring 2020 \\
   Assignment \#4}\\
Due Friday, March 6th\\
\end{center}


\vspace{10mm}

\begin{enumerate}


\item For the input keys $<$12, 23, 75, 3, 32, 18, 82, 19, 41$>$ hash function $h'(k) = k \bmod 11$ and a hash table of length $m = 11$ (for parts (a) and (c)) and a hash table of length $m = 13$ with $h'(k) = k \bmod 13$ (for part (b)), illustrate the result of inserting these keys in the order shown using open addressing methods (a)--(c), below. For each case, show the result of each operation to place the key (i.e., show the remainder of key $k$ divided by $m$) and state the number of collisions. For full credit, ({\it fill in the final table values in the hash tables below and show all your calculations below the tables.}) 


\begin{enumerate}
\item[(a)] (5 points) Insert input keys $<$12, 23, 75, 3, 32, 18, 82, 19, 41$>$ using linear probing.\\



\begin{center}
\begin{tabular}{ c c c c c c c c c c c }
 \ \ 0\ \ \ \ & \ 1 \ \ \ & 2 \ \ \ \ & 3 \ \ \ \ & 4\ \ \ \ & 5 \ \ \ \ & 6 \ \ \ \ & 7\ \ \ \ &8 \ \ \ \ & 9 \ \ \ \ & 10\ \ \ \\
\hline
\end{tabular}
\begin{tabular}{| c | c | c | c | c | c | c | c | c | c | c |}
\hspace{.245in} &  \hspace{.245in} &  \hspace{.245in} &  \hspace{.245in} & \hspace{.245in} &  \hspace{.245in} &  \hspace{.245in} & \hspace{.245in} & \hspace{.245in} &  \hspace{.245in} & \hspace{.245in}  \\
 \ \ \ &  \ \ \ &  \ \ \ &  \ \ \ & \ \ \ &  \ \ \ &  \ \ \ & \ \ \ & \ \ \ &  \ \ \ &  \\
\hline
\end{tabular}
\end {center} 

\vspace{1.75in}


\item [(b)] (5 points) Insert input keys $<$12, 23, 75, 3, 32, 18, 82, 19, 41$>$ using quadratic probing with the $i^{th}$ probe $h(k, i) = (h'(k) + c_1i + c_2i^2)$ mod $m$, where $c_1 = 1$ and $c_2 = 3$. Note: The table size for this part is 13, with hash function $h'(k) = k \bmod 13$.\\ 

\begin{center}
\begin{tabular}{ c c c c c c c c c c c c c}
 \ \ 0\ \ \ \ & \ 1 \ \ \ & 2 \ \ \ \ & 3 \ \ \ \ & 4\ \ \ \ & 5 \ \ \ \ & 6 \ \ \ \ & 7\ \ \ \ & 8 \ \ \ \ & 9 \ \ \ \ & 10\ \ \ & 11\ \ \ & 12\ \ \ \\
\hline
\end{tabular}
\begin{tabular}{| c | c | c | c | c | c | c | c | c | c | c | c | c |}
\hspace{.245in} &  \hspace{.245in} &  \hspace{.245in} &  \hspace{.245in} & \hspace{.245in} &  \hspace{.245in} &  \hspace{.245in} & \hspace{.245in} & \hspace{.245in} &  \hspace{.245in} & \hspace{.245in}  & \hspace{.245in} &
 \hspace{.245in} \\
 \ \ \ &  \ \ \ &  \ \ \ &  \ \ \ & \ \ \ &  \ \ \ &  \ \ \ & \ \ \ & \ \ \ &  \ \ \ &  \ \ \ & \ \ \ &\\
\hline
\end{tabular}
\end {center} 


\vspace{2.25in}

\item[(c)] (5 points) Insert input keys $<$12, 23, 75, 3, 32, 18, 82, 19, 41$>$  using double hashing with $h_1(k) = h'(k)$, $h_2(k) = (k \bmod (m - 1))$, and the $i^{th}$ probe $h(k, i) = (h_1(k) + h_2(k)i) \bmod m$.\\ 

\begin{center}
\begin{tabular}{ c c c c c c c c c c c}
 \ \ 0\ \ \ \ & \ 1 \ \ \ & 2 \ \ \ \ & 3 \ \ \ \ & 4\ \ \ \ & 5 \ \ \ \ & 6 \ \ \ \ & 7\ \ \ \ &8 \ \ \ \ & 9 \ \ \ \ & 10\ \ \ \\
\hline
\end{tabular}
\begin{tabular}{| c | c | c | c | c | c | c | c | c | c | c |}
\hspace{.245in} &  \hspace{.245in} &  \hspace{.245in} &  \hspace{.245in} & \hspace{.245in} &  \hspace{.245in} &  \hspace{.245in} & \hspace{.245in} & \hspace{.245in} &  \hspace{.245in} & \hspace{.245in}  \\
 \ \ \ &  \ \ \ &  \ \ \ &  \ \ \ & \ \ \ &  \ \ \ &  \ \ \ & \ \ \ & \ \ \ &  \ \ \ &  \\
\hline
\end{tabular}
\end {center} 



\end{enumerate}

\vspace{3in}



\item (10 points)
In a programming language of your choice (well documented, preferably Java), write code to confirm your results for 
problem 1. For
each of the 3 open-addressing collision resolution algorithms (linear and quadratic probing and double hashing), write
code to implement the program with the given inputs and table sizes.  In particular, what happens in the quadratic
probing case when the table size is 11?\\

Your program should output the final placement of numbers in the hash table, the number of collisions, and as much 
intermediate data as you want (e.g., keys that have collisions, probe numbers, and results of rehashing).\\ 

Test your code on the data given for problem 1 and also on this data set: 10, 22, 31, 4, 15, 28, 17, 88, 59. 

\newpage
\item (5 points) For the input keys $<$1, 12, 4, 43, 18, 22, 9, 81, 25, 7, 42, 16, 24, 41, 77 $>$ and hash function $h'(k) = k \bmod 11$, show how the keys would be distributed if they are inserted in the order shown when using chaining to resolve collisions. Fill in the table to depict the final array of lists.\\

%What is the load factor $\alpha$ on the resulting table?

\begin{center}
\begin{tabular}{ c c c c c c c c c c c}
 \ \ 0\ \ \ \ & \ 1 \ \ \ & 2 \ \ \ \ & 3 \ \ \ \ & 4\ \ \ \ & 5 \ \ \ \ & 6 \ \ \ \ & 7\ \ \ \ &8 \ \ \ \ & 9 \ \ \ \ & 10\ \ \ \\
\hline
\end{tabular}
\begin{tabular}{| c | c | c | c | c | c | c | c | c | c | c |}
\hspace{.245in} &  \hspace{.245in} &  \hspace{.245in} &  \hspace{.245in} & \hspace{.245in} &  \hspace{.245in} &  \hspace{.245in} & \hspace{.245in} & \hspace{.245in} &  \hspace{.245in} & \hspace{.245in}  \\
 \ \ \ &  \ \ \ &  \ \ \ &  \ \ \ & \ \ \ &  \ \ \ &  \ \ \ & \ \ \ & \ \ \ &  \ \ \ &  \\
\hline
\end{tabular}
\end {center}

\vspace{1in}

%\item 

\end{enumerate}


\end{document}



