\documentstyle[11pt,psfig]{article}

\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}

\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcounter{questnum}
\newcommand{\question}[1]{
\vspace{.1in}
  \refstepcounter{questnum}
{\bf \medskip Problem \thequestnum: }}

\newcommand{\titledquestion}[2]{
 \refstepcounter{questnum}
{\bf \medskip Problem \thequestnum:} #2 {\normalsize (#1 pts) \\}}

\newcommand{\answerspace}{\verb+                                  +
\underline{\makebox[2.0in]{}}}
\newcommand{\smanswerspace}{\underline{\makebox[0.5in]{}}}

\setlength{\topmargin}{-0.5 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{8.75 in}
\setlength{\textwidth}{6.5 in}
\setlength{\parindent}{0.0 in}

\begin{document}

{\large 
CS294-3: Algorithms in the real world \hfill Assignment 5 (VLSI and Pattern Matching)\\[.03in]
Due: Friday Nov 21, 1997\\[.1in]
}

Please feel free to send me email if there are any ambiguous questions.

\question{??}
Consider the following graph.\\

\centerline{\psfig{file=steiner.ps}}
\begin{description}
\item[A.] Find a minimum cost Rectilinear Steiner Tree (RST) for the following
set of points (the shaded points are the demand points).
\item[B.] Is this an S-RST?  If not show the minimum cost S-RST.
\end{description}

\question{??}
For the following routing problem the three nets $A, B$ and $C$ need
to be connected.
The numbers on the edges represent their lengths, and
assume that the capacity of every edge is 2.\\  

\centerline{\psfig{file=iprog.ps,width=1.8in}}
\begin{description}
\item[A.] Specify an integer (0-1) program for which the solution
gives the minimum total wire length.

\item[B.] Solve the program (you do not need to show your work).
\end{description}

\question{??}
Describe an $O(nm)$ time $O(n + m)$ space algorithm for finding
a minimum cost alignment assuming an affine gap cost model.
Pseudocode with comments would be the best way to describe it.

\question{??} ({\bf Extra Credit.})
Describe an $O(nm \log (m + n))$ time algorithms for finding a minimum
cost alignment assuming the gap cost function $x(k)$ (where $k$ is the length
of the gap) is concave downward
({\em i.e.} the second derivative is always negative).

\end{document}
