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

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

\newcommand{\emax}{\mbox{{\sc Extract-Max}}}
\newcommand{\ins}{\mbox{{\sc Insert}}}
\newcommand{\enq}{\mbox{{\sc Enqueue}}}
\newcommand{\deq}{\mbox{{\sc Dequeue}}}
\newcommand{\ind}{\mbox{{\it in-degree}}}
\newcommand{\Adj}{\mbox{{\it Adj}}}


\head{1390}{Algorithms}{Winter 2001}{8 March 2001}{19}

\begin{center}
\Large{\bf Sample Solution to Problem Set 4}
\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 Answer:} The two hashing techniques yield the following results:

\begin{itemize}
\item {\bf Linear probing:} The key $10$ goes into location $10$, $22$
  into $0$, $31$ into $9$, $4$ into $4$, $15$ after colliding with $4$
  goes into location $5$, and so on.  The final result is:

\[ [22 , 88 , \mbox{X} , \mbox{X}, 4 , 15 , 28 , 17 , 59 , 31 , 10].\]

\item {\bf Double hashing:}

\[ [22 , \mbox{X}, 59 , 17 , 4 , 15 , 28 , 88 , \mbox{X} , 31 , 10].\]

The ``\mbox{X}'' represents an empty slot.
\end{itemize}

{\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 Answer:} Consider the graph that just consists of the path $v
\rightarrow u \rightarrow w$.  Suppose the order of vertices in {\sc
DfsSweep} is $w, u, v$.  So we start the depth-first search at $w$,
i.e., call {\sc Dfs}$(w)$ first.  Then since there are no edges coming
out of $w$, $w$ forms a depth-first search tree all by itself.  We
next call {\sc Dfs}$(u)$.  Since $w$ is already colored black and
there are no other edges out of $u$, $u$ forms a depth-first search
tree all by itself.  Thus, even though $u$ has both an incoming edge
as well as an outgoing edge, $u$ ends up in a depth-first search tree
by itself.  Finally, we call {\sc Dfs}$(v)$, and it too forms a
depth-first tree all by itself.

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

{\bf Answer:} Let $n$ and $m$ denote the number of vertices and edges,
respectively.  The algorithm begins by first finding the in-degree of
all vertices.  For this we initialize the in-degrees to zero and then
go through all of the edges and increases the increment the in-degrees
of the heads of the edges by $1$.
\begin{tabbing}
1. \= \algfor\ \= $u \in V$\\
2. \> \> $\ind[u] \leftarrow 0$\\
3. \> \algfor\ $u \in V$\\
4. \> \> \algfor\ \= $v \in \Adj[u]$\\
5. \> \> \> $\ind[v] \leftarrow \ind[v] + 1$
\end{tabbing}
This takes $\Theta(n + m)$ time, since $n$ adjacency lists are
accessed and $m$ edges found.  We keep the vertices with in-degree $0$
in a FIFO queue, so that they can be enqueued and dequeued in $O(1)$
time.
\begin{tabbing}
6. \= $Q \leftarrow \emptyset$\\
7. \> \algfor\ \= $u \in V$\\
8. \> \> \algif\ \= $\ind[u] = 0$\\
9. \> \> \> $\enq(Q, u)$
\end{tabbing}
This takes $\Theta(n)$ time.  As we process each vertex from the
queue, we effectively remove its outgoing edges from the graph by
decrementing the in-degree of each vertex one of those edges enters,
and we enqueue any vertex whose in-degree goes to $0$.  Each vertex is
enqueued/dequeued at most once because it is enqueued only if it
starts out with in-degree $0$ or if its in-degree becomes $0$ after
being decremented (and never incremented) some number of times.
\begin{tabbing}
10. \= \algwhile\ \= $Q \neq \emptyset$\\
11. \> \> $u \leftarrow \deq(Q)$\\
12. \> \> output $u$\\
13. \> \> \algfor\ \= $v \in \Adj[u]$\\
14. \> \> \> $\ind[v] \leftarrow \ind[v] - 1$\\
15. \> \> \> \algif\ \= $\ind[v] = 0$\\
16. \> \> \> \> $\enq(Q, v)$
\end{tabbing} 
The processing of a vertex from the queue happens $\Theta(n)$ times
because every vertex is enqueued once.  The other work (dequeue and
output) takes a total of $\Theta(n)$ time.  Since each adjacency list
is scanned once (the for-loop in line 13), the total time spent
scanning the edges is $\Theta(m)$.  The overall running time of the
algorithm is $\Theta(n + m)$.

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

