
\ifx\PrefixAlreadyIncluded\undefined
    \newcommand{\BeamerMode}[1]{}
    \newcommand{\NoBeamerMode}[1]{#1}
\else
\fi

%\setlength{\headsep}{0.5in}
%\usepackage{sariel}
\providecommand{\Course}{CS 573}
\providecommand{\CourseName}{Algorithms}
\providecommand{\Year}{2014}
\providecommand{\Semester}{Fall \Year{}}

\providecommand{\UsePackageExt}[2][]{}%
\renewcommand{\UsePackageExt}[2][]{%
   \typeout{}
   \typeout{-+---------------------------------------------------}%
      \IfFileExists{styles/#2.sty}{
         \typeout{styles/#2}
         \usepackage[#1]{styles/#2}
      }{         
         \IfFileExists{../styles/#2.sty}{
            \typeout{../styles/#2}
            \usepackage[#1]{../styles/#2}%
         }{%
            \IfFileExists{../../styles/#2.sty}{
               \usepackage[#1]{../../styles/#2}%
            }{%
               \usepackage[#1]{#2}%
            }
         }
      }%
      \typeout{}
   }

\newcommand{\InputFile}[1]{%
   \typeout{}
   \typeout{-+---------------------------------------------------}%
      \IfFileExists{styles/#1}{
         \typeout{styles/#1}
         \input{styles/#1}
      }{         
         \IfFileExists{../styles/#1}{
            \typeout{../styles/#1}
            \input{../styles/#1}%
         }{%
            \IfFileExists{../../styles/#1.sty}{
               \input{../../styles/#1}%
            }{%
               \input{#1}%
            }
         }
      }%
      \typeout{}
   }

\providecommand{\UsePackage}[1]{}%
\renewcommand{\UsePackage}[1]{%
   \UsePackageExt[]{#1}%
}

\usepackage{hyperref}
\usepackage{url}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{mleftright}%
%\usepackage{wide}
\UsePackage{picins}
\usepackage{amsmath}

\ifx\theorem\undefined
\usepackage[amsmath,thmmarks]{ntheorem}
\theoremseparator{.}%
\fi

\usepackage{ifpdf}
\usepackage{cancel}
\usepackage{caption}
%\usepackage{solutions}
%\usepackage{salgorithm}
\usepackage{amssymb}

\NoBeamerMode{%
   \usepackage[cm]{fullpage}%
}

\usepackage{xspace}
\usepackage{euscript}
\usepackage{lmodern}

\usepackage{paralist}

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

\usepackage{color}

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

\newcommand{\Hastad}{H{\aa}stad\xspace}
\providecommand{\TSP}{\TermI{TSP}\xspace}
\providecommand{\LP}{\TermI{LP}\xspace}%

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

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

\providecommand{\xbeginlgox}{\begin{minipage}{1in}\begin{tabbing}
        \quad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\kill}
\providecommand{\xendlgox}{\end{tabbing}\end{minipage}}

\newenvironment{algorithmEnv}{\begin{tabular}{|l|}\hline\xbeginlgox}
        {\xendlgox\\\hline\end{tabular}}

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


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

\providecommand{\AlgorithmI}[1]{}
\renewcommand{\AlgorithmI}[1]{{%
      \textcolor[named]{AlgorithmColor}{\texttt{\bf{#1}}}}}
\providecommand{\Algorithm}[1]{{\AlgorithmI{#1}\index{#1@{\AlgorithmI{#1}}}}}


\DefineNamedColor{named}{OliveGreen}    {cmyk}{0.64,0,0.95,0.40}
\providecommand{\ProblemC}[1]{{\textsf{\textcolor{red}{#1}\index{Problem!#1}}}}
\providecommand{\ComplexityClass}[1]{{{\textcolor[named]{OliveGreen}{%
      \textsc{#1}}}}}

\fi

%\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{\coNP}{\ComplexityClass{co-NP}\xspace}
\providecommand{\POLYT}{\ComplexityClass{P}\xspace}

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

%\newcommand{\dirEdge}[2]{\overrightarrow{{#1}{#2}}}
\newcommand{\ndirEdge}[2]{{{#1} \rightarrow {#2}} }
\providecommand{\dirEdge}[2]{\left({{#1} \rightarrow {#2}} \right)}

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


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

\newcommand{\etal}{\textit{et~al.}\xspace}

\ifx\theorem\undefined
  \newtheorem{theorem}{Theorem}[section]

  \newtheorem{algorithm}[theorem]{Algorithm}
  \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{suggestion}[theorem]{Suggestion}
  \newtheorem{prop}[theorem]{Proposition}
  \newtheorem{openproblem}[theorem]{Open Problem}

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

   \theoremstyle{plain}%
   \theoremheaderfont{\sf} \theorembodyfont{\upshape}%
   
%   \newtheorem{defn}[theorem]{Definition}
   
   \newtheorem*{remark:unnumbered}[theorem]{Remark}%
   \newtheorem*{remarks}[theorem]{Remarks}%
   \newtheorem{remark}[theorem]{Remark}%
   \newtheorem{tidbit}[theorem]{Tidbit}%
%   \newtheorem{example}[theorem]{Example}
   
   \newtheorem{definition}[theorem]{Definition}
   \newtheorem{defn}[theorem]{Definition}
   \newtheorem{example}[theorem]{Example}
   \newtheorem{exercise}[theorem]{Exercise}
   \newtheorem{problem}[theorem]{Problem}
   \newtheorem{xca}[theorem]{Exercise}
   \newtheorem{exercise_h}[theorem]{Exercise}
   \newtheorem{assumption}[theorem]{Assumption}%
   
   % Proof environment
   
   \theoremheaderfont{\em}%
   \theorembodyfont{\upshape}%
   \theoremstyle{nonumberplain}%
   \theoremseparator{}%
   \theoremsymbol{\myqedsymbol}%
   \newtheorem{proof}{Proof:}%

%    \theoremstyle{definition}
%    \newtheorem{definition}[theorem]{Definition}
%    \newtheorem{defn}[theorem]{Definition}
%    \newtheorem{example}[theorem]{Example}
% %   \newtheorem{exercise}[theorem]{Exercise}
%    \newtheorem{exercise_h}{Exercise}[chapter]
%    \newtheorem{problem}[theorem]{Problem}
%    \newtheorem{xca}[theorem]{Exercise}
% %   \newtheorem{openproblem}[theorem]{Open Problem}

\fi

\BeamerMode{%
   \newtheorem{exercise}[theorem]{Exercise}%
}

\providecommand{\emphind}[1]{\emph{#1}\index{#1}}
\definecolor{blue25}{rgb}{0,0,0.95}
\definecolor{instcolor}{rgb}{0.05,0.45,0.05}

\providecommand{\emphOnly}[1]{}
\renewcommand{\emphOnly}[1]{\textcolor{blue25}{\textbf{\emph{#1}}}}

\providecommand{\emphic}[2]{}%
\renewcommand{\emphic}[2]{%
   \emphOnly{#1}%
   \index{#2}}

\providecommand{\emphi}[1]{\emphic{#1}{#1}}
\renewcommand{\emphi}[1]{\emphic{#1}{#1}}



%    -----------------------------------------------------------------
%    -----------------------------------------------------------------
%    -----------------------------------------------------------------
%    Handling references
%    -----------------------------------------------------------------
%    -----------------------------------------------------------------
%    -----------------------------------------------------------------
\newcommand{\HLinkShort}[2]{\hyperref[#2]{#1\ref*{#2}}}
\newcommand{\HLink}[2]{\hyperref[#2]{#1~\ref*{#2}}}
\newcommand{\HLinkPage}[2]{\hyperref[#2]{#1~\ref*{#2}%
      $_\text{p\pageref{#2}}$}}
\newcommand{\HLinkPageOnly}[1]{\hyperref[#1]{Page~\refpage*{#1}%
      $_\text{p\pageref{#1}}$}}

\newcommand{\HLinkSuffix}[3]{\hyperref[#2]{#1\ref*{#2}{#3}}}
\newcommand{\HLinkPageSuffix}[3]{\hyperref[#2]{#1\ref*{#2}%
      #3$_\text{p\pageref{#2}}$}}

% \newcommand{\figref}[1]{Figure~\ref{fig:#1}}
\newcommand{\figlab}[1]{\label{fig:#1}}
\newcommand{\figref}[1]{\HLink{Figure}{fig:#1}}
\newcommand{\Figref}[1]{\HLink{Figure}{fig:#1}}
\newcommand{\figrefpage}[1]{\HLinkPage{Figure}{fig:#1}}

\newcommand{\seclab}[1]{\label{sec:#1}}
\newcommand{\secref}[1]{\HLink{Section}{sec:#1}}
\newcommand{\secrefpage}[1]{\HLinkPage{Section}{sec:#1}}

\newcommand{\corlab}[1]{\label{cor:#1}}
\newcommand{\corref}[1]{\HLink{Corollary}{cor:#1}}%
\newcommand{\correfshort}[1]{\HLinkShort{C}{cor:#1}}%
\newcommand{\correfpage}[1]{\HLinkPage{Corollary}{cor:#1}}

\providecommand{\deflab}[1]{\label{def:#1}}
\newcommand{\defref}[1]{\HLink{Definition}{def:#1}}
\newcommand{\defrefpage}[1]{\HLinkPage{Definition}{def:#1}}

\newcommand{\apndlab}[1]{\label{apnd:#1}}
\newcommand{\apndref}[1]{\HLink{Appendix}{apnd:#1}}
\newcommand{\apndrefpage}[1]{\HLinkPage{Appendix}{apnd:#1}}

\newcommand{\clmlab}[1]{\label{claim:#1}}
\newcommand{\clmref}[1]{\HLink{Claim}{claim:#1}}
\newcommand{\clmrefpage}[1]{\HLinkPage{Claim}{claim:#1}}%

\newcommand{\remlab}[1]{\label{rem:#1}}
\newcommand{\remref}[1]{Remark~\ref{rem:#1}}
\newcommand{\remrefpage}[1]{Remark~\ref{rem:#1}%
   $_\text{p\pageref{rem:#1}}$}

\newcommand{\itemlab}[1]{\label{item:#1}}
\newcommand{\itemref}[1]{\HLinkSuffix{(}{item:#1}{)}}

\newcommand{\lemlab}[1]{\label{lemma:#1}}
\newcommand{\lemref}[1]{\HLink{Lemma}{lemma:#1}}%
\newcommand{\lemrefpage}[1]{\HLinkPage{Lemma}{lemma:#1}}
\newcommand{\lemrefshort}[1]{\HLinkShort{L}{lemma:#1}}
\newcommand{\pagelemref}[1]{\HLinkPageOnly{lemma:#1}}

\newcommand{\obslab}[1]{\label{observation:#1}}
\newcommand{\obsref}[1]{\HLink{Observation}{observation:#1}}
\newcommand{\obsrefshort}[1]{\HLinkShort{O}{observation:#1}}
\newcommand{\obsrefpage}[1]{\HLinkPage{Observation}{observation:#1}}

\newcommand{\alglab}[1]{\label{Algorithm:#1}}%
\newcommand{\algref}[1]{\HLink{Algorithm}{Algorithm:#1}}%
\newcommand{\algrefpage}[1]{\HLinkPage{Algorithm}{Algorithm:#1}}%

\newcommand{\thmlab}[1]{{\label{theo:#1}}}
\newcommand{\thmref}[1]{\HLink{Theorem}{theo:#1}}
\newcommand{\thmrefpage}[1]{\HLinkPage{Theorem}{theo:#1}}

\providecommand{\eqlab}[1]{}%
\renewcommand{\eqlab}[1]{\label{equation:#1}}
\newcommand{\Eqref}[1]{\HLinkSuffix{Eq.~(}{equation:#1}{)}}
\newcommand{\Eqrefpage}[1]{\HLinkPageSuffix{Eq.~(}{equation:#1}{)}}

\newcommand{\exmlab}[1]{\label{example:#1}}
\newcommand{\exmref}[1]{\HLink{Example}{example:#1}}


%----    Handling references - end


%\providecommand{\theolab}[1]{\label{theo:#1}}

%\providecommand{\thmlab}[1]{{\label{theo:#1}}}
%\providecommand{\thmref}[1]{Theorem~\ref{theo:#1}}

   
   
\providecommand{\ProblemInd}[2]{\textsf{\textcolor{red}{#1}\index{Problem!#2}}}
\providecommand{\ZZ}{{\sf Z\!\hspace{-0.2em} Z}}

\providecommand{\NPProblemInd}{}

\definecolor{ProblemDefColor}{rgb}{0,0,1}

\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{ProblemDefColor}%
                 {\bf \textsf{Instance}}:} {#3}
              
              \noindent{\textcolor{ProblemDefColor}%
                 {\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{\OptProblemInd}{}
\renewcommand{\OptProblemInd}[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{instcolor}{\bf %
                    \textsf{Instance}}:} {#3}
              
              \noindent{\textcolor{instcolor}{\bf \textsf{Target}:}} {#4}
          \end{minipage}
       }
   \end{center}
%   \marginpar{\footnotesize\ProblemInd{#1}{#2}}%
   \smallskip
   }
\providecommand{\OptProblem}[3]{\OptProblemInd{#1}{#1}{#2}{#3}}


\renewcommand{\th}{th\xspace}
\newcommand{\ts}{\hspace{0.6pt}}


\providecommand{\Version}[1]{\hfill\textbf{Version}: #1}

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

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

%\providecommand{\HWProblem}[3]{}


\renewcommand{\th}{t{}h\xspace}
\newcommand{\SpaceChar}{\ensuremath{\text{\textvisiblespace}}\xspace}

\providecommand{\DAG}{}
\renewcommand{\DAG}{\TermI{DAG}\xspace}

\newcommand{\Ground}{\mathsf{S}}
\newcommand{\Family}{\EuScript{F}}
\newcommand{\FamilyB}{\EuScript{G}}
\newcommand{\FamilyC}{\EuScript{H}}

\providecommand{\ds}{\displaystyle}
\renewcommand{\ds}{\displaystyle}

\providecommand{\Graph}{}
\renewcommand{\Graph}{\mathsf{G}}%

\providecommand{\GraphB}{}
\renewcommand{\GraphB}{\mathsf{H}}%

\providecommand{\Tree}{\mathsf{T}}%
\renewcommand{\Tree}{\mathsf{T}}%

\newcommand{\nfrac}[2]{{#1}/{#2}}

\providecommand{\LPInstance}{}
\renewcommand{\LPInstance}{\mathcal{L}}

\providecommand{\Vertices}{}
\renewcommand{\Vertices}{\mathsf{V}}%

\providecommand{\Edges}{\mathsf{E}}%
\renewcommand{\Edges}{\mathsf{E}}%

\newcommand{\EdgesX}[2][\!]{\Edges\pth[#1]{#2}}%

\newcommand{\edge}{\mathsf{e}}

\newcommand{\VerticesX}[2][\!]{\Vertices\pth[#1]{#2}}


\newcommand{\degreeX}[2][\!]{\mathrm{d}\pth[#1]{#2}}


\providecommand{\remove}[1]{}
\renewcommand{\remove}[1]{}

\ifx\savedparindent\undefined
  \newlength{\savedparindent}
  \newcommand{\SaveIndent}{\setlength{\savedparindent}{\parindent}}
  \newcommand{\RestoreIndent}{\setlength{\parindent}{\savedparindent}}
\fi

\providecommand{\permut}[1]{\left\langle {#1} \right\rangle}

\newcommand{\eps}{{\varepsilon}}%
%\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}}
\renewcommand{\Re}{\mathbb{R}}
\providecommand{\reals}{\Re}
\renewcommand{\reals}{\Re}

\newcommand{\MakeSBig}{\Bigl.}


\providecommand{\Entropy}{}
\renewcommand{\Entropy}[1]{\EntropyChar\pth{#1}}

\providecommand{\EntropyX}{}
\renewcommand{\EntropyX}[1]{\EntropyChar\pth[]{#1}}

\providecommand{\EntropyChar}{}
\renewcommand{\EntropyChar}{\mathbb{H}}


\providecommand{\si}[1]{#1}%
\renewcommand{\si}[1]{#1}

\newcommand{\FPTAS}{\TermI{FPTAS}\xspace}
\newcommand{\PTAS}{\TermI{PTAS}\xspace}


\newcommand{\IncludeGraphics}[2][]{%
   \typeout{}%
   \typeout{Graphics: #2}%
   \typeout{\ includegraphics[#1]{#2}}%
   \includegraphics[#1]{#2}
   \typeout{}%
}

\newcommand{\IncGraphPage}[4][]{
   \ifpdf
      \IncludeGraphics[page=#4,#1]{\File{#2/#3}}
   \else
      \IncludeGraphics[#1]{\File{#2/#3/#3_#4}}
   \fi
}
\newcommand{\DotProd}[2]{\permut{{#1},{#2}}}
\newcommand{\distG}[2]{\mathsf{d}_\Graph\pth{#1, #2}}

