\newcommand{\blank}[1]{\underline{\hs{#1}}}
\newcommand{\eeq}{==}

   % \newcommand{\Bbb}{\bf}
\newcommand{\bm}{\boldmath}

  % e.g. $\mathbf {bold + 2^{ft}\Psi \log[\psi]}$
  % - also \mathit \mathrm \mathsf \mathtt for other styles
  % - only affects letters, numbers, and uppercase Greek characters
  % 
  % - there is also \boldmath which makes everything in an equation bold,
  % e.g. \boldmath ${diff + 2^{ft}\Psi \log[\psi]$
  % 
  % \boldmath can't be used inside of the math environment.  To make a subformula
  % bold, you need to use \mbox
  % e.g. \(x + \mbox{\boldmath $\nabla f$} = 0\)

% Quetions & Answers
\newif\ifAns 

\bibliographystyle{plain}
\sloppy

%\newtheorem{TM}{Theorem}
%\newtheorem{LM}[TM]{Lemma}
%\newtheorem{LM}{Lemma}
%\newtheorem{LM}{Lemma}[section]
%\newtheorem{LM}{Lemma}[TM]

\newtheorem{TM}{Theorem}
\newtheorem{LM}{Lemma}
\newtheorem{CJ}{Conjecture}
% used usually   \newtheorem{LM}{Lemma}
% used in ED     \newtheorem{LM}{Lemma}[TM]

% Theorem
\newcommand{\tm}[1]{\mbox{} \vspace{-1.5em} \mbox{} \begin{TM} \label{#1}}
\newcommand{\tmr}[2]{\begin{TM}[{[#1]}] \label{#2} }
\newcommand{\etm}{\end{TM} \mbox{} \vspace{-1.5em} \mbox{}}
\newcommand{\reptm}[2]{\noindent {\bf Theorem}~\ref{#1} {\em #2}}
\newcommand{\primetm}[2]{\noindent {\bf Theorem}~\ref{#1}$'$ {\em #2}}
\newcommand{\rtm}[1]{Theorem~\ref{#1}}
\newcommand{\pftm}[1]{\noindent {\bf Proof of Theorem \ref{#1}:\ }}
\newcommand{\pftmr}[2]{\noindent {\bf Proof of Theorem \ref{#1}\ #2:\ }}

% Lemma
\newcommand{\lm}[1]{\mbox{} \vspace{-1.5em} \mbox{} \begin{LM} \label{#1}}
\newcommand{\lmr}[2]{\begin{LM}[{[#1]}] \label{#2} }
\newcommand{\elm}{\end{LM} \mbox{} \vspace{-1.5em} \mbox{} }
\newcommand{\replm}[2]{\noindent {\bf Lemma}~\ref{#1} {\em #2} \vspace{.1em}}
\newcommand{\primelm}[2]{\noindent {\bf Lemma}~\ref{#1}$'$ {\em #2}}
\newcommand{\rlm}[1]{Lemma~\ref{#1}}
\newcommand{\rlms}[2]{Lemmas~\ref{#1} and \ref{#2}}
\newcommand{\pflm}[1]{\noindent {\bf Proof of Lemma \ref{#1}:\ }}
\newcommand{\pflmr}[2]{\noindent {\bf Proof of Lemma \ref{#1}\ #2:\ }}

% Sub-Lemma
\newtheorem{LLM}{Lemma}[LM]
\newcommand{\llm}[1]{\mbox{} \vspace{-1.5em} \mbox{} \begin{LLM} \label{#1}}
\newcommand{\ellm}{\end{LLM} \mbox{} \vspace{-1.5em} \mbox{} }

% Claim
\newtheorem{CL}{Claim}							
\newcommand{\cl}[1]{\mbox{} \vspace{-1.5em} \mbox{} \begin{CL} \label{#1}}
\newcommand{\ecl}{\end{CL}}
\newcommand{\rcl}[1]{Claim~\ref{#1}}
\newcommand{\rcls}[2]{Claims~\ref{#1} and~\ref{#2}}
\newcommand{\pfcl}[1]{\noindent {\bf Proof of Claim \ref{#1}:\ }}

% Corollary
\newtheorem{COR}[TM]{Corollary}
\newcommand{\cor}[1]{\mbox{} \vspace{-1.5em} \mbox{} \begin{COR} \label{#1}}
\newcommand{\ecor}{\end{COR}}
\newcommand{\repcor}[2]{\noindent {\bf Corollary}~\ref{#1} {\em #2}}
\newcommand{\rcor}[1]{Corollary~\ref{#1}}
\newcommand{\pfcor}[1]{\noindent {\bf Proof of Corollary \ref{#1}:\ }}

% Conjecture
\newcommand{\cj}[1]{\begin{CJ} \label{#1}}
\newcommand{\ecj}{\end{CJ}}
\newcommand{\repcj}[2]{\noindent {\bf Conjecture}~\ref{#1} {\em #2}}
\newcommand{\rcj}[1]{Conjecture~\ref{#1}}
\newcommand{\pfcj}[1]{\noindent {\bf ``Proof'' of Conjecture \ref{#1}:\ }}

% Definition
\newtheorem{DF}{Def$^n$}[section]
\newcommand{\df}[1]{ \bsinglespace \noindent {\bf Def$^n$:} #1 \esinglespace}
\newcommand{\dfi}[1]{ \bsinglespace \noindent {\bf Def$^n$:} \parbox[t]{6 in}{#1} \esinglespace}
\newcommand{\dfr}[1]{\begin{DF}[{[#1]}]}

% Section
\newcommand{\sectiona}[1]{\vspace{-0em} \section{#1} \vspace{-0em} }
\newcommand{\subsectiona}[1]{\vspace{-0em} \subsection{#1} \vspace{-0em} }
\newcommand{\sectionc}[1]{\vspace{.5em} \begin{center} {\LARGE\bf #1} \end{center} \vspace{-2 em}  \noindent}
\newcommand{\subsectionb}[1]{\vspace{1em}\noindent {\bf #1}}
\newcommand{\subsectionc}[1]{\vspace{.5em} \begin{center} {\large\bf #1} \end{center}\vspace{-.5em} }
\newcommand{\rsc}[1]{Section~\ref{#1}}
\newcommand{\rsec}[1]{Section~\ref{#1}}
\newcommand{\rsecs}[2]{Sections~\ref{#1} and~\ref{#2}}

% Chapter
\newcommand{\rcht}[1]{Chapter~\ref{#1}}
\newcommand{\rchpt}[1]{Chapter~\ref{#1}}

% Equation
\newcommand{\req}[1]{Equation~\ref{#1}}
\newcommand{\reqf}[1]{(\ref{#1})}
\newcommand{\reqs}[2]{Equations~\ref{#1} and~\ref{#2}}

% Code
\newcommand{\bcodefrag}{
\begin{tabbing}
\hs{0.2in} \= \hs{0.2in} \= \hs{0.2in} \= \hs{0.2in} \= \hs{0.2in} \= \hs{0.2in} \= \hs{0.2in} \= 
\hs{0.2in} \= \hs{0.2in} \= \hs{0.2in} \= \hs{0.2in} \= \hs{0.2in} \= \hs{0.2in} \= \kill}
\newcommand{\ecodefrag}{\end{tabbing}}

\newcommand{\bcode}[3]{
\bd
\i[algorithm] #1 
\i[\bm$\left< pre\!-\!cond \right>$:] #2
\i[\bm$\left< post\!-\!cond \right>$:] #3
\ed
\vs{-1.5em}
\bcodefrag
begin \\}
\newcommand{\ecode}{end algorithm \end{tabbing}}
\newcommand{\bcodeTogether}[2]{
\bd
\i[algorithm] #1 
\i[\bm$\left< pre\ \&\ post\!-\!cond \right>$:] #2
\ed
\vs{-.5em}
\bcodefrag
begin \\}

\newcommand{\loopinv}[1]{\parbox[t]{5in}{\vs{-2em} 
\bd \i[\bm$\left<loop\!-\!invariant\right>$:] #1 \ed}}


% Induction Hypothesis
\newcommand{\Ih}[1]{Condition~(\ref{#1})}
\newcommand{\ih}[1]{condition~(\ref{#1})}
\newcommand{\ihs}[2]{conditions~(\ref{#1}) and~(\ref{#2})}
\newcommand{\ihss}[2]{conditions~(\ref{#1}-\ref{#2})}

% Exercise
\newtheorem{EX}{Exercise}[section]

\newcommand{\exerciseA}[2]{\begin{EX}\label{#2} (See solution in
  \rsc{chpt solutions}) #1 \end{EX}}
% answer in the notes
\newcommand{\exerciseNA}[2]{\begin{EX}\label{#2} #1 \end{EX}}
% answer written but not in the notes
\newcommand{\exerciseNNA}[2]{\begin{EX}\label{#2} #1 \end{EX}} 
% No answer written
\newcommand{\rexercise}[1]{Exercise~\ref{#1}}


% Figure
\newcommand{\rfig}[1]{Figure~\ref{#1}}
\newcommand{\ifig}[2]{\psfig{file=#2.eps,height=#1}}
% \newcommand{\ifig}[2]{file = #2}
\newcommand{\ifigw}[2]{\psfig{file=#2.eps,width=#1}}
\newcommand{\fig}[2]{\centerline{\ifig{#1}{#2}}}
\newcommand{\figw}[2]{\begin{figure}[hbt] 
                     \centerline{\ifigw{#1}{#2}} 
                     \end{figure}}
\newcommand{\figc}[4]{\begin{figure}[hbt] 
                     \centerline{\ifig{#1}{#2}} 
                     \caption{#3} \label{#4}
                     \end{figure}}
% \newcommand{\figwc}[4]{\begin{figure}[hbt] 
%                      \centerline{\ifigw{#1}{#2}} 
%                      \caption{#3} \label{#4}
%                      \end{figure}}
\newcommand{\figwc}[4]{\begin{figure}[hbt] 
                     \ifigw{#1}{#2}
                     \caption{#3} \label{#4}
                     \end{figure}}
\newcommand{\figt}[6]{\begin{figure}[hbt] 
                     \centerline{\raisebox{#1}{\ifig{#2}{#3}} \mbox{ } 
                                 \raisebox{#4}{\ifig{#5}{#6}}}
                     \end{figure}}
\newcommand{\figct}[8]{\begin{figure}[hbt] 
                     \centerline{\raisebox{#1}{\ifig{#2}{#3}} \mbox{ } 
                                 \raisebox{#4}{\ifig{#5}{#6}}}
                     \caption{#7} \label{#8}
                     \end{figure}}
\newcommand{\Fig}[2]{\cp{2in}{\rule{0in}{#1} FIG(#2)}}

%\begin{figure}[hbt] 
%\centerline{}
%\caption{} 
%\label{fig stack}
%\end{figure}


% Game
\newtheorem{GM}{Game}							
\newcommand{\game}[1]{\mbox{} \vspace{-1.5em} \mbox{} \begin{GM}  \label{#1}}
\newcommand{\egm}{\end{GM}}
\newcommand{\rgm}[1]{Game~\ref{#1}}
\newcommand{\rgms}[2]{Games~\ref{#1} and~\ref{#2}}



\newcommand{\rright}{\hspace{.5cm} \Rightarrow \hspace{.5cm}}
\newcommand{\ab}{\allowbreak}

\newcommand{\lra}{\vphantom{2}}
\newcommand{\lrb}{\vphantom{2^2}}
\newcommand{\lrc}{\vphantom{2^{2^2}}}
\newcommand{\lrd}{\vphantom{2^{2^{2^2}}}}
\newcommand{\lre}{\vphantom{2^{2^{2^{2^{2^2}}}}}}
\newcommand{\lefta}[1]{\left#1 \lra \right.}
\newcommand{\leftb}[1]{\left#1 \lrb \right.}
\newcommand{\leftc}[1]{\left#1 \lrc \right.}
\newcommand{\leftd}[1]{\left#1 \lrd \right.}
\newcommand{\lefte}[1]{\left#1 \lre \right.}
\newcommand{\righta}[1]{\left. \lra \right#1}
\newcommand{\rightb}[1]{\left. \lrb \right#1}
\newcommand{\rightc}[1]{\left. \lrc \right#1}
\newcommand{\rightd}[1]{\left. \lrd \right#1}
\newcommand{\righte}[1]{\left. \lre \right#1}
\newcommand{\biga}[1]{\left#1 \lra \right.}
\newcommand{\bigb}[1]{\left#1 \lrb \right.}
\newcommand{\bigc}[1]{\left#1 \lrc \right.}
\newcommand{\bigd}[1]{\left#1 \lrd \right.}
\newcommand{\bige}[1]{\left#1 \lre \right.}

\renewcommand{\(} {\left(}
\renewcommand{\)} {\right)}
\renewcommand{\[} {\left[}
\renewcommand{\]}{\right]}

%******************

\newcommand {\qu}{\quad}
\newcommand {\pf}{\medskip\noindent{\bf Proof:}\qu}
   % \newcommand {\qed}{\hfil\break\null\hspace{14cm}$\Box$}
\newcommand {\alg}{\medskip\noindent{\bf Algorithm:}\qu}
\newcommand{\epf}{$\Blacksquare$}
\newcommand{\epfa}{\ \mbox{ } \Blacksquare}

\newcommand {\giv}  {\rightarrow}
\newcommand {\givs}  {\rightarrow}
\newcommand {\gives}  {\rightarrow}
\newcommand {\Givs}  {\Rightarrow}
\newcommand {\Gives}  {\Rightarrow}

\newcommand {\ddd}  {,\ldots,}
\newcommand {\X}    {\overline{X}}
%\newcommand {\x}[1] {\overline{x_{#1}}}
%\newcommand {\xx}   {\overline{x}}
\newcommand {\yy}   {\overline{y}}
\newcommand {\zz}   {\overline{z}}

\renewcommand {\a}    {\alpha}
\renewcommand {\b}    {\beta}
  \newcommand {\e}    {\epsilon}
\renewcommand {\d}    {\delta}
   %   \newcommand {\D}    {\Delta}
\renewcommand {\r}    {\rho}
% \r = \right
  \newcommand {\g}    {\gamma}
  \newcommand {\G}    {\Gamma}
\renewcommand{\l}{\lambda}
%  \newcommand {\P}    {\Pi}
  \newcommand {\p}    {\pi}
  \newcommand {\s}    {\sigma}
\renewcommand {\S}    {\Sigma}
\renewcommand {\t}    {\tau}
  \newcommand {\w}    {\omega}
  \newcommand {\x}    {\chi}
%  \newcommand {\Tilde} {$\sim$}
\renewcommand {\O} {\Omega}
\newcommand{\bigO}{{\cal O}}
\newcommand {\T} {\Theta}
\newcommand {\pmnew}{{\tiny \begin{array}{c} + \\ \vspace{-.5em} - \end{array}}}

\newcommand{\bit}{\{0,1\}}
\newcommand{\bits}{\{0,1\}}

\newcommand{\etal}{{\em et al.}} %follow with \ to avoid end-of-sent space
% \newcommand{\land}{\wedge}
% \newcommand{\lor}{\vee}
% \newcommand{\lnot}{\neg}
\newcommand{\basis}{\{\land,\lor,\lnot\}}
\newcommand{\parity}{\bigoplus}
\newcommand{\Min}{{\rm Min}}
\newcommand{\Max}{{\rm Max}}
\newcommand{\Avg}{{\rm Avg}}
\newcommand{\Exp}{{\rm Exp}}
\newcommand{\pr}{{\rm Pr}}
\newcommand{\Var}{{\rm Var}}
\newcommand{\cross}{\times}
\newcommand{\nlog}{{\rm \scriptsize (-)} \log}
\newcommand{\overbar}{\overline}
\newcommand{\union}{\cup}
\newcommand{\dunion}{\stackrel{\cdot}{\union}}
\renewcommand{\th}[1]{$#1^{\em th}\/$}                 %used to print "i-th"
\newcommand{\st}[1]{#1^{st}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% \newcommand{\mnote}[1]{\marginpar{\scriptsize\it
%             \begin{minipage}[t]{1in}
%               \raggedright #1
%             \end{minipage}}}
\newcommand{\np}{\newpage}
\newcommand{\vs}[1]{\mbox{} \vspace{#1} \mbox{}}
\newcommand{\hs}[1]{\mbox{} \hspace{#1} \mbox{}}
\newcommand{\ul}[1]{\underline{\Large #1}}
\newcommand{\dzs}{\hspace{.5em}}
% \renewcommand{\tt}[1]{\begin{center} \underline{\LARGE #1} \end{center}}
% \newcommand{\TT}[1]{\begin{center} \underline{\Huge #1} \end{center}}
% \newcommand{\ttt}[2]{\begin{center} \underline{\LARGE #1} \\ {\Large  #2} \end{center}}
\newcommand{\ttt}[1]{\begin{center} \underline{\LARGE #1} \end{center}}

\newcommand{\ct}[1]{\begin{center} {\Large #1} \end{center}}
\newcommand{\cp}[2]{\begin{center} \parbox{#1}{\Large #2} \end{center}}
\newcommand{\CT}[1]{\begin{center} {\LARGE #1} \end{center}}
\newcommand{\CP}[2]{\begin{center} \parbox{#1}{\LARGE #2} \end{center}}
\newcommand{\pb}[2]{\parbox{#1}{#2}}
\newcommand{\mb}[1]{\mbox{#1}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
\newcommand{\btb}{\begin{tabular}}
\newcommand{\etb}{\end{tabular}}
\newcommand{\ba}{\begin{array}}
\newcommand{\ea}{\end{array}}
\newcommand{\bt}{\vs{-.2in} \begin{tabbing}}
\newcommand{\et}{\end{tabbing} \vs{-.1in}}
\renewcommand{\i}{\item}
\newcommand{\im}[1]{\i \hspace{0pt}\marginpar{\hspace{12pt}(#1)}}
\newcommand{\ds}{\hspace{.1cm} \displaystyle}
\newcommand{\dsum}{\sum}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*} \vspace{0cm} \newline}
\newcommand{\bean}{\begin{eqnarray}}
\newcommand{\eean}{\end{eqnarray} \vspace{0cm} \newline}
\newcommand{\bk}{\linebreak[4]}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newenvironment{headingside}[1]{
   \noindent
   \begin{minipage}[t]{1.375in}
       \bf #1
   \end{minipage}
   \begin{minipage}[t]{5.2in}}
{  \end{minipage}
   \bigbreak
   \bigbreak}

\newenvironment{headingbot}[1]{
   \noindent
   \begin{minipage}[t]{6in}
       \bf #1
   \end{minipage}

   \vspace*{0.07in}
   \hspace*{0.125in}
   \begin{minipage}[t]{6.3in}}
{  \end{minipage}
   \bigbreak
   \bigbreak}

\newenvironment{headingbottight}[1]{
   \noindent
   \begin{minipage}[t]{6in}
       \bf #1
   \end{minipage}

   \vspace*{0.07in}
   \hspace*{0.125in}
   \begin{minipage}[t]{6.3in}}
{  \end{minipage} 
   \bigbreak}

\newcommand{\heading}[1]{
   \noindent
   \begin{minipage}[t]{3in}
       \bf #1
   \end{minipage}}

\newenvironment{refperson}[1]{
   \begin{minipage}[t]{2.1in}
       $\cdot$ #1
   \end{minipage}
   \hspace*{0.125in}
   \begin{minipage}[t]{2.8in}}
{  \end{minipage}
   \medskip}

\newenvironment{listpe}{ 
\begin{list}{$\cdot$}{
   \setlength{\labelwidth}{0in}
   % no paragraphs
      \setlength{\itemsep}{0in}
      \setlength{\parsep}{0in}
   % 1st line not extended
      \setlength{\itemindent}{0in}
      \setlength{\leftmargin}{0in}
   }}
{\end{list}}

\newenvironment{listpE}{ %no paragraphs,  1st line Extended
\begin{list}{$\cdot$}{
    \setlength{\labelwidth}{0in}
    % no paragraphs
      \setlength{\itemsep}{0in}
      \setlength{\parsep}{0in}
    % 1st line Extended
      \setlength{\itemindent}{-\leftmargin}
   }}
{\end{list}}

\newenvironment{listPe}{ 
\begin{list}{$\cdot$}{
   \setlength{\labelwidth}{0in}
   % Paragraphs
      \setlength{\parsep}{0in}
   % 1st line not extended
      \setlength{\itemindent}{0in}
      \setlength{\leftmargin}{0in}
   }}
{\end{list}}

\newenvironment{listPE}{ 
\begin{list}{$\cdot$}{
   \setlength{\labelwidth}{0in}
   % Paragraphs
       \setlength{\parsep}{0in}
   % 1st line Extended
      \setlength{\itemindent}{-\leftmargin}
   }}
{\end{list}}

\newenvironment{listbib}{ 
\begin{list}{$\cdot$}{
   \setlength{\labelwidth}{.4in}
   % Paragraphs
      \setlength{\parsep}{0in}
   % 1st line not extended
      \setlength{\itemindent}{0in}
      \setlength{\leftmargin}{0in}
   }}
{\end{list}}

\newenvironment{bibsub}{ 
\begin{list}{$\cdot$}{
   \setlength{\labelwidth}{.4in}
   % Paragraphs
      \setlength{\parsep}{0in}
   }}
{\end{list}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\Blacksquare}{\rule{.8em}{.8em}}
   % \newcommand{\blacksquare}{\rule{.8em}{.8em}}
% \linebreak[4]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\iif}{\bf if \rm }
\newcommand{\tthen}{\bf then \rm  }
\newcommand{\eelse}{\bf else \rm }
\newcommand{\wwhile}{\bf while \rm }
\newcommand{\ddo}{\bf do \rm }
\newcommand{\lloop}{\bf loop \rm }
\newcommand{\ffor}{\bf for \rm }
\newcommand{\rrepeat}{\bf repeat \rm }
\newcommand{\eend}{\bf end \rm }
\newcommand{\pprocedure}{\bf procedure \rm }
\newcommand{\ffunction}{\bf function \rm }
\newcommand{\aalgorithm}{\bf algorithm \rm}
\newcommand{\PPreCond}{\bf PreCond: \rm }
\newcommand{\PPostCond}{\bf PostCond: \rm }
\newcommand{\PPreCondnew}{\bf PreCond': \rm }
\newcommand{\PPostCondnew}{\bf PostCond': \rm }
\newcommand{\LLoopInv}{\bf Loop-Invariant: \rm }
\newcommand{\LLoopInvnew}{\bf Loop-Invariant': \rm }
\newcommand{\LI}{\bf LI: \rm }
\newcommand{\rreturn}{\bf return \rm }


