\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{courseMacros}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 2001}{20 February 2001}{16}

\begin{center}
\Large{\bf Problem Set 4 (due March 1)}
\end{center}

{\bf 1. (15 points)} Consider inserting the keys 10, 22, 31, 4, 15,
28, 17, 88, 59 into a hash table of length $m = 11$ using open
addressing with the first (primary) hash function $f(k) = k \bmod m$.
Illustrate the result of inserting these keys using (i) linear
probing; and (ii) using double hashing with the second hash function
$g(k) = 1 + (k \bmod (m - 1))$.

{\bf 2. (5 points)} Give an example of a directed graph $G$ in which
a vertex $u$ of $G$ ends up in a depth-first tree containing only $u$,
even though $u$ has both incoming and outgoing edges.  Your example
graph must have no self-loops.

{\bf 3. (20 points)} Exercise 7.21, page 379.

{\bf 4. (20 points)} Exercise 7.48, page 384.

{\bf 5. (20 points) Finding your way out of a maze}

Given a connected undirected graph $G$, design an efficient algorithm to
find a path in $G$ that goes through each edge exactly once in each
direction.  Argue the correctness of your algorithm and analyze its
running time.  Describe how you can find your way out of a maze if you
are given a large supply of pennies.
\end{document}
