%\setlength{\headsep}{0.5in}
%\usepackage{sariel}
\usepackage{hyperref}
\usepackage{url}
\usepackage{graphicx}
\usepackage{enumerate}
%\usepackage{wide}
\usepackage{picins}
\usepackage{amsmath}
\usepackage{ifpdf}
\usepackage{cancel}
%\usepackage{solutions}
%\usepackage{salgorithm}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{xspace}
\usepackage{euscript}

\usepackage{paralist}

% %%%%%%%%%%%%%%%%%%%% program macros %%%%%%%%%%%%%%%%%

\usepackage{color}

\newcommand{\Term}[1]{\textsf{#1}}
\newcommand{\TermI}[1]{\Term{#1}\index{#1@\Term{#1}}}


\newcommand{\TSP}{\TermI{TSP}\xspace}

\newcommand{\Do}{{\small\bf do}\ }
\newcommand{\End}{{\small\bf end}\ }
\newcommand{\Return}{{\small\bf return\ }}
\newcommand{\Proc}[1]{#1\+}
\newcommand{\Returns}{{\small\bf returns}}
\newcommand{\Procbegin}{{\small\bf begin}}
\newcommand{\If}{{\small\bf if}\ }
\newcommand{\Then}{{\small\bf then}\ }
\newcommand{\Else}{{\small\bf else}\ }
\newcommand{\rElse}{{\small\bf else}\ }
\newcommand{\Elseif}{{\small\bf elseif}\ }
\newcommand{\Foreach}{{\small\bf for each}\ }
\newcommand{\Endif}{{\small\bf end\ if\ }}
\newcommand{\Break}{{\small\bf break }}
\newcommand{\Endproc}[1]{{\small\bf end} #1}
\newcommand{\For}{{\small\bf for}\ }
\newcommand{\Endfor}{{\small\bf end\ for}}
\newcommand{\While}{{\small\bf while}\ }
\newcommand{\Endwhile}{{\small\bf end\ while}}
\newcommand{\LogAnd}{{\small\bf and}}

\newcommand{\Repeat}{{\small\bf repeat}\ }
\newcommand{\Until}{{\small\bf Until}}
\newcommand{\Loop}{{\bf loop}\ }
\newcommand{\Endloop}{{\bf end\ loop}\ }

\newcommand{\xbeginlgox}{\begin{minipage}{1in}\begin{tabbing}
        \quad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\kill}
\newcommand{\xendlgox}{\end{tabbing}\end{minipage}}
\newenvironment{algorithm}{\begin{tabular}{|l|}\hline\xbeginlgox}
        {\xendlgox\\\hline\end{tabular}}

\newenvironment{program}{
   \begin{minipage}{4.0in}
   \begin{tabbing}
      \= \ \ \ \= \ \ \ \ \= \ \ \ \ \= \ \ \ \ \=
      \ \ \ \ \= \ \ \ \ \= \ \ \ \ \= \ \ \ \ \=
      \ \ \ \ \= \ \ \ \ \= \ \ \ \ \= \ \ \ \ \= \kill
}{
   \end{tabbing}
   \end{minipage}
}

\DefineNamedColor{named}{RedViolet} {cmyk}{0.07,0.90,0,0.34}

\newcommand{\AlgorithmI}[1]{{\textcolor[named]{RedViolet}{\texttt{\bf{#1}}}}}
\newcommand{\Algorithm}[1]{{\AlgorithmI{#1}\index{#1@{\AlgorithmI{#1}}}}}


\DefineNamedColor{named}{OliveGreen}    {cmyk}{0.64,0,0.95,0.40}

\newcommand{\ProblemC}[1]{{\textsf{\textcolor{red}{#1}\index{Problem!#1}}}}
\providecommand{\ComplexityClass}[1]{{{\textcolor[named]{OliveGreen}{%
      \textsc{#1}}}}}
%\providecommand{\ComplexityClass}[1]{{\textPurple\textsc{#1}\textBlack}}
\providecommand{\NPHard}{\ComplexityClass{NP-Hard}\xspace}
\providecommand{\NPComplete}{\ComplexityClass{NP-Complete}\xspace}
\providecommand{\NPC}{\ComplexityClass{NPC}\xspace}
\providecommand{\NP}{\ComplexityClass{NP}\xspace}

\newcommand{\floor}[1]{\left\lfloor {#1} \right\rfloor}
\newcommand{\brc}[1]{\left\{ {#1} \right\}}
\newcommand{\sep}[1]{\,\left|\, {#1} \MakeBig\right.}
\newcommand{\MakeBig}{\rule[-.2cm]{0cm}{0.4cm}}
\newcommand{\cardin}[1]{\left| {#1} \right|}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}
\newcommand{\pbrcx}[1]{\left[ {#1} \right]}
\newcommand{\Ex}[1]{\mathop{\mathbf{E}}\!\pbrcx{#1}}
\newcommand{\ceil}[1]{\left\lceil {#1} \right\rceil}
\newcommand{\Prob}[1]{\mathop{\mathbf{Pr}}\!\pbrcx{#1}}

\newcommand{\Hint}[1]{[{\bf{}\bf{Hint:}} {#1}{\bf]}}


\newcommand{\Hard}{\textbf{(HARD)}}
\newcommand{\ReallyHard}{\textbf{(Really HARD)}}
\providecommand{\points}[1]{{\bf [{#1} Points]}}


\newcommand{\Course}{CS 573}
\newcommand{\CourseName}{Algorithms}
\newcommand{\Semester}{Fall 2012}

\newtheorem{theorem}{Theorem}[section]

\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{invariant}[theorem]{Invariant}
\newtheorem{question}[theorem]{Question}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{openproblem}[theorem]{Open Problem}

\newenvironment{proof}{{\em Proof:}}{\hfill{\hfill\rule{2mm}{2mm}}}

\newcommand{\emphind}[1]{\emph{#1}\index{#1}}
\definecolor{blue25}{rgb}{0,0,0.25}
\newcommand{\emphic}[2]{%
     \textcolor{blue25}{%
         \textbf{\emph{#1}}}%
         \index{#2}}

\newcommand{\emphi}[1]{\emphic{#1}{#1}}

\newcommand{\lemlab}[1]{\label{lemma:#1}}
\newcommand{\lemref}[1]{Lemma~\ref{lemma:#1}}
\newcommand{\ProblemInd}[2]{\textsf{\textcolor{red}{#1}\index{Problem!#2}}}
\newcommand{\ZZ}{{\sf Z\!\hspace{-0.2em} Z}}

\newcommand{\NPProblemInd}[4]{
   \begin{center}

       ~

       \fbox{
          \begin{minipage}{0.8\linewidth}
              \vspace{-0.6cm}\hspace{-0.35cm}
              {\bf Problem:} \ProblemInd{#1}{#2}
              \vspace{+0.2cm}

              \noindent\emph{Instance:} {#3}
              
              \noindent\emph{Question:} {#4}
          \end{minipage}
       }
   \end{center}
   }
\newcommand{\NPProblem}[3]{\NPProblemInd{#1}{#1}{#2}{#3}}
\renewcommand{\th}{th\xspace}