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

% Page format commands

\setlength{\parindent}{0in}                     % Paragraph Indentation
\setlength{\parskip}{0.3\baselineskip}          % Interparagraph Spacing

\hoffset        = -1.0 in
\voffset        = -1.0 in

\paperheight    = 11.0 in
\paperwidth     =  8.5 in

\topmargin      = 0.75 in
\headheight     = \baselineskip
\headsep        = \baselineskip
\footskip       = 0.75 in
\textheight     = \paperheight
\addtolength{\textheight}{-\topmargin}
\addtolength{\textheight}{-\headheight}
\addtolength{\textheight}{-\headsep}
\addtolength{\textheight}{-\footskip}

\textwidth      = \paperwidth
\oddsidemargin  = 1.0 in
\evensidemargin = 1.0 in
\addtolength{\textwidth}{-\oddsidemargin}
\addtolength{\textwidth}{-\evensidemargin}

\linewidth      = \textwidth

\newcommand{\printlayout}{%
  \typeout{----------------------- LaTeX Page Layout Parameters}
  \typeout{\string\paperwidth\space\space\the\paperwidth}
  \typeout{\string\paperheight\space\the\paperheight}
  \typeout{\string\textwidth\space\space\the\textwidth}
  \typeout{\string\textheight\space\the\textheight}
  \typeout{\string\oddsidemargin\space\space\the\oddsidemargin}
  \typeout{\string\evensidemargin\space\the\evensidemargin}
  \typeout{\string\topmargin\space\space\the\topmargin}
  \typeout{\string\headheight\space\the\headheight}
  \typeout{\string\headsep\space\the\headsep}
  \typeout{\string\footskip\space\space\space\the\footskip}
  \typeout{\string\marginparwidth\space\the\marginparwidth}
  \typeout{\string\marginparsep\space\space\space\the\marginparsep}
  \typeout{\string\hoffset\space\the\hoffset}
  \typeout{\string\voffset\space\the\voffset}
  \typeout{(1in=72.27pt, 1cm=28.45pt)}
  \typeout{-----------------------------------------}%
}

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

\makeatletter

\RequirePackage{amsmath}
\RequirePackage{amssymb}
\RequirePackage{psfig}

\newif\iflecture
\lecturetrue
\newif\ifonly
\onlyfalse
\newif\ifslides
\slidesfalse

