\documentclass{article}
\usepackage{graphicx}

\begin{document}

\noindent CS140: Exam 2 \hfill 11/7/01 \\


\vspace{.2 in}
You have three hours to work on this exam.  You should return the exam to my office
within 20 minutes of your finish time.  The exam should be submitted no later than
8 AM, Sunday, Nov. 11, 2001.  

You may use a one page cheat sheet to help you on this exam.  You may not
consult any other texts or notes during this
exam.  You may not discuss the questions with anyone.
You may not use a calculator during the exam.

Your answers will be judged for clarity, conciseness, and correctness.  Algorithms and bounds
should be, respectively, as fast and as tight as possible.
The space provided should be adequate for your solutions.  

The exam consists of five problems and 11 pages.  Before you begin, make sure your exam is complete.
Then write your name and start time below.  When you complete the exam fill in your
stop time.

\vspace{.5 in}

\noindent Name \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~} \\
\vspace{.5 in}

\noindent I started this exam at \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}

\vspace{.5 in}

\noindent I finished this exam at \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
\vspace{1.5 in}


\pagebreak

\vspace{1 in}
\begin{enumerate}

\item
Consider the following flow network where the edge label $k/j$ indicates the
edge has flow $k$ and capacity $j$.
\vspace{.2 in}
\begin{figure}[h]
\centering
\includegraphics{netflow}
\end{figure}
\vspace{.2 in}
\begin{enumerate}
\item
Prove that the flow shown in the network is a feasible flow.
\vspace{1 in}
\item
Continue from the flow shown using the Ford-Fulkerson method to
find the maximum flow.
To receive credit you must show the residual graph and augmenting path
at each step. 
When you conclude, show a minimum capacity cut in the network.
\end{enumerate}
 
\pagebreak

\pagebreak
\item
Construct a graph $G$ with a vertex $s$ such that the shortest path tree for $s$ in $G$ is not a minimum spanning tree of $G$.

\pagebreak
\item
Let $G$ be a directed, acyclic graph with $n$ vertices.  A list $L$ of the
vertices of $G$ 
is said to be ``topologically sorted'' if it satisfies the following property:
For any vertices $w,z$ in $G$, 
if there is an edge from $w$ to $z$  then $z$ occurs  after
$w$ in $L$.  (Note:  $z$ need not occur immediately after $w$, just somewhere aafter.)  
\begin{enumerate}
\item
Consider the following directed, acylic graph.
\vspace{.2 in}
\begin{figure}[h]
\centering
\includegraphics{dag}
\end{figure}
\vspace{.2 in}


\noindent Which of the following lists are topologically sorted?

\begin{description}
\item[i.]
x,y,u,v
\item[ii.]
 y,x,u,v 
\item [iii.]
x,y,v,u 
\item[iv.]
y,x,v,u
\end{description}
\vspace{.2 in}

\item
Explain why it is always possible to topologically sort the vertices of a directed, acyclic graph.
\vspace{2 in}

\pagebreak
\item
Design an algorithm that takes a directed, acyclic graph as input and writes the vertices of that graph in topologically sorted order. (To receive full credit your algorithm should run in time $O(n+m)$.)
\end{enumerate} 
\pagebreak

\item

A Mealy machine is a finite automaton with a printing facility.
The machine begins in a specified state, called the start state.  In one step it reads the next symbol of the input, writes an output string, and transitions to its next state.  
Consider the Mealy machine shown in the following diagram. 
\vspace{.2 in}
\begin{figure}[h]
\centering
\includegraphics{mealy}
\end{figure}

\vspace{.2 in}
State A is the 
start state of the machine..  If the machine is in state A and reads a 0 then
it prints XXX and stays in state A.  This rule is described by the arrow from
state A to itself with the label 0/XXX.  A label ``b/s'' means on input symbol ``b'' print the string 
``s''.

Consider the input 1011.  The machine begins in state A and does
the following:
\begin{enumerate}
\item
Read first input symbol 1, print XYX, goto state B.
\item
Read next input symbol 0, print YXY, goto state A.
\item
Read next input symbol 1, print XYX, goto state B.
\item
Read next input symbol 1, print YYY, goto state B.
\end{enumerate}

When the input is exhausted the machine halts.  Thus on an input of
1011 the machines write the string XYXYXYXYXYYY.


\end{enumerate}

\end{document}
