\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: #1 }}

\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 Final Exam\\[.03in]
Due: 5pm Friday Dec 5, 1997\\[.1in]
}

This is an open book, take home exam.  You are free to use any
readings, but cannot talk to anyone else about this exam.
I will be in my office much of the time from around 11AM-6PM on 
Thursday and 12:30-5:00pm on Friday if you have questions.

\question{Compression: move to front}

A very simple compression heuristic that can take advantage of
patterns in data is the move-to-front heuristic.  The idea is to keep
the symbols to be compressed ordered.  Whenever you read a new
character to compress, output its position in the ordered symbols and
then move it to the front.  For example if we start with symbols
ordered as $\{A,B,C,D,E\}$, with $A$ at the front, the string $BBCAEB$
would be converted to $\{1,0,2,2,4,3\}$.  After generating these
numbers they can be compressed using arithmetic coding (we assume we
can see the whole sequence before compressing it).  The hope is that
there are many small numbers due to "temporal locality" of the symbols
so the compression will work well.

\begin{description}
\item[(A)]  
What to we have to send in order to uncompress the data.
(Answer in no more than two sentences.)

\item[(B)]
If we had a long string with the substring $ABCAB$ repeated over
and over, what is the asymptotic bits-per-char needed to transmit
the message.

\item[(C)]
If we had a long string with the substring $ABCDE$ repeated over
and over, what is the asymptotic bits-per-char needed to transmit
the message.

\item[(D)] Would using the method on pairs of symbols (i.e. keep all
possible pairs ordered, and code pairs by their position) help get
better compression?  Assume we are compressing the English language.

\item[(E)] Would it adapt well to changes in types of thing being
compressed (e.g. from English language to C code).

\item[(F)] Joe hacker decides to use the method for private-key
encryption by using the initial order of the symbols as a key.  Would
this be easy to crack?  If so, give a brief description.  Again, asume
he is encoding the English language.  

\end{description}

\question{Linear Programming: Minimum-cost network flow}

Let $G = (V,E)$ be a directed graph and assume that that associated
with each vertex $i$ is a quantity $b_i$ representing the net flow out
of (positive) or into (negative) a vertex.  This, for example,
represents the suply from a distribution site (positive) or the demand
from a customer or retailer (negative).  For each edge $ij$ we have an
associated cost $c_{i,j}$ which represents the per unit cost of
transporting material (flow) across that edge.  The goal of the
mimimun-cost network flow problem is to minimize the total cost of the
flow across the edges while properly supplying the demand vertices.
We assume the total demand equals the total supply.  This is easily
stated as a linear program \begin{eqnarray*} \mbox{minimize} &
\sum_{(i,j) \in E} c_{i,j} x_{i,j}\\ \mboxa{subject to} &
  \sum_{j | (i,j) \in E} x_{i,j} -
  \sum_{j | (j,i) \in E} x_{j,i} = b_i, \hspace{.5in} & for all i \in V\\
  & x_{i,j} \geq 0 & for all (i,j) \in E
\end{eqnarray*}
where $x_{i,j}$ represent the flow along edge $(i,j)$.

In the matrix $A$ in $Ax = b$ formed by this linear program the rows
correspond to vertices and the colums correspond to edges.  It turns
out that the matrix $A$ does not have full rank (it only has $n-1$
independent rows) and is therefore not in the correct format for the
simplex method.  However, an easy fix is to add one additional column
to the matrix which is all zeros except for a single 1 on an arbitrary
row (vertex).  This can be thought of as a root edge that goes from
that vertex to nowhere.

For the purpose of this problem we will define a cycle as any chain
of edges that comes back on itself, even if they are not directed
in the same directions (i.e. if A points to B and C, and B points
to C, then A,B and C form a cycle).

\begin{description}

\item[(a)] Show that the edges corresponding to a set of feasible basis
variables in the simplex method for the matrix $A$ cannot include a
cycle.  Hint:  is the corresponding submatrix invertible?

\item[(b)] What does this tell you about the form of the final solution?

\item[(c)] In terms of the graph, what does one step of the simplex
method correspond to.  I'm just looking for a short one or two sentence
answer.

\end{description}

