
\usepackage{paralist}%
\usepackage{graphicx}%
\usepackage{amsmath}%
\usepackage{color}%
\usepackage{mleftright}%
\usepackage{xspace}%

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

\providecommand{\ComplexityClass}[1]{{{\textcolor{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}

\providecommand{\points}[1]{(\textsc{#1 pts.})}


% \makeatletter
% \def\provideenvironment{\@star@or@long\provide@environment}
% \def\provide@environment#1{%
%         \@ifundefined{#1}%
%                 {\def\reserved@a{\newenvironment{#1}}}%
%                 {\def\reserved@a{\renewenvironment{dummy@environ}}}%
%         \reserved@a
% }
% \def\dummy@environ{}
% \makeatother



\newcommand{\File}[1]{#1}%
\newcommand{\HWProblem}[4]{\points{#1} \textsf{#2}
       
       #3}{}

\newcommand{\myqedsymbol}{\rule{2mm}{2mm}}


\usepackage[amsmath,thmmarks]{ntheorem}%
\theoremseparator{.}
%\usepackage{theorem}
%\theoremstyle{plain}% default




\ifx\theorem\undefined

\newtheorem{theorem}{Theorem}[section]
\newtheorem{exercise}[theorem]{Exercise}

\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\fi

%---------------------------------------------------------
%---------------------------------------------------------
%---------------------------------------------------------
% Proof environment

\theoremheaderfont{\em}%
\theorembodyfont{\upshape}%
\theoremstyle{nonumberplain}%
\theoremseparator{}%
\theoremsymbol{\myqedsymbol}%
\newtheorem{proof}{Proof:}%
% 
% Proof environment
%---------------------------------------------------------


\newcommand{\aftermathA}{\par\vspace{-\baselineskip}}
% %%%%%%%%%%%%%%%%%%%% program macros %%%%%%%%%%%%%%%%%


\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{\permut}[1]{\left\langle {#1} \right\rangle}

\newcommand{\DotProd}[2]{\permut{{#1},{#2}}}


\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{algorithm!#1@{\AlgorithmI{#1}}}}}

\providecommand{\ds}{\displaystyle}

\newcommand{\DFS}{\Algorithm{DFS}\xspace}

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

\newcommand{\MST} {\TermI{MST}\xspace}
\newcommand{\BFS} {\Algorithm{BFS}\xspace}
\newcommand{\DAG} {\TermI{DAG}\xspace}
\newcommand{\LCA} {\TermI{LCA}\xspace}

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


\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}%
\newcommand{\ceil}[1]{\left\lceil {#1} \right\rceil}%
\newcommand{\Prob}[1]{\mathop{\mathbf{Pr}}\!\pbrcx{#1}}
%\newcommand{\points}[1]{(#1 pts.)}

\newcommand{\dfsPre}{\ensuremath{\mathrm{pre}}}
\newcommand{\dfsPost}{\ensuremath{\mathrm{post}}}

\newcommand{\hr}{\noindent \rule{\linewidth}{0.2mm}}%
\newcommand{\Hr}{\noindent \rule{\linewidth}{0.4mm}}%

\newcommand{\Version}[1]{Version: \textbf{#1}}
\newcommand{\si}[1]{#1}

\newcommand{\figlab}[1]{\label{fig:#1}}
\newcommand{\figref}[1]{Figure~\ref{fig:#1}}

\newcommand{\eqlab}[1]{\label{equation:#1}}
\newcommand{\Eqref}[1]{Eq.~(\ref{equation:#1})}

\newcommand{\lemlab}[1]{\label{lemma:#1}}
\newcommand{\lemref}[1]{Lemma~\ref{lemma:#1}}

\newlength{\savedparindentx}

\newcommand{\code}[1] {{\tt \begin{center} \begin{tabbing}
                             \=----\=----\=----\=----\=----\=----\kill
                        #1 \end{tabbing}\end{center}}}

\newcommand{\ncode}[1]{
    \begin{minipage}{0.45\linewidth}
        \code{#1}
    \end{minipage}}

\newcommand{\cfncode}[1]{\centerline{\fbox{\ncode{#1}}}}

\newcommand{\LLineSkip}{}

\newcommand{\brc}[1]{\left\{ {#1}\right\}}%

%\newcommand{\pth}[2][\!]{#1\left({#2}\right)}%
%\newcommand{\pbrc}[2][\!\!]{#1\left[ {#2} \MakeBig \right]}

\newcommand{\pth}[2][\!]{\mleft({#2}\mright)}%
\newcommand{\pbrc}[2][\!\!]{#1\left[ {#2} \bigr. \right]}


\newcommand{\Graph}{\mathsf{G}}%
\newcommand{\GraphA}{\mathsf{H}}%
\newcommand{\Vertices}{\mathsf{V}}%
\newcommand{\VerticesX}[1]{\Vertices\pth{#1}}%
\newcommand{\Edges}{\mathsf{E}}
\newcommand{\EdgesX}[1]{\Edges\pth{#1}}%

\newcommand{\cardin}[1]{\left| {#1} \right|}%
\newcommand{\ProblemC}[1]{{\textsf{\textcolor{red}{#1}\index{problem!#1}}}}%
\newcommand{\GSCC}{{\Graph^{{\textsc{SCC}}}}}%
\newcommand{\SCC}{\textsc{SCC}\xspace}%

\newcommand{\heightA}{\rule[0.0cm]{0.0cm}{0.32cm}} % really small
\newcommand{\heightB}{\rule[0.0cm]{0.0cm}{0.35cm}} % really small
\newcommand{\heightC}{\rule[0.0cm]{0.0cm}{0.37cm}} % really small
\newcommand{\heightD}{\rule[0.0cm]{0.0cm}{0.39cm}} % really small
\newcommand{\heightE}{\rule[0.0cm]{0.0cm}{0.42cm}} % really small
\newcommand{\heightF}{\rule[0.0cm]{0.0cm}{0.45cm}} % really small
\newcommand{\heightG}{\rule[0.0cm]{0.0cm}{0.48cm}} % really small
\newcommand{\heightH}{\rule[0.0cm]{0.0cm}{0.51cm}} % really small
\newcommand{\heightI}{\rule[0.0cm]{0.0cm}{0.54cm}} % really small
\newcommand{\heightJ}{\rule[0.0cm]{0.0cm}{0.57cm}} % really small

%\newcommand{\MakeBig}{\rule[-.2cm]{0cm}{0.4cm}}
\newcommand{\sep}[1]{\,\left|\, {#1} \heightD\right.}

\newcommand{\Boruvka}{Bor{\r u}vka\xspace}
\newcommand{\dirEdge}[3][\!]{\pth[#1]{#2, #3}}

\newcommand{\vertex}{v}
\newcommand{\inX}[1]{{#1}_{\mathrm{in}}}
\newcommand{\outX}[1]{{#1}_{\mathrm{out}}}
\newcommand{\vin}{\inX{\vertex}}
\newcommand{\vout}{\outX{\vertex}}

\newcommand{\NPProblem}[3]{\NPProblemInd{#1}{#1}{#2}{#3}}
\providecommand{\ZZ}{{\sf Z\!\hspace{-0.2em} Z}}

\providecommand{\ProblemInd}[2]{\textsf{\textcolor{red}{#1}\index{Problem!#2}}}
\providecommand{\NPProblemInd}{}
\renewcommand{\NPProblemInd}[4]{
   \begin{center}
      \vspace{0.6cm}
       \fbox{
          \begin{minipage}{0.9\linewidth}
              \vspace{-0.6cm} \hspace{-0.35cm}
              %{\bf  Problem:} 
              {\large \bf \ProblemInd{#1}{#2}}
              \vspace{+0.2cm}%

              \noindent{\textcolor{blue}{\bf \textsf{Instance}}:} {#3}
              
              \noindent{\textcolor{blue}{\bf \textsf{Question}:}} {#4}
          \end{minipage}
       }
   \end{center}
%   \marginpar{\footnotesize\ProblemInd{#1}{#2}}%
   \smallskip
   }

\providecommand{\NPProblemOpt}{}
\renewcommand{\NPProblemOpt}[4]{\NPProblemInd{#1}{#2}{#3}{#4}}

\providecommand{\NPProblem}[3]{\NPProblemInd{#1}{#1}{#2}{#3}}






\providecommand{\remove}[1]{}

\newcommand{\CodeComment}[1]{\textcolor{blue}{\texttt{#1}}}
\newcommand{\fcode}[1]{
   \smallskip
   
   \centerline{\fbox{
    \begin{minipage}{0.95\linewidth}
        \code{#1}
    \end{minipage}}}
    
    \smallskip}

\newlength{\savedparindent}
\providecommand{\SaveIndent}{\setlength{\savedparindent}{\parindent}}
\providecommand{\RestoreIndent}{\setlength{\parindent}{\savedparindent}}
\newcommand{\MakeBig}{\rule[-.2cm]{0cm}{0.4cm}}
\newcommand{\ExChar}{\mathbf{E}}
\newcommand{\pbrcx}[1]{\left[ {#1} \right]}
\newcommand{\Ex}[2][\!]{\mathop{\mathbf{E}}#1\pbrcx{#2}}

\newcommand{\Event}{\EuScript{E}}
\newcommand{\EventA}{\EuScript{F}}
\providecommand{\ThreeCNF} {\TermI{3CNF}\xspace}
\providecommand{\CNF} {\TermI{CNF}\xspace}

\providecommand{\th}{}
\renewcommand{\th}{th\xspace}%
\newcommand{\Set}[2]{\left\{ #1 \;\middle\vert\; #2 \right\}}


