\documentstyle[12pt]{article}

\pagestyle{myheadings}
\def\headlineaux{\sc Math 540 T: Algorithm Design and Analysis
\hrulefill
}
\markboth{\headlineaux}{\headlineaux}

\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burton Rosenberg}}
\end{centerline}\end{titlepage}

\section*{Test 2 \hfill{\parbox{3in}
    {\small\sc\begin{flushright} April 28, 5:00--6:15 \end{flushright}}}}

There are five problems each counting equally.
~\\[.25in]
{\Large Name: \hrulefill}
\\[.5in]

\begin{center}{
{\Large
\begin{tabular}{c|c}
Problem & Credit \\ \hline\hline
 1 & \\ \hline 2 & \\ \hline 3 & \\ 
 \hline 4 & \\ \hline 5 & \\ \hline\hline
  Total & \end{tabular} 
}}
\end{center}

\vfill
\parbox{3.5in}{
\em On my honor, I have neither given nor received
aid on this examination-assignment.\\
~\\
Signature: \hrulefill
}


\newpage
\begin{enumerate}
\item {\sc [Network Flows]}
Negative Cycles

You are given a network $G(V,E)$ with edge costs $w(e)$ for
any $e\in E$. These costs can be negative or positive. You
would like to find out if there exists a cycle of edges in $G$
such that the weight summed over the edges in the cycle is negative.

Express this as a condition on a network transport problem.
\newpage

\item {\sc [Maximum Matching]}
Find a maximum matching and minimum cover in the following graph:
\[\begin{picture}(0,0)(200,300)
\put(100,200){\line(1,0){100}}
\put(100,200){\line(2,-1){100}}
\put(100,200){\line(1,-1){100}}
\put(100,200){\line(2,-3){100}}
\put(100,150){\line(1,0){100}}
\put(100,100){\line(2,1){100}}
\put(100,50){\line(2,3){100}}
\put(100,50){\line(1,1){100}}
\put(100,50){\line(2,1){100}}
\put(100,50){\line(1,0){100}}
\put(100,50){\circle*{10}}
\put(100,100){\circle*{10}}
\put(100,150){\circle*{10}}
\put(100,200){\circle*{10}}
\put(200,50){\circle*{10}}
\put(200,100){\circle*{10}}
\put(200,150){\circle*{10}}
\put(200,200){\circle*{10}}
\end{picture}\]
\newpage

\item {\sc [Node Costs and Tree Feasible Solutions]}
Give a spanning tree and assign costs, $\{\,y_v\,|\,v\in V\,\}$
to the following network. {\em Assume all edge costs are 1.}

\[\begin{picture}(0,0)(200,300)
\put(150,250){\vector(2,-1){90}}
\put(150,250){\vector(-2,-1){90}}
\put(250,200){\vector(-1,0){190}}
\put(150,150){\vector(0,-1){90}}
\put(150,150){\vector(-2,1){90}}
\put(150,150){\vector(2,1){90}}
\put(150,50){\vector(2,-1){90}}
\put(50,200){\vector(0,-1){190}}
\put(50,0){\vector(1,0){190}}
\put(50,0){\vector(2,1){90}}
\put(250,0){\vector(0,1){190}}
\put(150,250){\circle*{10}}
\put(50,200){\circle*{10}}
\put(250,200){\circle*{10}}
\put(150,150){\circle*{10}}
\put(150,50){\circle*{10}}
\put(50,0){\circle*{10}}
\put(250,0){\circle*{10}}
\end{picture}\]

\newpage

\item {\sc [Applications]}
Setup the following problems as a network transport problem.

You are given a network of computers, that is, a graph $G=(V,E)$
where $V$, the set of nodes, represent computers, and $E$, the set
of edges, giving communication pathways between computers. 
Each edge $e\in E $ has a weight, $w(e)$,
giving the costs of communication across the pathway.
Some of the computers are servers, which we represent as a subset $S$
of $V$. Each non-server, $v\in V \backslash S$ has a demand for
disk blocks $b(v)$.
A non-server computer $v\in V \backslash S$ 
will get its blocks over the network from
a server by selecting a path to a nearby server, call it  $P(v)$,
and paying $w(v) b(v)$, where $w(v)$ 
is the sum of the weights of all edges in the path $P(v)$:
\[    w(v) = \sum_{e\in P(v)} w(e).\]

The total disk blocks demanded is:
\[ D = \sum_{v\in V \backslash S} b(v).\]
You are to allocate the $D$ blocks to the servers in $S$ such that
the total communication costs are lowest, summed over all non-server
computers:
\[  \sum_{v\in V \backslash S} w(v).\]
\newpage

\item {\sc [Theory]}
Prove that a connected graph on $n$ vertices is a tree if
and only if it has $n-1$ edges.
\newpage

\end{enumerate}
\end{document}

