\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 2014}{15 September 2014}{4}

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

{\bf POW-3: 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-4: Minimal directed graphs}

Call a directed graph {\em minimal}\/ if which there is at most one
simple path from any vertex to any other vertex.  Give an $O(mn)$ time
algorithm to determine whether a given directed graph with $n$
vertices and $m$ edges is minimal.  If you are unable to achieve the
desired running time, give the fastest algorithm you can.
\end{document}