\question{Integer Programming: Steiner Trees}

Formulate the minimum steiner tree problem as an integer program.
Assume a graph $G = (V,E)$ with edge weights $w(e)$
and a set of demand points $D \subset V$.
The integer program must have at most a polynomial number
of equations and variables (in the size of $G$).
There are probably many ways to formulate the problem, but a hint for one
way is to consider a set of binary variables $x_{i,j,l}$ which
are 1 when there is a path from vertex $i$ to vertex $j$ that
traverses at most $l$ edges, and 0 otherwise.

\question{Delaunay Triangulation: Incremental worst case}

In class I mentioned that in the worst case doing an addition of a
single point to a Delaunay triangulation using the incremental method
can modify all the existing triangles, and thus take $\Theta(n)$ time.
Show (or describe) an example in which this will happen.

\question{Nbody Problem: Depth of Barnes-Hut}

Consider the following distribution of points that gets exponentially
denser as it approaches a line.
We start with a square $[0,1][0,1]$.
We place one point in the region $[0,1][.5,1]$.
We place two points down in the region $[0,1][.25,.5]$.
We then continue placing $2^k$ points down in the region 
$[0,1][1/2^{k+1},1/2^k]$ until we have placed $n-1$ points.
Assuming the points are put down pretty much evenly within each region,
how deep would the Barnes-Hut tree be for this distribution
as a function of $n$?

\question{Indexing: Latent semantic indexing and the SVD}

Assume you have n documents and for each we have a vector representing
weights on each of m terms (you can assume most weights are zero).
This can be represented as a matrix $A$ with n columns and m rows.
Lets consider a problem with 6 documents and 10 terms.
We are going to use latent semantic indexing to make queries on
the dataset, so we run an SVD on the matrix and keep the first
two dimensions.  Lets say this gives us:

 \[ A =
\left[\begin{array}{ll}
.5 & .5 \\
.5 & .5 \\
.5 & .5 \\
.5 & .5 \\
.5 & .5 \\
.5 & .5 \\
.5 & .5 \\
.5 & .5 \\
.5 & .5 \\
\end{array}\right]

\left[\begin{array}{ll}
2.3 & 0
0  & 1.5
\end{array}\right]

\left[\begin{array}{llllll}
.5 & .5 & .5 & .5 & .5 & .5\\
.5 & .5 & .5 & .5 & .5 & .5\\
\end{array}\right]
\]

\begin{description}
\item[(A)] 
If I'm make a query ??? and ask for documents with a cosine measure within
.9 in the reduced 2-d space, which documents do I get?

\item[(B)]
If I initially based my matrix A on the abstracts of articles and now
want to include the the titles, which includes some more words, it turns
out that I can add words to the existing SVD without completely rerunning it.
If a new word foo appears in documents 2 and 5 with equal weight what
is the value of the row I should add to U (i.e the location of foo in
the 2-d space).

\item[(C)] For a large dataset why might a user query in the reduced
dimensional space be much more expensive (runtime) than in the
original space, even if I don't include the cost of the transform.
In both cases assume we are using the cosine measure to find the
k closest documents.

\end{description}

\question{Clustering: Using compression to cluster}

The object of this problem is to design a divisive (hierarchical top
down) monothetic algorithm for clustering based on the minimum
desription length principal.  Assume your data is a set of $n$
objects each with $m$ variables, and for simplicity assume the
variables have binary values.  The goal is to divide the objects based
on one of the variables (this is what monothetic refers to) and then
recursively divide each of the subsets based on one of the remaining
variables (the two subcals could partition on different variables)
to build a hierarchical clustering.

The goal is to select a clustering that will allow you to get the best
compression out of your data (given that we are doing a hierarchical
divisive method).  This is based on the principal that shorter
descriptions are better descriptions.

\begin{description}
\item[(A)]
At each node how would divide the data so that you could compress it the most.
To simplify things you can assume you are only going to make the one divide.
Hint: consider conditional entropy.

\item[(B)]
One of the big problems of divisive clustering techniques is to decide when
to stop dividing.  The minimum description method combined with the method
of part (A) give a natural way to do this.  Explain how you might decide
when to stop dividing.
\end{description}

\end{document}