\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
9 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 nine 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
Continuing from the flow shown, use the Ford-Fulkerson method to
find the maximum flow of the network.
To receive credit you must show the residual graph and augmenting path
at each step. 
When you conclude, give a minimum capacity cut in the network.
\end{enumerate}
 
\pagebreak

(Use this page for problem 1.)

\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 after.)  
\begin{enumerate}
\item
Consider the following directed, acyclic 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
You have $n$ papers to write during the rest of the semester.
 The deadline for the $i$th
paper is $d_i$ days from now, where $d_i \le d_{i+1}$.  (Note:  You may
have several papers due on some days and none on other days).
You are an outstanding writer and will certainly get an A 
for any paper that is finished on time. Every paper you turn in after
the deadline will garner a C.   You
decide you can and will write exactly one paper a day until all $n$ papers are
written.
You need to figure out a strategy for choosing which paper to write
each day so as to maximize your grade.

\pagebreak

\item
Suppose we want to send a binary string across a noisy communication channel.
The channel never drops or adds bits to a message but may change a 0 to a 1
or a 1 to a 0.
We could use an error-correcting code; e.g.let 111 be the codeword for a 1 and let 000 be the codeword for a 0.  Using this code,
the string 101 is encoded and transmitted as 111000111. Now we can
 detect and correct a single error in 
in any codeword; e.g. if we received 111000110, the string would be corrected 
to 111000111 and decoded
to 101.

One way of encoding strings for error correction is by a Mealy machine.
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 string $b$, writes the encoding for $b$, 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 000 and stays in state A.  This rule is described by the arrow from
state A to itself with the label 0/000.  A label ``b/s'' means on input symbol ``b'' print the encoding
``s''.  Thus for input 1011 the machine outputs the code 110001110111.
(The state transitions are A$\rightarrow$B$\rightarrow$A$\rightarrow$B$\rightarrow$B.)

\begin{enumerate}
\item
What is the output of the Mealy machine on input  $01101$?  On input
$11101$?
\vspace{.2 in}
\item
Suppose 110111111 is output by the Mealy machine.  What was the input?
\vspace{.2 in}

\pagebreak
\item
Suppose an encoding is transmitted and received as
010111. Since this is not the valid encoding of any string, we can infer
an error was made.  Construct the encodings of 00, 01, 10 and 11.  Which
is closest to the received string, where by closest we mean the one
that differs in the fewest positions.

\vspace{1 in}
\item
Give a recursive algorithm that that finds the closest valid encoding to a
received string $b_0b_1 ... b_m$, where $m$ is a power of 3. (Hint:  You'll
want to strengthen the inductive hypothesis to consider the state of the
Mealy machine!)  At this point you needn't worry about efficiency.

\pagebreak
\item
Give an efficient dynamic programming algorithm for th problem described
in the last section.
\end{enumerate}
\end{enumerate}

\end{document}
