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

\head{CS7800}{Advanced Algorithms}{Fall 2010}{18 September 2010}{4}

\begin{center}
\Large{\bf Problems of the Week -- 2 and 3}
\end{center}

{\bf POW-2: Consistency of constraints in program analysis}

Here's a problem that occurs in automatic program analysis.  Consider
a program that has $n$ integer variables $x_1, \ldots, x_n$.  Analysis
of the program and its specification reveal several constraints, which
are of four forms: {\em equality}, of the form $x_i = x_j$; {\em
  inequality}, of the form $x_i > x_j$; {\em strict inequality}, of
the form $x_i \ge x_j$; and {\em disequality}, of the form $x_i \neq
x_j$.

Give an algorithm that takes as input $m$ constraints over $n$
variables and determines whether the constraints can be satisfied.
Analyze the running time of your algorithm.  Make your algorithm as
efficient as you can, in terms of its worst case running time.

{\bf POW-3: Clustering to maximize separation}

Many scientific applications, including medical imaging,
classification of astronomical objects, and web document
categorization, require partitioning a given set of objects into
disjoint sets.  Here is one of many variants of clustering problems.
You are given a set $S$ of $n$ points $v_1, \ldots, v_n$, together
with their pairwise distances.  You may assume that the distances are
symmetric and nonnegative, and that the distance between a point and
itself is zero, while that between two distinct points is nonzero.
Let $d(u,v)$ denote the distance between two points $u$ and $v$.  For
any two nonempty sets $X$ and $Y$ of points, define the {\em distance
  $d(X,Y)$ between $X$ and $Y$}\/ to be
\[
\min_{u \in X, v \in Y} d(u,v).
\]
Given a number $m \le n$, you are asked to partition $S$ into $m$
nonempty disjoint sets $S_1, \ldots, S_m$ so as to maximize the
minimum distance between any pair of disjoint sets; that is, determine
disjoint sets $S_1$ through $S_m$ that maximizes $\min_{i \neq j}
d(S_i, S_j)$ subject to the constraint that $\cup_i S_i = S$.

Give an algorithm to solve the above problem.  Analyze the running
time.  Make your algorithm as efficient as you can, in terms of its
worst case running time.
\end{document}