{\bf Answer:} Assume first that the graph is connected.  We perform a
breadth-first search of the given undirected graph $G$, starting from
an arbitrary vertex $s$.  The bfs traversal assigns a {\em level}\/ to
each vertex in $G$; this level is the distance (in number of hops)
from $s$ to $v$.  We note that every edge of $G$ is between two nodes
that are either in the same level or in consecutive levels.  We claim
that $G$ is bipartite if and only if there is no edge $(u,v)$ such
that $u$ and $v$ are in the same level.

We now prove the above claim.  We need to prove both the directions of
the claim.  Suppose first that $G$ is a bipartite graph and yet there
is an edge $(u,v)$ such that $u$ are in the same level.  We will
derive a contradiction.  Let $w$ be the {\em least common ancestor} of
$u$ and $v$; that is; $w$ is an ancestor of both $u$ and $v$ that has
the highest level number.  We note that such a vertex exists since the
vertex $s$ itself is an ancestor of both $u$ and $v$.  Since $w$ is an
ancestor of both $u$ and $v$, it follows that there is path $w, w_1,
w_2, \ldots, w_k, u$ and a path $w, w'_1, w'_2, \ldots, w'_k, v$ in
the breadth-first search tree.  Note that both the paths are of the
same length.  Since $G$ is assumed to be bipartite, we find that one
of the subsets of the partition contains $w, w_2, w'_2, w_4, w'_4,
\ldots$ and the other contains $w_1, w'_1, w_3, w'_3, \ldots$.  Since
$w_k$ and $w'_k$ are in the same subset of the partition, say $A$, it
follows that $u$ and $v$ are both in the other subset of the
partition, say $B$.  But we have an edge $(u,v)$ in the graph, which
contradicts the fact that $G$ is bipartite.

We now prove the other direction.  Suppose the breadth-first search
satisfies the condition that there is no edge $(u,v)$ such that $u$
and $v$ are at in the same level.  Then, we can assign all nodes at
odd levels to one subset of the partition, say $A$, and all nodes at
even levels to the other subset of the partition, say $B$.  Since
there are no edges between nodes in the same level, and all edges go
between consecutive levels, it follows that all edges go between an
odd level and an even level.  Thus, all edges go between a vertex in
$A$ and a vertex in $B$.  This shows that the graph is bipartite.

The above proof suggests the following algorithm for determining
whether a given connected graph $G$ is bipartite: (i) Find a
breadth-first search of $G$ starting from an arbitrary vertex $s$,
assigning levels (the $d[]$ values that we had assigned in the
algorithm studied in class); (ii) Check for every edge $(u,v)$ whether
$d[u] \neq d[v]$; (iii) If the check succeeds for every edge, then
return true, otherwise, return false.

Suppose the number of vertices is $n$ and the number of edges is $m$.
Then the running time of step~(i) is $\Theta(n + m)$.  The running
time of steps~(ii) and~(iii) is $\Theta(m)$.  Therefore, the overall
running time is $\Theta(n + m)$.

We finally consider the case when the graph may be unconnected.  In
this case, we do a {\em breadth-first search sweep}.  We start from
the bfs from an arbitrary vertex.  After the termination, we select an
arbitrary undiscovered vertex and start another bfs from that vertex,
and so on until all the vertices are discovered.  This process is
similar to the dfssweep procedure.  The remainider of the algorithm is
the same.  (Essentially, we are traversing the different connected
components of the graph.)


