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

\newif\ifanswer
\answertrue
\head{CS5800}{Algorithms}{Spring 2011}{7 March 2011}{12}

\begin{center}
\Large{\bf Quiz 3}
\end{center}

\noindent {\Large Name:~}\leaders\hrule\hfill\ 

\smallskip

{\bf (10 points) Consistency of constraints}

The following problem occurs in program analysis.  For a set of $n$
variables $x_1, \ldots, x_n$, you are given a set of $m$ constraints,
of one of two forms: {\em equality}, of the form $x_i = x_j$; {\em
  strict inequality}, of the form $x_i > x_j$.  The goal of this
problem is to determine whether a given set of constraints can be
satisfied.

For example, the following set of constraints can be satisfied.

\[ x_1 = x_2; x_1 = x_3; x_2 > x_4; x_3 > x_5\]

One can set $x_1 = x_2 = x_3 = 1$, $x_4 = 0$, and $x_5 = 0$.

The following set of constraints, however, cannot be satisfied.

\[ x_1 = x_2; x_1 = x_3; x_2 > x_4; x_4 > x_5; x_5 > x_3\]

Give an algorithm that takes as input $m$ constraints over $n$
variables and determines whether the constraints can be satisfied.
Your algorithm only needs to return a ``yes/no'' answer (``yes'' if the
constraints can be satisfied; and ``no'' otherwise).

State the running time of your algorithm.  You do not need to prove
the correctness of the algorithm.  The more efficient your algorithm
is, in terms of its worst case running time as a function of $n$ and
$m$, the more credit you will get.

\end{document}