%%% Fall 2004, HMW 4
\documentclass[11pt]{article}
 
\usepackage{epsf}
\usepackage{pslatex}

\setlength {\topmargin}{0in}
\setlength {\headheight}{0in}
\setlength {\headsep}{0cm}
\setlength {\textheight}{9in}
\setlength {\oddsidemargin}{0in}
\setlength {\evensidemargin}{0in}
\setlength {\textwidth}{6.5in}
\setlength {\parskip}{0cm} 


\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\begin{document}
\thispagestyle{empty}

\begin{center}
{\bf \large ECE G205 Fundamentals of Computer Engineering} \\
{\bf Fall 2003} \\[0.5cm]
{\large \bf Homework 4: Due by Wednesday October 13 2004} \\
\end{center}

{\large
\vspace*{2cm}\noindent
\begin{itemize}

\item This test contains $2$ problems. They allow you to earn
$100$ points.

\item Show your work, as partial credit can be given. You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it. \textbf{Be neat}.

\item {\bf No late submissions will be accepted.}

\item Only homework returned in a 9in $\times$ 12in envelope
will be accepted. (If you cannot find such envelope, ask the
Instructor.) Please, write your name and the class name (ECE
G205) on the envelope (write clearly, please).

\item For the two problems an e-mail to the TA should be sent that
contains the code and the executable of a (single) program that
implements the solutions to the problems as functions.

\end{itemize}


\vspace*{3cm}
Write your name here:\ 
\hrulefill
}


\setcounter{page}{0}

%----------------------------------------------------------------------
\newpage
\begin{itemize}

\item {\bf Problem \# 1\ \ [70 points]}. Describe how storage for 
elements can be allocated and deallocated within a hash table by
linking all unused slots into a free list. Assume that a slot can 
store a flag and either one element plus a pointer or two pointers.
All dictionary and all list operations should run in $O(1)$ expected 
time. Does the free list need to be doubly linked, or does a singly
linked free list suffice?



%----------------------------------------------------------------------
\newpage
\item {\bf Problem \# 2\ \ [40 points]}. Implement stacks and queues 
as seen in class in C++ using the C++ Standard Template Library container 
\texttt{vector}. Include tests for underflow and overflow conditions.


\end{itemize}

\end{document}