{\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.

{\bf Answer:} We consider any edge $(u,v)$ as two directed edges
(arcs) $\langle u, v \rangle$ and $\langle v, u \rangle$.  We first
obtain a depth-first search of the graph, starting from an arbitrary
vertex $s$.  Since the graph is connected, this traversal visits every
vertex and edge in the graph.  Furthermore, the depth-first search
also classifies the edges as tree and back.  (Note that since the
graph is undirected, there are no forward or cross edges.)

We need to find a path that goes through every edge in each direction
exactly once.  We first note that using the depth-first search tree,
we can easily find a path starting from the root $s$ that goes through
every {\em tree edge} exactly once in each direction.  In order to add
the back edges, we do the following: if $(u,v)$ is a back edge from
descendant $u$ to ancestor $v$, after the completion of {\sc Dfs}$(u)$
and before returning to {\sc Dfs}$(u)$, we go through the edge in both
directions.

We now describe the algorithm in more detail.  We maintain a path $P$
during the depth-first search algorithm, which will finally consist of
all edges in both directions exactly once.  We initially set $P$ to
nil.  A call to {\sc Dfs}$(u)$ goes through every edge $(u,v)$
adjacent to $u$.  If $v$ is {\sc White}, then the depth-first search
sets the parent of $v$ to $u$ and calls {\sc Dfs}$(v)$.  In the
modified algorithm, we add arc $\rangle u, v \rangle$ to $P$ just
before calling {\sc Dfs}$(v)$.  If $v$ is {\sc Gray}, then there are
two cases: (i) if $v$ is the parent of $u$, then we do nothing; (ii)
if $v$ is not the parent of $u$ (i.e., $(u,v)$ is a back edge), we add
the arcs $\langle u, v \rangle$ and $\langle v, u \rangle$ in this
order to $P$.  If $v$ is {\sc Black}, then $v$ has already finished;
this implies that $(v, u)$ is a back edge that we have already
explored in each direction when we were performing {\sc Dfs}$(v)$.  So
we do nothing.  When {\sc Dfs}$(u)$ completes, we add $\langle u,
\mbox{parent}[u] \rangle$ to $P$.

If $m$ is the number of edges, then the above algorithm takes $O(m)$
time, since each edge is explored exactly twice.

A maze can be modeled by a connected undirected graph with two special
nodes.  One is the node where you are currently trapped; let this node
be $s$.  The other is the node, which indicates the exit of the maze;
let this be denoted by $f$.  We can use the above exploration
algorithm to find our way through the maze.  We use two pennies for
each node (intersection point on the maze) that we visit and two
pennies for each edge that we explore (one for each direction).  Our
path starts from $s$.  When we visit a node (an intersection) for the
first time, we place a penny at the center.  Thus, if we visit a node
that has a penny, then its color is {\sc Gray}; if we visit a node
that has no penny, then its color is {\sc White}.  When we finish
exploring all edges out of a node, then we place 2 pennies indicating
that it is {\sc Black}.  Every time we explore an edge from a node
$u$, we place a penny on that edge close to $u$.  We ensure that we
never explore an edge, say $(u,v )$, in the same direction, say $u
\rightarrow v$, twice by checking whether a penny is placed on that
edge close to $u$.  If no penny is placed, then we can explore this
edge and continue on our path; otherwise, we need to pick another yet
unexplored edge.  Finally, we also need to keep track of the parent
for each node.  Suppose we are exploring node $v$ from $u$ for the
first time.  Thus, $u$ is the parent of $v$ in the depth-first
traversal.  We can encode this by placing an extra penny on the edge
$(u,v)$.

Using the exploration algorithm above, we can find a path that goes
through every edge exactly once in each direction.  Certainly, at some
point, this path will go through the exit node of the maze.  At this
point, we can exit the maze.

\junk{
\begin{tabbing}
1. \= \algfor\ \= each edge $(u,v)$\\
2. \> \> mark $\langle u, v \rangle$ and $\langle v, u \rangle$ as
``unexplored''
3. \> set $u$ to any vertex $s$ in the graph
4. \> set $P$ to nil
4. \> \algwhile\ \= there is an ``unexplored'' arcs $\langle u,
v \rangle$ 
5. \> \> mark $\langle u, v \rangle$ as ``explored''
6. \> \> add $\langle u, v \rangle$ to $P$
7. \> \> $u \leftarrow v$
8. \> \algreturn\ $P$
\end{tabbing}
Since the original graph $G$ is undirected, number of arcs $\langle v,
u \rangle$ coming into a vertex $u$ is exactly the same as the number
of arcs coming out of $u$.  Therefore, whenever we enter a vertex $u
\neq s$ through an arc, say $\langle v, u \rangle$, there exists an
unexplored arc $\langle u, w \rangle$ out of $u$.  It follows that 
}
\end{document}