\newcommand{\forstudent}[1]{
\iflecture \ifonly {} \else {\scriptsize #1} \fi
\else #1
\fi
}

\newcommand{\forstudents}[1]{\forstudent{#1}}

\newcommand{\forlecture}[1]{
\iflecture #1 
\else \ifonly {} \else {\scriptsize #1} \fi
\fi
}


% David Jones suggestions:
% The problem is that the catcodes of characters inside of macro bodies
% are set when the macro definition is scanned.  So, you have to arrange
% for . after the \let to be active when the macro is defined.
%    \def\PERIOD{.\\}
%    {
%        \catcode`\.=\active
%        \gdef\breakper{%
%            \catcode`\.=\active
%            \let.\PERIOD
%        }
%    }


\let\period=.
\def\.{\period}
\catcode`\.=\active
\def.{\iflecture\ifmmode\period\else\period\\\fi\else\period\fi}
\catcode`\.=12
\newenvironment{outline}{\catcode`\.=\active}{}
\newenvironment{nooutline}{\catcode`\.=12}{}
\def\protectperiod#1{\begingroup\catcode`\.=12 #1\endgroup}
\def\ie{\protectperiod{\it i.e.}}
\def\eg{\protectperiod{\it e.g.}}
\def\Eg{\protectperiod{\it E.g.}}

\newcommand{\makeslides}{
\slidestrue
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{0.5in}
\setlength{\textheight}{7.5in}
\setlength{\textwidth}{10in}
\def\section{}
\def\subsection{}
\def\subsubsection{}
\output={\setbox8=\box255}
}


\newenvironment{overhead}{
\begin{overhead*}{\small}
}{
\end{overhead*}
}

% Usage: \begin{overhead*}[lecture notes header]{overhead header}
\newenvironment{overhead*}[2][]{
\ifslides
\newpage
\normalsize
\output={}
\begin{slide}
#2
\else
#1
\fi
}{
\ifslides
\end{slide}
\newpage
\output={\setbox8=\box255}
\fi
}

\newenvironment{structproof}{
\begin{tabbing}
\ifslides
XXX\=XXX\=XXX\=XXXX\=XXXXXXXXXXXXXXXX\=    \kill
\else
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\fi
}{
\end{tabbing}
}

\newenvironment{proofoverhead}{
\begin{overhead}
\begin{structproof}
}{
\end{structproof}
\end{overhead}
}



\def\onlylecture{
\lecturetrue \onlytrue
}

\def\mainlylecture{
\lecturetrue \onlyfalse
}

\def\onlystudents{
\lecturefalse \onlytrue
}

\def\mainlystudents{
\lecturefalse \onlyfalse
}

\def\.{.\iflecture\\\fi}
\def\?{?\iflecture\\\fi}
\def\!{!\iflecture\\\fi}
\def\newl{\iflecture\\\fi}

\newcommand{\reading}[1]{{\bf Reading:} #1\\ \\}

%\input{handout-numbers}
%%  Formatting changes made at ARM's request. -- dmj, 2/21/96

\parindent\z@

\parskip\medskipamount

\def\@listI{\leftmargin\leftmargini \parsep 5pt plus 2.5pt minus 1pt%
\topsep 10pt plus 4pt minus 6pt%
\itemsep \z@}

\let\@listi\@listI
\@listi

%%%%%From Nancy's book directory:  This spaces the symbols within a
%%%%%word nicely, in math mode. 

\newcommand{\ms}[1]{%
        \relax\ifmmode
                \mathord{\mathcode`\-="702D\it #1\mathcode`\-="2200}%
        \else
                $\mathord{\mathcode`\-="702D\it #1\mathcode`\-="2200}$%
        \fi
}

\newcommand{\remove}[1]{}

%%%%%%%%found in /pub/ftp/pub/classes/6.042/handouts/H07-aeqn.tex

\newcommand{\fortext}[1]{\relax\ifmmode{#1}\else\mbox{$#1$}\fi}
\def\z3{\fortext{\integers_{3}}}
\def\ltecom{\fortext{\sqsubseteq}}
\newcommand{\lcm}{\mathop{\rm lcm}\nolimits}
\newcommand{\subst}[3]{#1[#2 := #3]}
\let\union\cup

\newcommand{\aeval}[2]{{\it val}(#1,#2)}
\newcommand{\mean}[1]{\llbracket#1\rrbracket}
\newcommand{\provable}{\fortext{\vdash}}
\newcommand{\notprovable}{\fortext{\not\vdash}}
\newcommand{\can}[1]{\mbox{canon}(#1)}

\newcommand{\notmodels}{\fortext{\not\models}}

%%%%%found in /pub/ftp/pub/classes/6.042/handouts/macros-course.tex



%%  Modified \newtheorem to provide *-variants. -- dmj, 5/20/96

\def\@xnthm#1#2[#3]{%
    \expandafter\@ifdefinable\csname #1\endcsname
        {\@definecounter{#1}%
         \@addtoreset{#1}{#3}%
         \expandafter\xdef\csname the#1\endcsname{%
            \expandafter\noexpand\csname the#3\endcsname
            \@thmcountersep \@thmcounter{#1}%
         }%
         \global\@namedef{#1}{\@thm{#1}{#2}}%
         \global\@namedef{end#1}{\@endtheorem}%
         \global\@namedef{#1*}{\@thm*{#1}{#2}}%
         \global\@namedef{end#1*}{\@endtheorem}%
        }%
}
 
\def\@ynthm#1#2{%
    \expandafter\@ifdefinable\csname #1\endcsname
        {\@definecounter{#1}%
         \expandafter\xdef\csname the#1\endcsname{%
            \@thmcounter{#1}%
         }%
         \global\@namedef{#1}{\@thm{#1}{#2}}%
         \global\@namedef{end#1}{\@endtheorem}%
         \global\@namedef{#1*}{\@thm*{#1}{#2}}%
         \global\@namedef{end#1*}{\@endtheorem}%
        }
}

%% RmS 92/01/10: check for existence of theorem environment #2
\def\@othm#1[#2]#3{%
    \@ifundefined{c@#2}
        {\@latexerr{No theorem environment `#2' defined}\@eha}%
        {%
            \expandafter\@ifdefinable\csname #1\endcsname{%
                \global\@namedef{the#1}{\@nameuse{the#2}}%
                \global\@namedef{#1}{\@thm{#2}{#3}}%
                \global\@namedef{end#1}{\@endtheorem}%
                \global\@namedef{#1*}{\@thm*{#2}{#3}}%
                \global\@namedef{end#1*}{\@endtheorem}%
            }%
        }%
}

\def\@thm{\@ifstar{\@tempswafalse\x@thm}{\@tempswatrue\x@thm}}
 
\def\x@thm#1#2{%
    \if@tempswa
        \refstepcounter{#1}%
    \fi
    \@ifnextchar[{\@ythm{#1}{#2}}{\@xthm{#1}{#2}}%
}

%% Removed \it so theorems will be in regular text. -- dmj, 2/21/96

\def\@begintheorem#1#2{\trivlist \item[\hskip \labelsep{\bf #1%
    \if@tempswa\ #2\fi}]}

\def\@opargbegintheorem#1#2#3{\trivlist
      \item[\hskip \labelsep{\bf #1\if@tempswa\ #2\fi\ (#3)}]}

\makeatother


% I'd suggest we mark changes we've made in the macros for each other
% up here. BDT 1/28/94

% I changed the \choose macro (which takes two arguments) to 
% \Choose. This way \choose still acts like \over. BDT 1/28/94

%%% oral, written, and no prefix commands added to ``problems''
%%% environment 1/94. BDT
%%% \pnumset sets the problem counter. added 2/2/94 BDT

%%% added definition of \remove for commenting large sections
%%% changed for spring 96 term 1/31/96 JK

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Cross-references for handout numbers.
\input{lecture-numbers}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%        SPRING 96:
\newcommand{\coursenumber}{6.042J/18.062J}
\newcommand{\coursetitle}{Mathematics for Computer Science}
\newcommand{\courseprofessors}{Professors David Karger and Nancy Lynch}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

%       Usage: \htitle{lecturenumber}{title}{dateout}
\newcommand{\htitle}[3]{\noindent\vspace*{-\toppush}\newline\parbox{6.5in}
{Massachusetts Institute of Technology \hfill Lecture #1 \newline
\coursenumber : \coursetitle \hfill #3 \newline
\courseprofessors\hfill\vspace*{-.5ex} \newline
\mbox{}\hrulefill\mbox{}}\vspace*{1ex}\mbox{}\newline
\bigskip
\begin{center}{\Large\bf #2}\end{center}
\bigskip}

%       Usage: \lecture{refname}{title}{dateout}
\newcommand{\lecture}[3]{
\ifslides \else
\thispagestyle{empty}
\markboth{Lecture \protect\ref{#1}: #2}{Lecture \protect\ref{#1}: #2}
\pagestyle{myheadings}\htitle{\protect\ref{#1}}{#2}{#3}
\fi
}

\newcommand{\htitlewithouttitle}[2]{\noindent\vspace*{-\toppush}\newline\parbox{6.5in}{\coursenumber : \coursetitle
\hfill Massachusetts Institute of Technology\newline
Lecture #1\hfill#2\vspace*{-.5ex}\newline
\mbox{}\hrulefill\mbox{}}\vspace*{1ex}\mbox{}\newline}

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

% Create the header for problem sets and solutions.
% Usage: \Pset{<problem-set-number>}{<out-date>}{<due-date>}
%        \Psol{<problem-set-number>}{<out-date>}
%


\newcommand{\examtitle}[2]{\noindent\vspace*{-\toppush}\newline\parbox{6.5in}
{Massachusetts Institute of Technology
\hfill #1\newline
\coursenumber : \coursetitle\hfill#2\newline
\courseprofessors\hfill\vspace*{-.5ex}
\newline
\mbox{}\hrulefill\mbox{}}\vspace*{1ex}\mbox{}\newline
\begin{center}{\Large\bf #1}\end{center}}

\newcommand{\points}[1]{\hspace{3pt}[#1 points]\hspace{8pt}}

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

\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

%\renewcommand{\cases}[1]{\left\{ \begin{array}{ll}#1\end{array}\right.}
\newcommand{\cif}[1]{\mbox{if $#1$}}
\newcommand{\cwhen}[1]{\mbox{when $#1$}}

%%%     oral, written, and no prefix commands added late 1/94 BDT
%%%     \pnumset sets the problem counter. added 2/2/94 BDT

\newcommand{\pnumset}[1]
  {\setcounter{problemnum}{#1}\addtocounter{problemnum}{-1}}
\newcounter{problemnum}

%% \theproblem changed at ARM's request. -- dmj, 2/21/96

%\newcommand{\theproblem}{Problem \oralwrit\theproblemsetnum-\arabic{problemnum}}

\newcommand{\theproblem}{Problem~\arabic{problemnum}}

\makeatletter

\newcommand{\noprefix}{}
\newcommand{\oralprefix}{O}
\newcommand{\writprefix}{W}
\newenvironment{problems}{
        \begin{list}{{\bf \theproblem. \hspace*{0.5em}}}
        {\setlength{\leftmargin}{0em}
         \setlength{\rightmargin}{0em}
         \setlength{\labelwidth}{0em}
         \setlength{\itemsep}{.3in}
%        \setlength{\labelsep}{0em}
%%  
%%  Added to make problem numbering consecutive, per ARM's request. --
%%  dmj, 2/21/96
%%  
         \count@=\c@problemnum
         \usecounter{problemnum}%
         \setcounter{problemnum}{\count@}%
        }}{\end{list}}

\newcommand{\problem}{\let\oralwrit=\noprefix
       \item \let\@currentlabel=\theproblem}
\newcommand{\oproblem}{\let\oralwrit=\oralprefix
       \item \let\@currentlabel=\theproblem}
\newcommand{\wproblem}{\let\oralwrit=\writprefix
       \item \let\@currentlabel=\theproblem}
\makeatother

\newcounter{problempartnum}[problemnum]
\newenvironment{problemparts}{
        \begin{list}{{\bf (\alph{problempartnum})}}
        {\setlength{\leftmargin}{2.5em}
         \setlength{\rightmargin}{2.5em}
         \setlength{\labelsep}{0.5em}}}{\end{list}}
\newenvironment{testproblemparts}{
        \begin{list}{{\bf (\alph{problempartnum})}}
        {\setlength{\leftmargin}{2.5em}
         \setlength{\rightmargin}{2.5em}
         \setlength{\itemsep}{2in}      
         \setlength{\labelsep}{0.5em}}}{\end{list}}
\newcommand{\problempart}{\addtocounter{problempartnum}{1}\item}
\newcommand{\bparts}{\begin{problemparts}}
\newcommand{\eparts}{\end{problemparts}}
\newcommand{\ppart}{\problempart}

\newcounter{exercisenum}
\newcommand{\theexercise}{Exercise \theproblemsetnum-\arabic{exercisenum}}
\newenvironment{exercises}{
        \begin{list}{{\bf \theexercise. \hspace*{0.5em}}}
        {\setlength{\leftmargin}{0em}
         \setlength{\rightmargin}{0em}
         \setlength{\labelwidth}{0em}
         \setlength{\labelsep}{0em}
        \usecounter{exercisenum}}}{\end{list}}
\makeatletter
\newcommand{\exercise}{\item \let\@currentlabel=\theexercise}
\makeatother

\newcounter{exercisepartnum}[exercisenum]
%\newcommand{\problem}[1]{\medskip\mbox{}\newline\noindent{\bf Problem #1.}\hspace*{1em}}
%\newcommand{\exercise}[1]{\medskip\mbox{}\newline\noindent{\bf Exercise #1.}\hspace*{1em}}

\newenvironment{exerciseparts}{
        \begin{list}{{\bf (\alph{exercisepartnum})}}
        {\setlength{\leftmargin}{2.5em}
         \setlength{\rightmargin}{2.5em}
         \setlength{\labelsep}{0.5em}}}{\end{list}}
\newcommand{\exercisepart}{\addtocounter{exercisepartnum}{1}\item}


% 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}}

%% \let\@mycaption\caption

%\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
\let\mycaption\caption
%\newcommand{\figcaption}[1]{\mycaption[]{#1}}

\newcounter{totalcaptions}
\newcounter{totalart}

\newcommand{\figcaption}[1]{\addtocounter{totalcaptions}{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}}

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


\macfigures     % STATE

% 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 macpsfig.
% To use these commands, documentstyle ``macpsfig'' must be specified.
\newlength{\macfigfill}
\makeatother
\newlength{\bbx}
\newlength{\bby}
\newcommand{\macfigure}[5]{\addtocounter{totalart}{1}
\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=./#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

\newlength{\savearraycolsep}
\newcommand{\narrowarray}[1]{\setlength{\savearraycolsep}{\arraycolsep}\setlength{\arraycolsep}{#1\arraycolsep}}
\newcommand{\normalarray}{\setlength{\arraycolsep}{\savearraycolsep}}

\newcommand{\hint}{{\em Hint:\ }}


% macros from clrmac.tex inserted by mb

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

% Macros from /th/u/clr/mac.tex

\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{\paren}[1]{\left( #1 \right)}
\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}
\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{\Ex}{\mathop{\rm Ex}}

%%%I like the old choose! BDT 1/28/94
%\renewcommand{\choose}[2]{{{#1}\atopwithdelims(){#2}}}
\newcommand{\Choose}[2]{{{#1}\atopwithdelims(){#2}}}

\def\pmod#1{\allowbreak\mkern12mu({\rm mod}\,\,#1)}
\newcommand{\matx}[2]{\left(\begin{array}{*{#1}{c}}#2\end{array}\right)}
\newcommand{\Adj}{\mathop{\rm Adj}\nolimits}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{xample}[theorem]{Example}
\newtheorem{defin}[theorem]{Definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{fact}{Fact}
\newtheorem{falsethm}{False Theorem}
\newtheorem{axiom}{Axiom}
\newtheorem{rul}[theorem]{Rule}
\newtheorem{falseclm}[theorem]{False Claim}

\newenvironment{example}{\begin{xample}\rm}{\end{xample}}
%               \newcommand{\proof}{
\newenvironment{proof}{\par{\noindent\em Proof.}\hspace{1em}\setlength{\parindent}{3ex}}{\qed}
\newenvironment{remark}{\par{\noindent\bf Remark.}\hspace{1em}\setlength{\parindent}{3ex}}{\qed}
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
%\newcommand{\qedbox}{\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newcommand{\qedbox}{\rule{2mm}{2mm}}
\newcommand{\qed}{\nopagebreak\mbox{}\hfill\qedbox\smallskip}
\newcommand{\eqnref}[1]{(\protect\ref{#1})}
\newcommand{\thm}{\begin{theorem}}
\newcommand{\ethm}{\end{theorem}}
\newcommand{\lem}{\begin{lemma}}
\newcommand{\elem}{\end{lemma}}
\newcommand{\pf}{\begin{proof}}
\newcommand{\epf}{\end{proof}}

\newcommand{\twodots}{\mathinner{\ldotp\ldotp}}

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

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

%\newcommand{\ckt}[1]{\ifmmode\mathord{\mathcode`-="702D\sc #1\mathcode`\-="2200}\else$\mathord{\mathcode`-="702D\sc #1\mathcode`\-="2200}$\fi}
\newcommand{\ckt}[1]{\ifmmode \sc #1\else$\sc #1$\fi}
\newcommand{\id}[1]{\mbox{\it #1}}
\newcommand{\proc}[1]{%
\ifmmode\mathord{\mathcode`-="702D\sc#1\mathcode`\-="2200}\else{\sc#1}\fi}
\newcommand{\procdecl}[1]{\proc{#1}\vrule width0pt height0pt depth 7pt \relax}
\newcommand{\func}[1]{\ifmmode\mathop{\mathcode`-="702D\rm #1\mathcode`\-="2200}\nolimits\else$\mathop{\mathcode`-="702D\rm #1\mathcode`\-="2200}\nolimits$\fi}

\newif\ifcodeinbox

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 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}

\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}\'}

\newcommand{\marnote}[1]{\marginpar{\raggedright{\footnotesize #1}}\ignorespaces}

\newcommand{\reals}{{\mathbb R}}
\newcommand{\ints}{{\mathbb Z}}
\newcommand{\integers}{{\mathbb Z}}
\newcommand{\naturals}{{\mathbb N}}
\newcommand{\nat}{\naturals}
\newcommand{\nats}{\naturals}
\newcommand{\rationals}{{\mathbb Q}}
\newcommand{\complex}{{\mathbb C}}
\newcommand{\complexes}{{\mathbb C}}
\newcommand{\given}{\mid}

\newcommand{\w}{\omega}                 %% for fft chapter

%\newcommand{\implies}{\Rightarrow}     %% already defined in amstex
%\newcommand{\remove}[1]{}
%\newcommand{\divides}{\mid}
%\newcommand{\mod}[1]{(\mbox{mod } #1)}

\newenvironment{closeitemize}{\begin{list}%
{$\bullet$}%
{\setlength{\itemsep}{-0.2\baselineskip}%
\setlength{\topsep}{0.2\baselineskip}}}%
{\end{list}}


\long\gdef\boxit#1{\dimen200 = \hsize \advance\dimen200 by -7pt
\begingroup\vbox{\hrule \hbox to \hsize{\vrule\kern3pt
      \vbox{\hsize \dimen200 \kern3pt#1\kern3pt}\hfil \kern3pt\vrule}\hrule}\endgroup}
 
\newlength{\myfigwidth}
\setlength{\myfigwidth}{\columnwidth}
\addtolength{\myfigwidth}{-2ex}  %made this wider -- CS

\newcommand{\boxtext}[1]{\setlength{\myfigwidth}{\columnwidth}\addtolength{\myfigwidth}{-2ex}\boxit{\vspace*{.1ex}\begin{minipage}{\myfigwidth}#1\end{minipage}\\[.1ex]}}

%% Code imported from 6044.sty

\makeatletter

\newtoks\old@everyhbox

\def\Code{%
    \leavevmode
    \old@everyhbox=\expandafter{\the\everyhbox}%
    \everyhbox=\expandafter{%
        \the\everyhbox
        \tt\frenchspacing
        \catcode`\#=12
        \global\everyhbox=\expandafter{\the\old@everyhbox}%
    }%
    \hbox
}

\let\rulesto\longrightarrow

\newcommand{\proves}{%
    \@ifnextchar [{\@proves}{\@proves[]}%
}

\newcommand{\@proves}[1]{% provability (cf. \models)
    \if!#1!
        \vdash
    \else
        \mathrel{\mathop{\vdash}\limits_{#1}}%
    \fi
}

\makeatother


\endinput


% Local Variables: 
% mode: latex
% TeX-master: t
% End: