\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]{
  \refstepcounter{questnum}
\paragraph{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 
\noindent
CS294-3: Algorithms in the real world \hfill Final Exam\\[.03in]
Due: 5pm Friday Dec 5, 1997\\[-.05in]
\mbox{}\hrulefill \mbox{}\\
}

This is an open book, take home exam.  You are free to use any
readings, but cannot talk to other people about questions on the 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.
You should read your email regularly to check for any corrections or
clarifications I might need to make to the final, and you should drop
the final off at my office when you are done.

\question{Compression: move to front}

The move-to-front heuristic is a simple compression heuristic that can
take advantage of patterns in data.  The idea is to keep the symbols
to be compressed ordered.  Whenever you read a new symbol 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 Huffman or 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.

In the following questions assume we are using the move-to-front
heuristic followed by arithmetic coding.

\begin{description}
\item[(A)]  
What do 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, asymptotically how many bits-per-symbol would the move-to-front
heuristic use to store the string.

\item[(C)]
If we had a long string with the substring $ABCDE$ repeated over and
over, asymptotically how many bits-per-symbol would the move-to-front
heuristic use to store the string.

\item[(D)] Would the move-to-front heuristic 
adapt well to changes in types of text within a single ``document''
({\em e.g.} compressing a tar file containing a mix of English, C and
postscript files).

\item[(E)] Would coding pairs of symbols (i.e. keep all
possible pairs ordered, and code two symbols at a time) help get
better compression for long messages?  Assume we are compressing the
English language.

\item[(F)] Joe hacker decides to use the move-to-front heuristic 
for private-key encryption by using the initial order of the symbols
as a key ({\em i.e} only the sender and receiver know the initial
ordering).  Would this be easy to crack?  If so, give a brief
description.  Again, assume he is encoding the English language.

\end{description}

\newpage

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

Let $G = (V,E)$ be a directed graph and assume that associated
with each vertex $i \in [1,\ldots,n]$ is a quantity $b_i$ representing
the net flow out of (positive) or into (negative) a vertex.  This, for
example, can represent the supply from a distribution site if
positive, or the demand from a customer or retailer if negative.  For
each edge $(i,j) \in E$ 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 minimum-cost network flow problem is to
minimize the total cost of the flow across the edges while properly
supplying the demand vertices (ones with negative $b_i$).  We assume
the total demand equals the total supply ($\sum_i b_i = 0$).  The
minimum-cost network flow problem can be stated as the following
linear program:

\[
\begin{array}{lll}
\mbox{minimize} &
\displaystyle \sum_{(i,j) \in E} c_{i,j} x_{i,j}\\ \mbox{subject to} &
\displaystyle  \sum_{j | (i,j) \in E} x_{i,j} -
  \sum_{j | (j,i) \in E} x_{j,i} = b_i, \hspace{.2in} & \mbox{for all } i \in V\\[.08in]
  & x_{i,j} \geq 0 & \mbox{for all } (i,j) \in E
\end{array}
\]
where $x_{i,j}$ represent the flow along edge $(i,j)$.

In the matrix $A$ in the constraint $Ax = b$ formed by this linear
program, the rows correspond to vertices and the columns correspond to
edges (each column corresponding to an edge has a 1 at the source
vertex a -1 at the destination vertex and 0s elsewhere).  It turns
out, however, 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 the edges are not directed
in the same directions ({\em 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 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 final solution
in terms of what subsets of the edges can have nonzero flows?

\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, not a full description.

\end{description}

\vspace{.2in}

\question{Integer Programming: Steiner Trees}

Formulate the minimum steiner tree problem as an integer program.
Assume an undirected 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.

\newpage

\question{Delaunay Triangulation: Incremental worst case}

In class I mentioned that in the worst case adding 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 2-dimensional 
distribution of points that gets exponentially
denser as it approaches a line.
All points are in the region $[0,1][0,1]$ ({\em i.e.} in the
square between 0 and 1 in the $x$ and $y$ dimensions).
We place one point in the region $[0,1][.5,1]$.
We place two points in the region $[0,1][.25,.5]$.
We then continue placing $2^k$ points 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 information can be represented as a matrix $A$ with
$n$ columns and $m$ rows.  Lets say we want to index this data using
latent semantic indexing so we run an SVD on the matrix and keep
the first $k$ dimensions.

Consider the following example with $n = 5, m = 10$ and $k = 2$
which gives us the $A_2 = U_2 \Sigma_2 V_2$ decomposition:

 \[ A_2 =
\left[\begin{array}{rr}
.2 & .1\\ 
.2 & -.2\\
.2 & -.4\\
.4 & .1\\
.1 & -.3\\
.2 & -.5\\
.3 & .2\\
.1 & -.1\\
.1 & .2\\
.4 & -.3
\end{array}\right]
\left[\begin{array}{rr}
2.3 & 0\\
0  & 1.5
\end{array}\right]
\left[\begin{array}{rrrrr}
.2 & .1 & .1 & .3 & .2\\
.2 & -.2 & -.5 & .1 & -.3 
\end{array}\right]
\]

\begin{description}
\item[(A)] 
If someone makes a query using the words 4 and 7 (indexed starting at
1 -- {i.e.} word 4 has column value $(.4,.1)$) and wants the documents
with cosine measure within $.6$ in the reduced 2-d space, which
documents does she get?

\item[(B)]
If I initially based my matrix $A$ on the abstracts of articles and
now want to include the titles, which includes some more words, it
turns out that I can add words to the existing SVD without modifying
the existing entries (this is called folding-in).  If a new word
``wombat'' appears in documents 2 and 5 with weights 1 and in the
other documents with weight 0, what is the value of the row I should
add (fold-in) to $U$ (i.e the location of ``wombat'' 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 transformation
from the higher dimension to the lower diminsion.  In both cases
assume we are using the cosine measure to find the $k$ closest
documents.

\end{description}

\newpage

\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
description 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 into
two sets 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 subcalls 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 of your data, given certain assumptions.  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, in calculating the compression
you can assume you are only going to make the one divide.
Hint: consider the conditional entropy between variables.

\item[(B)]
One of the big problems of divisive clustering techniques is to decide
when to stop dividing (we typically don't want to divide until there
is only one object per group).  The method of part (A) gives a natural
way to make this decision.  Explain how you might decide when to stop
dividing (i.e. when you are not going to get any further compression).
\end{description}

\end{document}
