\documentclass[11pt]{article}
\usepackage{handout2e}
\usepackage[pdftex]{graphicx}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\input{epsf}

\newif\ifexam
\examtrue
%\examfalse

\ifexam
\newcommand{\answer}[1]{}
\else
\newcommand{\answer}[1]{{\bf Answer:} #1}
\fi

\ifexam
\head{CSU690}{Algorithms and Data}{Fall 2006}{14 December 2006}{21}
\else
\head{CSU690}{Algorithms and Data}{Fall 2006}{14 March 2005}{22}
\fi

\ifexam
\begin{center}
\Large{{\bf Final}} 
\end{center}
\else
\begin{center}
\Large{{\bf Sample Solution to Final}} 
\end{center}
\fi

\ifexam
{\bf Instructions.}
\begin{itemize}
\item This is an open-book, open-notes, 120 minute final exam.

\item
Read all the problems through first and attack them in the order that
allows you to make the most progress.  There are 4 questions worth a
total of 35 points and a bonus problem worth 4 points.

\item 
While describing an algorithm, you may use any of the algorithms
  covered in class or in the text as a subroutine.  You need to
  provide a proof of correctness and/or an analysis of the running
  time only for those problems where they are explicitly required.

\item
Show your work, as partial credit will be given.  If you need extra
space, use the blank facing page.

\item
Best of luck!
\end{itemize}

\vfill

{\Large
\begin{center}
\begin{tabular}{||c|c|c||}\hline
Question & Score & Maximum \\ \hline
1 & & 10 \\ \hline
2 & & 7\\ \hline
3 & & 10 \\ \hline
4 & & 8 \\ \hline
Bonus & & 4 \\ \hline
Total & & 35 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

\begin{center}
{\bf Name:} {\vrule height0.4pt width3in}
\end{center}
\vfill
\vfill


\newpage
\fi


{\bf Problem 1. (2 + 2 + 3 + 3 = 10 points) \hs Finding pairs in a list} 

Consider a set $S$ of $n\geq 2$ distinct integers given in unsorted
order.  Each of the following three problems asks you to give an
algorithm to determine two distinct integers $x$ and $y$ in the set
$S$ that satisfy a stated condition.  Briefly describe your algorithm
and justify its running time.
\begin{itemize}
\item[{\bf (a)}] In $O(n)$ time, determine $x,y \in S$ such that 
\[
|x - y | \geq |w-z|
\]
for all $w,z \in S$.  That is, determine two numbers that are as far
apart as any two numbers in the set.

\answer{The two numbers are the maximum and minimum of $S$.  Finding
them takes $O(n)$ time.}
\vfill

\item[{\bf (b)}] In $O(n\log n)$ time, determine $x,y\in S$
such that $x\neq y$ and
\[
|x-y|\leq |w-z|
\]
for all $w,z\in S$ such that $w\neq z$.  That is, determine two
numbers that are as close together as any two numbers in the set.

\answer{Sort $S$.  Scan through $S$ maintaining the smallest distance
between consecutive numbers processed, and output the minimum.}
\vfill

\newpage 

\item[{\bf (c)}] In $O(n)$ expected time, determine $x,y\in S$ such
that $x\neq y$ and
\[
x+y= Z
\]
where $Z$ is given, or determine that no such pair exists.  {\em
Hint:} Use hashing.

\answer{Store each element in an $O(n)$ size hash table.  For each $x$
in $$S, search for $Z -x$ in the hash table, and return $(x,Z-x)$ if
this number exists in the table.  Each insert and lookup operation
takes expected $O(1)$ time, for a total of $O(n)$ expected time.} \vfill

\newpage

\item[{\bf (d)}] In $O(n)$ expected time, determine $x, y \in S$ such
that
\[
|x - y| \le Z
\]
where $Z$ is a given integer, or determine that no such pair exists.
{\em Hint:} Use hashing.  

\answer{We compute a new array $T$ in which we have an entry $(\lfloor
x/Z \rfloor, x)$ for each $x$ in $S$.  We store $T$ in an $O(n)$ size
hash table, by hashing on the first coordinate.  

(1) For each $(q,x)$ in $T$, check whether there is more than one
entry with same key $q$.  If yes, then we return two numbers $x$ and
$y$ such that $|x - y| \le Z$ since their quotients, when divided by
$Z$, are the same.

(2) If we complete (1) without returning, then for each $(q,x)$ in
$T$, we check whether there is an entry with key $q-1$.  If yes, then
there can only be one entry since otherwise we would have terminated
in step (1).  Let this entry be $(q-1,y)$; return $x$ and $y$ if $x -
y \le Z$.

(3) If we do not return anything in step (2), return ``no pair found''.

The total number of insert operations is $n$ and the total number of
lookup operations is $2n$.  Each insert and lookup operation takes
$O(1)$ expected time, so the total expected time is $O(n)$.
}\vfill
\end{itemize}

\newpage

{\bf Problem 2. (7 points)\hs Vertex cover in trees}

A {\em vertex cover}\/ of a graph is a set $C$ of vertices such that
for every edge, at least one of the end points of the edge is in $C$.
For instance, in the tree given in the figure below, the set $\{A, F,
G, H\}$ forms a vertex cover, while the set $\{A, C, D, E, I, J\}$
does not since none of the endpoints of the edges $(B,G)$ and $(B,H)$
are in the set.  The smallest vertex cover is given by the set $\{A,
B, F\}$.

\begin{figure}[h]
\centerline{\epsfxsize = 2in \epsffile{tree.eps}}
\label{fig:k-or}
\end{figure}

Give a polynomial-time algorithm to compute a smallest vertex cover of
a given tree.

({\em Hint:} One approach to solve this is dynamic programming.)

\newpage

{\bf Problem 3 (2 + 2 + 3 + 3 = 10 points) \hs}
\begin{itemize}
\item[{\bf (a)}] Prove or disprove: In every directed acyclic graph,
there is at least one node that has no incoming edge and at least one
node that has no outgoing edge.

\vfill

\item[{\bf (b)}] Let $G$ be a graph with distinct weights on edges,
and let $e$ be the maximum-weight edge of $G$.  Under what conditions
does $e$ belong to a minimum spanning tree of $G$?

\vfill
\newpage
\item[{\bf (c)}] In an RSA cryptosystem, let $p = 5$ and $q = 17$, so
that $N = 85$.  If the public exponent is $e = 3$, then determine the
private exponent $d$.  Show your work.

\vfill

\item[{\bf (d)}] Give the Huffman code for an $n$-character data file
in which the frequency of the every character is identical.  (You may
simply state the answer without any additional justification.)

\vfill
\end{itemize}
\newpage

{\bf Problem 4. (8 points) \hs Marriage brokers and network flows} 

A community has $n$ men, $n$ women, and $m$ marriage brokers.  Broker
$i$ has a list $M_i$ of some of the men and a list $W_i$ of some of
the women as clients, and can arrange marriages between any pairs of
men and women on that list.  The number of marriages that a broker $i$
can arrange is limited to be $b_i$.  We would like to determine the
maximum number of heterosexual marriages that can be brokered subject
to the constraints of each broker.  Assume that all people are
monogamous.  Formulate the given problem as a maximum flow problem and
justify the correctness of your formulation.

\newpage

{\bf Bonus Problem. (4 bonus points) \hs Network flows using paths of
bounded length}

Many problems related to finding routes in capacitated networks can be
formulated as network flow problems.  In such applications, it is
often helpful to find short paths.  Give a polynomial-time algorithm
that takes as input a directed graph with capacities on edges, a
source $s$, a sink $t$, and a length bound $L$, and returns a maximum
flow from $s$ to $t$ that can be realized by paths of length at most
$L$.

\end{document}

