% Cross-references for handout numbers and chapter numbers.

%\input{xrefs}
\newcommand{\cents}{\hbox{\rm c \hskip -1.75ex /}}  % copyright 1989 PWR
\newcommand{\legendre}[2]{{#1 \overwithdelims() #2}}
\newcommand{\jacobi}[2]{\legendre{#1}{#2}}      % for we all know that the
                                                % the jacobi symbol is defined
                                                % in terms of the legendre
                                                % symbol.

\newcommand{\xboldmath}[1]{{\boldmath#1}}
\newcommand{\xunboldmath}{}
\newcommand{\bit}{}

\newcounter{subprobno}
\newcounter{probno}
\newcommand{\problem}{
        \setcounter{subprobno}{0}
        \addtocounter{probno}{1} \bigskip
        \noindent {\bf Problem \theprobno.\ }}
\newcommand{\Problem}{
        \setcounter{subprobno}{0}
        \addtocounter{probno}{1}
        \noindent {\bf Problem \theprobno.\ }}
\newcommand{\subproblem}{
        \addtocounter{subprobno}{1} \bigskip
        (\alph{subprobno})\ }

\newcommand{\problempart}{\subproblem}

\newcommand{\solstart}{{\bf Solution: }}

\newcommand{\solution}{\problem}
\newcommand{\solutionpart}{\subproblem}
\newcommand{\solpart}{\subproblem}


\newlength{\toppush}
\setlength{\toppush}{2\headheight}
\addtolength{\toppush}{\headsep}

\newcommand{\course}{6.851/18.414: Algorithms}

% \htitle  usage: \htitle{handout-number}{handout-title}{date}
\newcommand{\htitle}[3]%
{\noindent\vspace*{-\toppush}\newline%
\parbox{6.5in}%
{\course\hfill {\bf Handout #1}\newline
Massachusetts Institute of Technology\hfill#3\vspace*{-.5ex}\newline
\mbox{}\hrulefill\mbox{}}\vspace*{1ex}\mbox{}\newline
\begin{center}{\Large\bf #2}\end{center}}

% \handout  usage: \handout{tag}{handout-title}{handout-date}
\newcommand{\handout}[3]{\thispagestyle{empty}
 \markboth{Handout \protect\ref{#1}: #2}{Handout \protect\ref{#1}: #2}
 \pagestyle{myheadings}\htitle{\protect\ref{#1}}{#2}{#3}}

% \handoutnonum  usage: \handoutnonum{handout-title}{handout-date}
\newcommand{\handoutnonum}[2]{\thispagestyle{empty}
 \markboth{Handout:      #1}{Handout: #1}
 \pagestyle{myheadings}\htitle{#1}{#1}{#2}}



\newcommand{\handoutt}[3]{\thispagestyle{empty}
 \markboth{{Initials:$\qquad\qquad$Handout}
\protect\ref{#1}: #2}{Initials:$\qquad\qquad$Handout \protect\ref{#1}: #2}
 \pagestyle{myheadings}\htitle{\protect\ref{#1}}{#2}{#3}}

\newcommand{\htitlewithouttitle}[2]%
{\noindent\vspace*{-\toppush}\newline%
\parbox{6.5in}%
{\course\hfill {\bf Handout #1}\newline
Massachusetts Institute of Technology\hfill#2\vspace*{-.5ex}\newline
\mbox{}\hrulefill\mbox{}}\vspace*{1ex}\mbox{}\newline}

\newcommand{\handoutwithouttitle}[2]{\thispagestyle{empty}
 \markboth{Handout \protect\ref{#1}}{Handout \protect\ref{#1}}
 \pagestyle{myheadings}\htitlewithouttitle{\protect\ref{#1}}{#2}}

% \Pset  usage: \Pset{problem-set-number}{out-date}{due-date}
\newcommand{\Pset}[3]%
{\handout{ps#1}{Problem Set #1}{#2}

\centerline{
\underline{{\bf Due:}} {\bf Beginning of class, Wednesday, #3.}}}

% \Psol  usage: \Pset{problem-set-number}{soln-out-date}
\newcommand{\Psol}[2]%
{\handout{ps#1-solutions}{Problem Set #1 Solutions}{#2}}





% \mychaptertitle  usage: \mychaptertitle{chapter-number}{chapter-title}
\newcommand{\mychaptertitle}[2]%
{\noindent\vspace*{-\toppush}\newline%
\parbox{6.5in}%
{{\sl Lecture Notes in Algorithms}\hfill {\bf Chapter #1}\newline
\copyright 1987 by T. Cormen, C. E. Leiserson, and R. L. Rivest\hfill%
{\small (rev. \today)}\vspace*{-.5ex}\newline
\mbox{}\hrulefill\mbox{}}\vspace*{1ex}\mbox{}\newline
\begin{center}{\Large\bf Chapter #1: #2}\end{center}}

% \mychapter  usage: \mychapter{tag}{chapter-title}
\newcommand{\mychapter}[2]{\thispagestyle{empty}
 \markboth{Chapter \protect\ref{#1}: #2}{Chapter \protect\ref{#1}: #2}
 \pagestyle{myheadings}\mychaptertitle{\protect\ref{#1}}{#2}}

%%\setlength{\oddsidemargin}{0pt}
%%\setlength{\evensidemargin}{0pt}
%%\setlength{\textwidth}{6.5in}
%%\setlength{\topmargin}{0in}
%%\setlength{\textheight}{8.5in}

%\newcommand{\gets}{\leftarrow}
%\newcommand{\to}{\rightarrow}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\card}[1]{\left| #1\right|}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\ang}[1]{\ifmmode{\left\langle #1 \right\rangle}
   \else{$\left\langle${#1}$\right\rangle$}\fi}
        % the \if allows use outside mathmode,
        % but will swallow following space there!
\newcommand{\prob}[1]{\Pr\left\{ #1 \right\}}
\newcommand{\Var}{\mathop{\rm Var}\nolimits}
\renewcommand{\choose}[2]{{{#1}\atopwithdelims(){#2}}}
\def\pmod#1{\allowbreak\mkern12mu({\rm mod}\,\,#1)}
%\newcommand{\thm}{\bigskip\noindent{\bf Theorem.}\hspace{1em}}
%\newcommand{\lem}{\bigskip\noindent{\bf Lemma.}\hspace{1em}}
%\newcommand{\proof}{\noindent{\em Proof.}\hspace{1em}}
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qed}{\hfill\hfill\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}\smallskip}
\newenvironment{defn}{\medskip\noindent{\bf Definition.}\hspace{1em}}{\medskip}
\newenvironment{thm}{\medskip\noindent{\bf Theorem.}\hspace{1em}\em}{\medskip}
\newenvironment{namedthm}[1]{\medskip\noindent{\bf Theorem.} (#1.)\hspace{1em}\em}{\medskip}
\newenvironment{lem}{\medskip\noindent{\bf Lemma.}\hspace{1em}\em}{\medskip}
\newenvironment{namedlem}[1]{\medskip\noindent{\bf Lemma.} (#1.)\hspace{1em}\em}{\medskip}
\newenvironment{claim}{\medskip\noindent{\bf Claim.}\hspace{1em}\em}{\medskip}
\newenvironment{cor}{\medskip\noindent{\bf Corollary.}\hspace{1em}\em}{\medskip}
\newcommand{\eqnref}[1]{(\protect\ref{#1})}

\newlength{\ptabwidth} \settowidth{\ptabwidth}{\bf then }
\newcommand{\ptab}{\hspace*{\ptabwidth}}
\newlength{\progwidth} \setlength{\progwidth}{\textwidth}
\addtolength{\progwidth}{-3em}
\newcommand{\programwithcost}[1]{\newline\hspace*{2em}
 \parbox{\progwidth}{\begin{flushleft}\begin{tabular}{clcc}
 & & {\em cost} & {\em times}\\
 #1
 \end{tabular}\end{flushleft}}\newline}
\newcommand{\twodots}{\mathinner{\ldotp\ldotp}}
\newcommand{\programwithoutcost}[1]{\newline\hspace*{2em}
 \parbox{\progwidth}{\begin{flushleft}\begin{tabular}{cl}
 #1\end{tabular}\end{flushleft}}\newline}
\newcommand{\proc}[1]{\mbox{\it #1}}
\newcommand{\program}[1]{\programwithoutcost{#1}}
\newcommand{\progname}[1]{\multicolumn{2}{l}{#1}}
\newcommand{\prognamewithcost}[1]{\multicolumn{4}{l}{#1}}

\renewcommand{\cases}[1]{\left\{ \begin{array}{ll}#1\end{array}\right.}
\newcommand{\cif}[1]{\mbox{if $#1$}}
\newcommand{\fakepar}{\vspace*{-\baselineskip}\vspace*{-\parskip}\vspace*{-\medskipamount}\mbox{}\newline}
%\newcommand{\example}{\medskip\mbox{}\newline\noindent{\bf Example.}\hspace*{1em}}
%\newcommand{\problem}[1]{\medskip\mbox{}\newline\noindent{\bf Problem #1.}\hspace*{1em}}

% Macros to make captions print with small type and 'Figure xx' in bold.
% \makeatletter
% \def\fnum@figure{{\bf Figure \thefigure}}
% \def\fnum@table{{\bf Table \thetable}}
% \long\def\@mycaption#1[#2]#3{\addcontentsline{\csname
%   ext@#1\endcsname}{#1}{\protect\numberline{\csname 
%   the#1\endcsname}{\ignorespaces #2}}\par
%   \begingroup
%     \@parboxrestore
%     \small
%     \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par
%   \endgroup}
% \def\mycaption{\refstepcounter\@captype \@dblarg{\@mycaption\@captype}}
% \makeatother
%\newcommand{\figcaption}[1]{\mycaption[]{#1}}
\newcommand{\figcaption}[1]{\caption[]{#1}}
 
\newcommand{\matx}[2]{\left(\begin{array}{*{#1}{c}}#2\end{array}\right)}

\newcommand{\reserve}{\mbox{$^*$}}



%**************************************************
%**************************************************
% stuff from clrmac.

\typeout{[[clrmac.tex version 1/8/90]]}

% Make small caps defined
\load{\normalsize}{\sc}
\load{\small}{\sc} 
\makeatletter

% Environment like description, but without a label.  Makes each item
% have a hanging indent.
\def\hanglistlabel#1{\hspace\labelsep}
\def\hanglist{\leftmarginii=1pc
\list{}{\labelsep=0pt\labelwidth\z@ \itemindent-1pc%\leftmargin
\let\makelabel\hanglistlabel}}
\let\endhanglist\endlist


% Make bold italic print as bold, if it's not otherwise defined.
\@ifundefined{bfi}{\newcommand{\bfi}{\bf}}{}

% Part numbers print in Roman uppercase.
\newcommand{\partref}[1]{\@Roman{\ref{#1}}}

% Allow chapters to start on even-numbered pages.
%% this is redefined in ah.sty << july 29
%\def\chapter{\clearpage \thispagestyle{empty}%%
% \global\@topnum\z@\global\partintroonfalse
%\@afterindentfalse \secdef\@chapter\@schapter}

% new macros I found in the text and answers not yet defined

\newcommand{\gray}{\id{d}}
\newcommand{\eqngray}{\eqnid{d}}
\newcommand{\black}{\id{f}}
\newcommand{\distance}{\id{d}}
\newcommand{\eqndistance}{\eqnid{d}}
\newcommand{\II}{{\cal I}} % Used to denote family of independent sets.
\newcommand{\I}{{\cal I}} % Used to denote family of independent sets.
\newcommand{\be}{\begin{eqnarray*}}
\newcommand{\ee}{\end{eqnarray*}}
\newlength{\digitwidth}
\settowidth{\digitwidth}{0}
\newcommand{\dtab}{\hspace*{\digitwidth}}
%\newcommand{\solution}[1]{\problem{#1}}
\newenvironment{solutions}{\begin{problems}}{\end{problems}}
%\newcommand{\solutionpart}{\problempart}
\newenvironment{solutionparts}{\begin{problemparts}}{\end{problemparts}}

% end new macros I found



\newcommand{\subheading}[1]{\subsubsection*{\xboldmath#1\xunboldmath}}

\newcommand{\inchapter}[1]{\label{ch:#1}\input{#1}}%% << need this?


\newcommand{\chapternotes}{\section*{Chapter notes}
\markright{Chapter notes}
\ifnum\c@chapter=1\gdef\thesection{}\fi}

\newcommand{\chapterproblems}{\section*{Problems}
\markright{Problems}}

% \newcommand{\comment}[1]{}
\long\def\comment#1{}   % allows a comment to span paragraph breaks

% Notes to ourselves:
\newcommand{\notefont}{\fivrm}
%\newcommand{\clrnote}[1]{\marginpar{\raggedright{\notefont #1}}\ignorespaces}
\def\clrnote#1{\ignorespaces}
%\newcommand{\clrpunt}[1]{\marginpar{\raggedright{\notefont #1}}\ignorespaces}
\def\clrpunt#1{\ignorespaces}
\newcommand{\sknote}[1]{\clrnote{SK, #1}}
\newcommand{\wjnnote}[1]{\clrnote{WJN, #1}}
\newcommand{\dwnote}[1]{\clrnote{DW, #1}}
\newcommand{\celnote}[1]{\clrnote{CEL, #1}}
\newcommand{\copyedit}[1]{\clrnote{COPYEDIT #1}}

% Where we stopped in revising a chapter:
\newcommand{\clrstop}{\noindent\mbox{}\hrulefill\mbox{}}

%\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\smallset}[1]{\{ #1 \}}
%\newcommand{\abs}[1]{\left| #1\right|}
%\newcommand{\card}[1]{\left| #1\right|}
%\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
%\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
%\newcommand{\ang}[1]{\langle#1\rangle}
%\newcommand{\ang}[1]{\ifmmode{\left\langle #1 \right\rangle}
%   \else{$\left\langle${#1}$\right\rangle$}\fi}
        % the \if allows use outside mathmode,
        % but will swallow following space there!
%\newcommand{\prob}[1]{\Pr\left\{ #1 \right\}}
\newcommand{\expect}[1]{{\rm E}\left[ #1 \right]}
\newcommand{\expectsq}[1]{{\rm E}^2\left[ #1 \right]}
\newcommand{\variance}[1]{{\rm Var}\left[ #1 \right]}
%\newcommand{\Var}{\mathop{\rm Var}\nolimits}   %variance
\renewcommand{\choose}[2]{{{#1}\atopwithdelims(){#2}}}
\def\pmod#1{\allowbreak\mkern12mu({\rm mod}\,\,#1)}
\newcommand{\matxspace}{\hspace*{.25pc}}
%\newcommand{\matx}[2]{\left(\matxspace\begin{array}{*{#1}{c}}#2\end{array}\matxspace\right)}
\newcommand{\rmatx}[2]{\left(\matxspace\begin{array}{*{#1}{r}}#2\end{array}\matxspace\right)}
%\newcommand{\deter}[2]{\left|\matxspace\begin{array}{*{#1}{c}}#2\end{array}\matxspace\right|}
% Redefined by THC to leave \matxspace after left paren and before right paren.
\def\bordermatrix#1{\begingroup \m@th
  \setbox\z@\vbox{\def\cr{\crcr\noalign{\kern2\p@\global\let\cr\endline}}%
    \ialign{$##$\hfil\kern2\p@\kern\p@renwd&\thinspace\hfil$##$\hfil
      &&\quad\hfil$##$\hfil\crcr
      \omit\strut\hfil\crcr\noalign{\kern-\baselineskip}%
      #1\crcr\omit\strut\cr}}%
  \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}%
  \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}%
  \setbox\tw@\hbox{$\kern\wd\@ne\kern-\p@renwd\matxspace\left(\matxspace\kern-\wd\@ne
    \global\setbox\@ne\vbox{\box\@ne\kern2\p@}%
    \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\baselineskip}\,\matxspace\right)$}%
  \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup}
\newcommand{\norm}[1]{\left\| #1 \right\|}
\newcommand{\cofactor}[1]{{\tilde{#1}}}
\newcommand{\eqnline}{\\[.75ex]}
\newcommand{\bigeqnline}{\\[1.75ex]}
\newcommand{\dollar}[1]{\$$#1$}
% Old \path definition that we've gone back to:
\newcommand{\path}[1]{\stackrel{#1}{\leadsto}}
\newcommand{\edge}{\rightarrow}
% \path definition that looked bad, so we went back to the old one:
% \newcommand{\path}[1]{\mathrel{\mathop{\rightarrow}\limits^{*}_{#1}}}
\newcommand{\namededge}[3]{#1\mathrel{\mathop{\rightarrow}\limits_{#3}}#2}
% More symbols that looked bad, so we punted them:
%\newcommand{\uedge}{\mathrel{\mbox{$\bullet\hspace*{-.2em}$\xboldmath$-$\xunboldmath$\hspace*{-.2em}\bullet$}}}
%\newcommand{\upath}[1]{\mathrel{\mathop{\mbox{$\bullet\hspace*{-.2em}$\xboldmath$-$\xunboldmath$\hspace*{-.2em}\bullet$}}\limits^{*}_{#1}}}
%\newcommand{\nameduedge}[3]{#1\mathrel{\mathop{\mbox{$\bullet\hspace*{-.2em}$\xboldmath$-$\xunboldmath$\hspace*{-.2em}\bullet$}}\limits_{#3}}#2}
\newcommand{\segment}[2]{\overline{#1#2}}
% Amy's attempt at fixing \dirsegment...
%\def\dirsegment#1#2{\vcenter{\ialign{##\cr\hrulefill\hskip1pt\lower1.87pt\hbox to0pt{\hss$\rightarrow$}\cr
%\noalign{\nointerlineskip}
%$\displaystyle#1#2$\cr}}}
% Old versions of \dirsegment, supposedly superceded by Amy's attempt.
%\newcommand{\dirsegment}[2]{{\boxmaxdepth=1000pt\relax\overrightarrow{#1#2}}}
\newcommand{\dirsegment}[2]{\overrightarrow{#1#2}}
%\newcommand{\subop}[2]{\mathbin{\mathop{#1_{#2}}}}

\renewcommand{\P}{\func{\mbox{}P}}
\newcommand{\eqnP}{\eqnfunc{\mbox{}P}}
\newcommand{\NP}{\func{NP}}
\newcommand{\NPC}{\func{NPC}}
\newcommand{\coNP}{\func{co-NP}}
\newcommand{\comp}[1]{\overline{#1}}
\newcommand{\red}{\leq_{\rm P}}
\newcommand{\emptystring}{\varepsilon}

\newcommand{\Mz}{{\makebox[0.7ex]{$\cdot$}}}
\newcommand{\Mp}{{\makebox[0.7ex]{{\tt +}}}}
\newcommand{\Mm}{{\makebox[0.7ex]{{\tt -}}}}

\newcommand{\se}{^{[0]}}
\newcommand{\so}{^{[1]}}

\newcommand{\wrong}[1]{\hspace*{#1}\Longleftarrow\mbox{{\it wrong!!}}}
% Command that works like \stackrel but for operands, not binary operators.
\newcommand{\stackop}[2]{\mathop{\mathop{#2}\limits^{#1}}}
\newcommand{\amortized}[1]{\widehat{#1}}
\newcommand{\prefix}[2]{#1_{#2}}
% Regular \hat is too wimpy.
\renewcommand{\hat}[1]{\widehat{#1}}

\newcommand{\reals}{{\bf R}}
\newcommand{\integers}{{\bf Z}}
\newcommand{\naturals}{{\bf N}}
\newcommand{\rationals}{{\bf Q}}
\newcommand{\complex}{{\bf C}}
\newcommand{\w}{\omega}                 %% for fft chapter

\newcommand{\transpose}{^{\rm T}}
\newcommand{\transposeintext}{{\rm T}}
\newcommand{\scc}{^{\rm SCC}}

% Closed semiring identities
\newcommand{\oplusid}{\overline{0}}
\newcommand{\odotid}{\overline{1}}
\newcommand{\oident}{\overline{I}}

\newcommand{\flow}{f}
\newcommand{\capacity}{c}
\newcommand{\excess}{e}
\newcommand{\height}{h}
\newcommand{\Xbar}{\overline{X}}
\newcommand{\Ubar}{\overline{U}}
\newcommand{\admissible}{\flow,\height}

\newcommand{\hull}{{\rm CH}}

%% Number theory notations
\newcommand{\divs}{\mathrel |}
\newcommand{\ndivs}{\mathrel{\not|}}
\newcommand{\lcm}{\mathop{\rm lcm}\nolimits}
\newcommand{\sign}{\mathop{\rm sign}\nolimits}
\newcommand{\Zn}{\integers_n}
\newcommand{\Zp}{\integers_p}
\newcommand{\Zq}{\integers_q}
\newcommand{\dispLegendre}[2]{\left(\frac{#1}{#2}\right)}
\newcommand{\Legendre}[2]{\bigl(\frac{#1}{#2}\bigr)}
\newcommand{\ord}{\mathop{\rm ord}\nolimits}
\newcommand{\ind}{\mathop{\rm ind}\nolimits}
%% ``imod'' is an ``in-line mod'' that leaves less space before the parens.
\def\imod#1{\allowbreak \mkern10mu ({\rm mod}\,\,#1)}
%% boldface imod
\def\bimod#1{\allowbreak \mkern10mu (\hbox{mod}\,\,#1)}

%% String-matching notations
\newcommand{\isprefix}{\sqsubset}
\newcommand{\issuffix}{\sqsupset}
\newcommand{\suffix}{\sigma}
\newcommand{\gapchar}{\diamondsuit}

\newcommand{\Pp}[1]{P_{#1}}                     % prefix of P
% \newcommand{\Ps}[1]{P_{#1\twodots m}}         % suffix
\newcommand{\Pb}[2]{P[#1\twodots #2]}           % both endpoints
\newcommand{\Px}[1]{P[#1]}                      % index

\newcommand{\Prp}[1]{P'_{#1}}                   % prefix of P'
% \newcommand{\Prs}[1]{P'_{#1\twodots m}}       % suffix
\newcommand{\Prb}[2]{P'[#1\twodots #2]}         % both endpoints
\newcommand{\Prx}[1]{P'[#1]}                    % index

\newcommand{\Tp}[1]{T_{#1}}                     % prefix of T
% \newcommand{\Ts}[1]{T_{#1\twodots n}}         % suffix
\newcommand{\Tb}[2]{T[#1\twodots #2]}           % both endpoints
\newcommand{\Tx}[1]{T[#1]}                      % index

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% don't use the example environment; use ... ??

%\newenvironment{example}{\begin{xample}\rm}{\end{xample}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% theorem, proof, lemma, corollary, example

\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

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


\def\proof{\vskip-\lastskip\vskip-4pt\vskip1sp\subparagraph{Proof}}
\def\proofsketch{\vskip-\lastskip\vskip-4pt\vskip1sp\subparagraph{Sketch of proof}}
\def\endproof{\qed}

%\def\qed{ \penalty-250\hbox to 5pt{\hfill}\hfill\llap{\vrule height 5pt width 5pt}\vskip11pt}

\def\qed{\unskip\parfillskip=0pt~~~~\hfill\llap{\vrule height 5pt width 5pt}\vskip11pt\parfillskip=0pt plus 1fil\relax}

\let\thqed\qed

% \renewcommand this for horizontal/vertical struts within tables.
\newcommand{\tbox}{\makebox[0em]{\rule[0ex]{0em}{0ex}}}

%\newtheorem{xample}{Example}[chapter]

%\newcommand{\prooffootnote}[1]{\noindent{\em Proof.}\footnote{#1}\hspace{1em}}
%\newcommand{\eqnref}[1]{(\protect\ref{#1})}

%% \newenvironment{defn}{\medskip\noindent{\bf Definition.}\hspace{1em}}{\medskip}
%% Preceding line commented out 2/23/88 by RLR



\def\@makethmnumber#1#2{#1 #2}
\def\@begintheorem#1#2{\let\qed\thqed\vskip-\lastskip
\vskip-4pt\vskip1sp\paragraph{#1\ #2}}

\def\@endtheorem{\vskip11pt}

\def\@opargbegintheorem#1#2#3{\vskip-\lastskip
\vskip-4pt\vskip1sp\paragraph{#1\ #2\ (#3)}}



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

%%% command for putting definitions into boldface
% New style for defined terms, as of 2/23/88, redefined by THC.
%\newcommand{\defn}[1]{\xboldmath{\bit #1}\xunboldmath}
\newcommand{\defi}[1]{\xboldmath{\bit #1\/}\xunboldmath}

\newcommand{\const}[1]{\ifmmode\mathord{\mathcode`-="702D\sc #1\mathcode`\-="2200}\else$\mathord{\mathcode`-="702D\sc #1\mathcode`\-="2200}$\fi}

\newif\ifcodeinbox
%\newcommand{\proc}[1]{\ifli\else\ifcodeinbox
%\vrule width0pt height0pt depth 7pt\fi\fi%
%\ifmmode\mathord{\mathcode`-="702D\sc#1\mathcode`\-="2200}\else
%$\mathord{\mathcode`-="702D\sc#1\mathcode`\-="2200}$
%{\sc#1}\fi}


%\newcommand{\proc}[1]{%
%\ifmmode\mathord{\mathcode`-="702D\sc#1\mathcode`\-="2200}\else{\sc#1}\fi}

% Switches needed for tags in index entries.
\newif\ifinproblem
\global\inproblemfalse
\newif\ifinexercise
\global\inexercisefalse
\newif\ifindexasis
\global\indexasisfalse

\newcommand{\indextagspace}{\nolinebreak[4]\hspace*{.15em}\nolinebreak[4]}
\newcommand{\see}[2]{\global\indexasistrue\index{\string#1[{\string\it{see}\/} \string#2]}\global\indexasisfalse}
%\newcommand{\seealso}[2]{\global\indexasistrue\index{\string#1[{\string\it{see also}\/} \string#2]}\global\indexasisfalse}
\newcommand{\seealso}[2]{\global\indexasistrue\index{\string#1/ZZZZ{{\string\it{see also}\/} \string#2}[]}\global\indexasisfalse}
%\newcommand{\tabindex}[1]{\global\indexasistrue\index{#1[0\string\indextagspace{}tab.]}\global\indexasisfalse}
\newcommand{\figindex}[1]{\global\indexasistrue\index{#1[0\string\indextagspace{}fig.]}\global\indexasisfalse}
\newcommand{\fnindex}[1]{\global\indexasistrue\index{#1[0\string\indextagspace{}n.]}\global\indexasisfalse}

% The \string in these commands is needed to keep Tex from expanding
% the \proc too early.  God knows why this works. I don't...
\newcommand{\indexas}[2]{\global\indexasistrue%
\index{#1{#2}[]}%
\global\indexasisfalse}
\newcommand{\indexckt}[1]{\global\indexasistrue%
\index{#1{\string\ckt{#1}}[]}%
\global\indexasisfalse}
\newcommand{\indexlang}[1]{\global\indexasistrue%
\index{#1{\string\lang{#1}}[]}%
\global\indexasisfalse}
\newcommand{\indexproc}[1]{\global\indexasistrue%
\index{#1{\string\proc{#1}}[]}%
\global\indexasisfalse}
\newcommand{\procdecl}[1]{\global\indexasistrue%
\index{#1{\string\proc{#1}}[]}%
\global\indexasisfalse%
\index{#1}\printprocdecl{#1}}
\newcommand{\procdecltag}[2]{\global\indexasistrue%
\index{#1#2{\string\proc{#1}#2}[]}%
\global\indexasisfalse%
\index{#1#2}\printprocdecl{#1#2}}
\newcommand{\printprocdecl}[1]{\proc{#1}\vrule width0pt height0pt depth 7pt \relax}

\newcommand{\id}[1]{\ifmmode\mathord{\mathcode`-="702D\it #1\mathcode`\-="2200}\else$\mathord{\mathcode`-="702D\it #1\mathcode`\-="2200}$\fi}
\newcommand{\func}[1]{\ifmmode\mathop{\mathcode`-="702D\rm #1\mathcode`\-="2200}\nolimits\else$\mathop{\mathcode`-="702D\rm #1\mathcode`\-="2200}\nolimits$\fi}
\newcommand{\lang}[1]{\ifmmode\mathop{\mathcode`-="702D\rm #1\mathcode`\-="2200}\else$\mathop{\mathcode`-="702D\rm #1\mathcode`\-="2200}$\fi}
% The \eqn versions of the above are for use in eqnarrays because
%       \const, \proc, \id, \func, and \lang crash in eqnarrays.
\newcommand{\eqnconst}[1]{\mathord{\mathcode`-="702D\sc #1\mathcode`\-="2200}}
\newcommand{\eqnproc}[1]{\mathord{\mathcode`-="702D\sc #1\mathcode`\-="2200}}
\newcommand{\eqnid}[1]{\mathord{\mathcode`-="702D\it #1\mathcode`\-="2200}}
\newcommand{\eqnfunc}[1]{\mathop{\mathcode`-="702D\rm #1\mathcode`\-="2200}\nolimits}
\newcommand{\eqnlang}[1]{\mathop{\mathcode`-="702D\rm #1\mathcode`\-="2200}}
\newcommand{\ckt}[1]{\ifmmode\mathord{\mathcode`-="702D\sc #1\mathcode`\-="2200}\else$\mathord{\mathcode`-="702D\sc #1\mathcode`\-="2200}$\fi}
%\newcommand{\twodots}{\mathinner{\ldotp\ldotp}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% The Code environment %%%

%% The following commands are so we can automatically number and symbolically reference
%% lines.
%% The ``codelinenumber'' counter counts the current line number
\newcounter{codelinenumber}
%% The \zeroli command zeros the line number counter
\newcommand{\zeroli}{\setcounter{codelinenumber}0}
%% The \li command bumps the counter, outputs it, and skips some space
%% It also GLOBALLY sets the value of \@currentlabel, so that the \label
%% commands on the same line work OK.  The problem otherwise is that Latex
%% uses groups on each field of a line in tabbing mode, and this causes
%% \@currentlabel to get reset as soon as a field ends (e.g. at the \').
%% Now, the label can appear after the \\, as in
%%      \li \>\>$x\gets y$ \\ \label{li:assign-x}
%%

\def\@startline{\global\@curtabmar\@nxttabmar\relax
   \global\@curtab\@curtabmar\setbox\@curline\hbox
    {}\@startfield\global\lifalse\strut}

\newenvironment{code}{\global\codeinboxtrue%
\setbox\strutbox\hbox{\vrule height 9pt depth 4pt width0pt}%
\noindent\begin{tabbing}%
\zeroli\setlength{\tabbingsep}{1em}
\hspace*{1em}\=999\ifdoubledigit9\fi
\=\ {\bf if} \={\bf then} \={\bf if} \={\bf then}
        \={\bf if} \={\bf then} \={\bf if} \={\bf then} \={\bf if} \={\bf then}
        \={\bf if} \=\+\+\kill}{\end{tabbing}\global\codeinboxfalse}

\newif\ifdoubledigit
\newcommand{\codebox}[1]{\setbox0=\vbox{\begin{code}#1\end{code}}
\ifnum\c@codelinenumber>9\global\doubledigittrue\else\doubledigitfalse\fi
\vskip1sp\noindent\hskip-14pt%% 
\parbox{\textwidth}{\begin{code}\protect#1\end{code}}\global\let\@currentlabel=\thechapter}

\newenvironment{codewithcost}{\vskip1sp\global\codeinboxtrue
\noindent\hskip-14pt% 
\setbox\strutbox\hbox{\vrule height 9pt depth 4pt width0pt}%
\begin{tabbing}%
\zeroli\setlength{\tabbingsep}{1em}%
        \hspace*{1em}\=99
\=\ {\bf if} \={\bf then} \={\bf if} \={\bf then}
        \={\bf if} \={\bf then} \={\bf if} \={\bf then} {\bf if} {\bf then}
        \hspace*{0.75em}\={\bf if} {\bf then} \=\+\+\kill}{\end{tabbing}
\global\codeinboxfalse}

\newcommand{\codewithcostbox}[1]{\vskip1sp\noindent\hskip-14pt\parbox{\textwidth}{\begin{codewithcost}\protect#1\end{codewithcost}}}
\newenvironment{narrowcode}{\noindent\hskip-14pt%
\setbox\strutbox\hbox{\vrule height 9pt depth 4pt width0pt}%
\begin{tabbing}%
\setlength{\tabbingsep}{1em}%
        \hspace*{1em}\=99
\=\ \hspace*{1.25ex}\={\bf then}
        \=\hspace*{1.25ex}\={\bf then} \=\hspace*{1.25ex}\={\bf then}
        \=\hspace*{1.25ex}\={\bf then} \=\hspace*{1.25ex}\={\bf then}
        \=\hspace*{1.25ex}\=\+\+\kill}{\end{tabbing}}

\newcommand{\narrowcodebox}[1]{\vskip1sp\noindent\parbox{\textwidth}{\begin{narrowcode}\protect#1\end{narrowcode}}}



\newif\ifli
\newcommand{\li}{\global\litrue\stepcounter{codelinenumber}%
\ifdoubledigit%
\hbox to8pt{\hss\thecodelinenumber\hskip5pt}\else%
\hbox to8pt{\hskip-1pt\thecodelinenumber\hss}\fi%
\xdef\@currentlabel{\p@codelinenumber\thecodelinenumber}\'}

\let\widetable\table
\let\endwidetable\endtable


\newcommand{\widecodebox}[1]{\vskip1sp
\hbox to\textwidth{\llap{\hbox to 7.5pc{%
\parbox{35.5pc}{\vskip6pt\begin{code}\protect#1%
\end{code}\vskip6pt}\hss}}\hfill}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\For}{{\bf for} }
\newcommand{\To}{{\bf to} }
\newcommand{\By}{{\bf by} }
\newcommand{\Downto}{{\bf downto} }
\newcommand{\While}{{\bf while} }
\newcommand{\Repeat}{\>\>{\bf repeat}\'}
\newcommand{\Until}{\>\>{\bf until}\'}
\newcommand{\If}{{\bf if} }
\newcommand{\Then}{\>{\bf then}\>}
\newcommand{\Else}{\>{\bf else}\>}
\newcommand{\ElseIf}{{\bf elseif} }
\newcommand{\ElseNoIf}{{\bf else} }
\newcommand{\Do}{\>\>{\bf do}\'}
\newcommand{\Return}{{\bf return} }
\newcommand{\Comment}{$\!\rhd$ }
\newcommand{\Inparallel}{{\bf in parallel} }    %This should be flushed
\newcommand{\Goto}{{\bf goto} }
\newcommand{\Error}{{\bf error} } % optionally followed by string argument

% Parallel constructs
\newcommand{\Vector}{{\bf vector} }     % declare vectors
\newcommand{\Where}{{\bf where} }       % select processors
\newcommand{\declpv}[2]{\pv{#1}\colon{#2}}      %declare a vector
\newcommand{\pv}[1]{\id{#1}}            % vector
\newcommand{\pvang}[1]{\hskip-1pt\ang{#1}}
\newcommand{\pvs}[2]{\pv{#1}\pvang{#2}}%vector with nonvector subscript
\newcommand{\pvv}[2]{\pv{#1}\pvang{\pv{#2}}}  % vector with vector subscript
\newcommand{\pvd}[2]{\pv{#1}_{#2}}      % vector with ``real'' subscript
\newcommand{\pvds}[3]{\pvd{#1}{#2}\pvang{#3}} % vector with ``real'' and nonvector subscripts
\newcommand{\pvdv}[3]{\pvd{#1}{#2}\pvang{\pv{#3}}} % vector with ``real'' and vector subscripts

\newcommand{\eqnpv}[1]{\eqnid{#1}}              % vector
\newcommand{\eqnpvs}[2]{\eqnpv{#1}\pvang{#2}}   % vector with nonvector subscript
\newcommand{\eqnpvv}[2]{\eqnpv{#1}\pvang{\eqnpv{#2}}}  % vector with vector subscript
\newcommand{\eqnpvd}[2]{\eqnpv{#1}_{#2}}      % vector with ``real'' subscript
\newcommand{\eqnpvds}[3]{\eqnpvd{#1}{#2}\pvang{#3}} % vector with ``real'' and nonvector subscripts
\newcommand{\eqnpvdv}[3]{\eqnpvd{#1}{#2}\pvang{\pv{#3}}} % vector with ``real'' and vector subscripts

\newcommand{\self}{\const{I}}           % vector of processor indices
\newcommand{\myrow}{\self_{\id{row}}}   % vector of 2D row indices
\newcommand{\mycol}{\self_{\id{col}}}   % vector of 2D column indices


\renewcommand{\cases}[1]{\left\{ \begin{array}{ll}#1\end{array}\right.}
%\newcommand{\cif}[1]{\mbox{if $#1$}}
\newcommand{\cwhen}[1]{\mbox{when $#1$}}
%\newcommand{\fakepar}{\vspace*{-\baselineskip}\vspace*{-\parskip}\vspace*{-\medskipamount}\mbox{}\newline}


\def\useourcounter#1{\@nmbrlisttrue\def\@listctr{#1}}

\newcounter{problemnum}

% Redefined by THC for all problems within chapters.
%\newcommand{\theproblem}{\ifnum\c@part<1 1\else\Roman{part}\fi-\arabic{problemnum}}
\newcommand{\theproblem}{\arabic{chapter}-\arabic{problemnum}}

%\newlength{\problemwidth}\settowidth{\problemwidth}{\bf VIII-99}

% for problems at end of first chapter
%\newenvironment{chapterproblems}{\newpage
%\addcontentsline{toc}{fmatter}%
%{\protect\numberline{}Problems}
%\gdef\thesection{}
%       \section*{Problems for Chapter 1}
%       \markboth{Problems for Chapter 1}{Problems for Chapter 1}}{}

% Redefined by THC for all problems within chapters.
%\let\savethefigure\thefigure
%\newenvironment{problems}{\newpage\global\c@problemnum=0
%\global\c@figure=0
%\global\turnoffsectnumtrue
%\global\inproblemtrue
%\addcontentsline{toc}{fmatter}%
%{\protect\numberline{}Problems}
%\gdef\thesection{}\let\thefigure\theprobfigure
%       \section*{Problems for Part \thepart}
%       \markboth{Problems for Part \thepart}{Problems for Part \thepart}}{\global\inproblemfalse}

\let\savethefigure\thefigure
%\newenvironment{problems}{\global\c@problemnum=0\global\inproblemtrue}{\global\inproblemfalse}

%\newcommand{\problem}[1]%% 
%{\c@problempartnum=0\relax\advance\c@problemnum by 1\let\@currentlabel=\theproblem\relax\paragraph{\theproblem\hskip1em#1}}
%%{[#1]}}


%\newcounter{problempartnum}[problemnum]
%\newenvironment{problemparts}{\begin{list}{\hbox to 1pc{\bit{\alph{problempartnum}.}\hss}}{}
%\itemsep7pt}{\end{list}{\c@problempartnum=0}}
%\newcommand{\problempart}{\addtocounter{problempartnum}{1}\item}
\newenvironment{problemparts}{}{}

\newcounter{exercisenum}[section]
\newcommand{\theexercise}
{\thechapter\ifnum\c@section<1\else.\arabic{section}\fi-\arabic{exercisenum}}


\newenvironment{exercises}{\subsection*{Exercises}
\global\inexercisetrue\c@exercisenum=0\vskip7pt}{\global\inexercisefalse\vskip6pt}


\newcommand{\exercise}{\vskip-6pt\vskip1sp\advance\c@exercisenum by 1\paragraph{\theexercise}\let\@currentlabel=\theexercise\c@problempartnum=0\relax\advance\c@problemnum by 1}
%{[#1]}}
% preceding modified 2/25/89 by rlr to reset problempartnum so we can use
% problem parts inside an exercise.

\newcommand{\clrexercise}[1]{\vskip-6pt\vskip1sp\advance\c@exercisenum by 1\paragraph{\theexercise#1}\let\@currentlabel=\theexercise}
\newcommand{\exer}[1]{\ifnum#1=0\clrexercise{}\else\ifnum#1=1\clrexercise{\hspace*{1em}\verysmstar}\else\clrexercise{\hspace*{.5em}\verysmstar\verysmstar}\fi\fi}


\newcommand{\hint}{{\em Hint:\/}\ }
%\newcommand{\optional}{{\em Optional:\/}\ }

% Macros for answers and ``noanswers'' to problems and exercises.
% The \answer macro ignores its argument
%\long\def\answer#1{\setcounter{problempartnum}{0}\ignorespaces}
\long\def\answer#1{\begin{description}
\item{{\it Answer:}} #1
\end{description}}

% The \noanswer macro has no arguments
%%%\long\def\noanswer{\ignorespaces}
\long\def\noanswer#1{\answer{{\it None.}}}

% Text to be included in the answer key only

\long\def\keytext#1{}
%\newenvironment{keytext}{\csname wjnnote\expandafter\endcsname\{}{\}}
%\newenvironment{keytext}{}{}

% Macros to make captions print with small type and 'Figure xx' in bold.

%\def\fnum@figure{{\ninepoint\bf Figure \thefigure}}
%\def\fnum@table{{\bf Table \thetable}}
%\let\@mycaption\caption
%\long\def\@mycaption#1[#2]#3{% the following lines are commented out
%\addcontentsline{\csname    % since we are not making listoftables
%  ext@#1\endcsname}{#1}{\protect\numberline{\csname %or listofigures
%  the#1\endcsname}{\ignorespaces #2}}\par
%  \begingroup
%    \@parboxrestore
%    \small
%    \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par
%  \endgroup}
%\def\mycaption{\refstepcounter\@captype \@dblarg{\@mycaption\@captype}}
\let\mycaption\caption

%\newcommand{\figcaption}[1]{\caption[]{#1}}

% \psfigures determines what to do for figures:
%       0 means just leave vertical space
%       1 means put a vertical rule and the figure name
%       2 means insert the PostScript version of the figure
%       3 means put the figure name flush left or right
\newcommand{\psfigures}{0}
\newcommand{\spacefigures}{\renewcommand{\psfigures}{0}}
\newcommand{\rulefigures}{\renewcommand{\psfigures}{1}}
\newcommand{\macfigures}{\renewcommand{\psfigures}{2}}
\newcommand{\namefigures}{\renewcommand{\psfigures}{3}}

\macfigures

% When calling \figspace, make sure to leave a blank line afterward!!
% \widefigspace is for figures that are more than 28pc wide.
\newlength{\halffigspace} \newlength{\wholefigspace}
\newlength{\figruleheight} \newlength{\figgap}
\newcommand{\setfiglengths}{\ifnum\psfigures=1\setlength{\figruleheight}{\hruleheight}\setlength{\figgap}{1em}\else\setlength{\figruleheight}{0pt}\setlength{\figgap}{0em}\fi}
\newcommand{\figspace}[2]{\ifnum\psfigures=0\leavefigspace{#1}\else%
\setfiglengths%
\setlength{\wholefigspace}{#1}\setlength{\halffigspace}{.5\wholefigspace}%
\rule[-\halffigspace]{\figruleheight}{\wholefigspace}\hspace{\figgap}#2\fi}
\newlength{\widefigspacewidth}
% Make \widefigspace put the figure flush right on the text page.
\newcommand{\widefigspace}[2]{
\ifnum\psfigures=0\leavefigspace{#1}\else%
\setfiglengths%
\setlength{\widefigspacewidth}{28pc}%
\addtolength{\widefigspacewidth}{-\figruleheight}%
\setlength{\wholefigspace}{#1}\setlength{\halffigspace}{.5\wholefigspace}%
\makebox[\widefigspacewidth][r]{#2\hspace{\figgap}}\rule[-\halffigspace]{\figruleheight}{\wholefigspace}\fi}
\newcommand{\leavefigspace}[1]{\setlength{\wholefigspace}{#1}\setlength{\halffigspace}{.5\wholefigspace}\rule[-\halffigspace]{0em}{\wholefigspace}}

% Commands for including figures with psfig.
\newlength{\macfigfill}
\makeatother
%%% \input{/a/aviary/psfig/lib/psfig.tex}
%%% Changed to the following on 1/31/91 by RLR.  Other related possbily necessary
%%% changes to this file have not been made.
 \input support/psfig
\newlength{\bbx}
\newlength{\bby}
\newcommand{\macfigure}[5]{
\ifnum\psfigures=2%
\setlength{\bbx}{#2}\addtolength{\bbx}{#4}%
\setlength{\bby}{#3}\addtolength{\bby}{#5}%
\begin{flushleft}
\ifdim#4>28pc\setlength{\macfigfill}{#4}\addtolength{\macfigfill}{-28pc}\hspace*{-\macfigfill}\fi%
\mbox{\psfig{figure=/a/clr/figures/#1.ps,%
bbllx=#2,bblly=#3,bburx=\bbx,bbury=\bby}}
\end{flushleft}%
\else\ifdim#4>28pc\widefigspace{#5}{#1}\else\figspace{#5}{#1}\fi\fi}
\makeatletter

% Environment to make a figure float to a verso.


\newenvironment{versofigure}{\ifodd\count\z@ \global\@topnum\z@\fi
\begin{figure}[tp]}{\end{figure}}

\newenvironment{rectofigure}{\begin{figure}[tp]}{\end{figure}}

\newenvironment{versofigurepage}{\begin{versofigure}\vbox to\textheight\bgroup}{\vfill\egroup\end{versofigure}}
\newenvironment{rectofigurepage}{\begin{rectofigure}\vbox to\textheight\bgroup}{\vfill\egroup\end{rectofigure}}




\newcommand{\figpart}[1]{{\bf (#1)}\nolinebreak[2]\relax}
\newcommand{\figparts}[2]{{\bf (#1)--(#2)}\nolinebreak[2]\relax}

\newlength{\savearraycolsep}
%\newlength{\arrayadjust}
\newcommand{\narrowarray}[1]{\setlength{\savearraycolsep}{\arraycolsep}%
\setlength{\arraycolsep}{#1\arraycolsep}%
%\setlength{\arrayadjust}{\savearraycolsep}%
%\addtolength{\arrayadjust}{-\arraycolsep}%
%\hspace*{\arrayadjust}%
}
\newcommand{\normalarray}{\setlength{\arraycolsep}{\savearraycolsep}}
\newlength{\savetabcolsep}
%\newlength{\tabadjust}
\newcommand{\narrowtabular}[1]{\setlength{\savetabcolsep}{\tabcolsep}%
\setlength{\tabcolsep}{#1\tabcolsep}%
%\setlength{\tabadjust}{\savetabcolsep}%
%\addtolength{\tabadjust}{-\tabcolsep}%
%\hspace*{\tabadjust}
}
\newcommand{\normaltabular}{\setlength{\tabcolsep}{\savetabcolsep}}
% Old defns, fixed by THC
%\newcommand{\narrowarray}[1]{\setlength{\savearraycolsep}{\arraycolsep}\setlength{\arraycolsep}{#1\arraycolsep}}
%\newcommand{\narrowtabular}[1]{\setlength{\savetabcolsep}{\tabcolsep}\setlength{\tabcolsep}{#1\tabcolsep}}

%\def\udots{\mathinner{\mkern1mu\raise\p@\vbox{\kern7\p@\hbox{.}}\mkern2mu
%    \raise4\p@\hbox{.}\mkern2mu\raise7\p@\hbox{.}\mkern1mu}}

%\newcommand{\powertwos}[1]{{\narrowarray{0.1}#1\left.#1\begin{array}{ccc}#1&#1&#1 2\hspace*{.5em}\\[-0.2ex]#1&#1 \udots&#1\\[-.5ex]#1 2&#1&#1\end{array}#1\right\}\normalarray}}

\def\diagdots{\hbox{\hskip2pt\raise5pt\hbox{.}\hskip1pt\raise8pt\hbox{.}\hskip1pt\raise11pt\hbox{.}\hskip2pt\vrule height16pt width0pt}}

\def\powertwos#1#2{\hbox{${#12}\diagdots^{#12}\raise7pt\vbox to0pt{\vss\hbox{$\left.\vrule height12.49pt width0pt\right\}$\raise1pt\hbox{$#1#2$}}}
$}}

%% for powertwos that are used in superscript
\def\secondpowertwos#1#2{\lower3pt\hbox{${#12}\diagdots^{#12}\raise7pt\vbox to0pt{\vss\hbox{$\left.\vrule height12.49pt width0pt\right\}$\raise1pt\hbox{$#1#2$}}}
$}}


% The following is used to control copyright printing
\newif\ifdraft\draftfalse
%\newif\ifdraft\drafttrue


%%% commands for writing out bustup command file
%%% this command file uses dviselect to bust up book into chapter-sized dvi
%%% files



\newcounter{bustupctrchap}
\newcounter{bustupctrpart}

\def\makebustup{\if@filesw \newwrite\@bustupfile
  \immediate\openout\@bustupfile=\jobname.bustup
  \def\bustupbeginpart{\@bsphack\begingroup\@sanitize\@wrbustupbeginpart\@bustupfile}
  \def\bustupbeginchap{\@bsphack\begingroup\@sanitize\@wrbustupbeginchap\@bustupfile}
  \def\bustupbeginintrochap{\@bsphack\begingroup\@sanitize\@wrbustupbeginintrochap\@bustupfile}
  \def\bustupendchap{\@bsphack\begingroup\@sanitize\@wrbustupendchap\@bustupfile}
  \def\bustupendpart{\@bsphack\begingroup\@sanitize\@wrbustupendpart\@bustupfile}
  \typeout
  {Writing bustup file \jobname.bustup }\fi}

\def\@wrbustupbeginchap#1#2{
   \setcounter{bustupctrchap}{\value{page}}
   \addtocounter{bustupctrchap}{1}
   \global\edef\bustupmacchap{dviselect -i \jobname.dvi -o chap.#2.dvi \arabic{bustupctrchap}-}
   \endgroup}

\def\@wrbustupbeginintrochap#1#2{
   \setcounter{bustupctrchap}{\value{page}}
   \global\edef\bustupmacchap{dviselect -i \jobname.dvi -o chap.#2.dvi \arabic{bustupctrchap}-}
   \endgroup}

\def\@wrbustupendchap#1{\let\thepage\relax
   \xdef\@gtempa{\write#1{\bustupmacchap\thepage}}\endgroup\@gtempa
   \if@nobreak \ifvmode\nobreak\fi\fi\@esphack}

\def\@wrbustupbeginpart#1#2{
   \setcounter{bustupctrpart}{\value{page}}
   \addtocounter{bustupctrpart}{1}
   \global\edef\bustupmacpart{dviselect -i \jobname.dvi -o part.#2.dvi \arabic{bustupctrpart}-}
   \endgroup}

\def\@wrbustupendpart#1{\let\thepage\relax
   \xdef\@gtempa{\write#1{\bustupmacpart\thepage}}\endgroup\@gtempa
   \if@nobreak \ifvmode\nobreak\fi\fi\@esphack}

\def\makeindex{\if@filesw \newwrite\@indexfile
  \immediate\openout\@indexfile=\jobname.idx
  \def\index{\ifhmode\unskip\fi\@bsphack\begingroup
             \def\protect####1{\string####1\space}\@sanitize
             \@wrindex\@indexfile}\typeout
  {Writing index file \jobname.idx }\fi}

\def\label#1{\ifhmode\unskip\fi\@bsphack\if@filesw {\let\thepage\relax
   \def\protect{\noexpand\noexpand\noexpand}%
\xdef\@gtempa{\write\@auxout{\string
      \newlabel{#1}{{\@currentlabel}{\thepage}}}}}\@gtempa
   \if@nobreak \ifvmode\nobreak\fi\fi\fi\@esphack}

\def\alabel#1{\ifhmode\unskip\fi\@bsphack\if@filesw {\let\thepage\relax
   \def\protect{\noexpand\noexpand\noexpand}%
\xdef\@gtempa{\write\@auxout{\string
      \newlabel{#1}{{\@currentlabel}{\thepage}}}}}\@gtempa
   \if@nobreak \ifvmode\nobreak\fi\fi\fi\@esphack}


\def\Commnt{\noexpand\comment\begingroup} %\def\endCommnt{\endgroup}

\makeatother

% \input{hyphenation}



%------------
%\documentstyle[12pt,twoside]{article}
%\input{mac}
%\begin{document}
%\Pset{5}{March 6, 1991}{March 13, 1991}
%
%\medskip
%
%\index{Fibonacci heap/deletion from}%
%Professor Pisano has proposed the following variant of the
%\proc{Fib-Heap-Delete} procedure, claiming that it runs in $O(1)$
%amortized time when
%the node being deleted is not the node pointed to by $\id{min}[H]$.
%
%\codebox{%
%\<$\procdecl{Pisano-Delete}(H,x)$\\
%\li \If $x = \id{min}[H]$\\
%\li \Then $\proc{Fib-Heap-Extract-Min}(H)$\\
%\li \Else $y \gets p[x]$\\
%\li \>\>\If $y \neq \const{nil}$\\
%\li \>\>\Then $\proc{Cut}(H,x,y)$\\
%\li \>\>\>\>$\proc{Cascading-Cut}(H,y)$\\
%\li \>\>add $x$'s child list to the root list of $H$\\ \label{li:pisano}
%\li \>\>remove $x$ from the root list of $H$}
%
%\begin{problemparts}
%
%\problempart Give all the variables 
%of the Fibonacci heap data structure
%that will have incorrect values
%after an execution of \proc{Pisano-Delete}.
%Show how to modify \proc{Pisano-Delete} so that these variables
%get correct values.
%
%\problempart Give a good upper bound on the actual time of your modified
%\proc{Pisano-Delete} when $x \neq \id{min}[H]$.  Your bound should be
%in terms of $\id{degree}[x]$ and the number $c$ of calls to the
%\proc{Cascading-Cut} procedure.
%
%\problempart Let $H'$ be the Fibonacci heap that results from an
%execution of your modified 
%\proc{Pisano-Delete}$(H,x)$.  Assuming that node $x$ is
%not a root, bound the potential of $H'$ in terms of $\id{degree}[x]$,
%$c$, $t(H)$, and $m(H)$.
%Is the amortized time for your modified \proc{Pisano-Delete}
%asymptotically better than for \proc{Fib-Heap-Delete}, even when
%$x \neq \id{min}[H]$?
%
%\end{problemparts}
%
%\problem Do Problem 23.2-7 from the book, page 476.
%(Hint: the ``efficient'' in the problem refers to $O(V+E)$.)
%
%\problem Do Problem 23.5-3 from the book, page 494.
%
%\end{document}
