% 6046preamble.tex
%% this should be included with a command like
%% \input{6046preamble.tex}

\usepackage{amssymb,amsfonts,amsmath,amsthm,mathrsfs}
\usepackage{graphicx}
\usepackage{nicefrac}
\usepackage{listings}
\usepackage{clrscode}
\usepackage{url}

% 
% Set lengths
%

\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

%
% mathify-- ensure argument is in math mode
%

\newcommand{\mathify}[1]{\ifmmode{#1}\else\mbox{$#1$}\fi}


%
% Impressive box to go at the top of the first page
%


\newcommand{\handout}[8]{
  \renewcommand{\thepage}{#1-\arabic{page}}
  \noindent
  \begin{center}
      \vbox{
        \hbox to 5.78in { {\bf #2} {\bf \hfill #3} }
        \vspace{2mm}
        \hbox to 5.78in { #4 \hfill #5 }
        \vspace{2mm}
        \hbox to 5.78in { #6 \hfill #7 }
        \vspace{3mm}
        \rule[3mm]{5in}{.5pt}
%        \vspace{1mm}
        \hbox to 5.78in { {\Large \hfill #8  \hfill} }
      }

  \end{center}
  \vspace*{4mm}
}
  

% Set typesetting
% Adds braces and optionally accepts a ``pipe'' representing
% set-builder notation.  ie $\set{1,2,3}$ or $\set{A | A=B+2}$
\def\set#1{%
  \def\setInside\setStart##1|##2\setEnd{%
    \def\tempa{}\def\tempb{##2}
    \ifx\tempa\tempb
    ##1
    \else
    \def\stripPipe####1|{####1}
    ##1 \mid \stripPipe##2
    \fi}
  \left\{\setInside\setStart#1|\setEnd\right\}}


%
% Useful symbols
%

%\newcommand{\qed}{\rule{7pt}{7pt}}
\newcommand{\ihat}{\hat{\imath}}
\newcommand{\jhat}{\hat{\jmath}}
\newcommand{\Nat}{\bf N}                               % natural numbers
\newcommand{\Int}{\mathbf{Z}}                             % integers
\newcommand{\Bool}{\it Bool}                   % booleans
\newcommand{\true}{\tt t}
\newcommand{\false}{\tt f}
\newcommand{\I}{\cal I}                                % interpretations
\newcommand{\M}{\cal M}                         % meaning functions
\newcommand{\A}{\cal A}                         % arithmetic interpretation
\newcommand{\B}{\cal B}                         % binary word interpretation
\newcommand{\union}{\cup}
\newcommand{\intersect}{\cap}
%\newcommand{\implies}{\Rightarrow}

% 
% Useful functions
%

\newcommand{\abs}[1]{\mathify{\left| #1 \right|}}
\renewcommand{\Pr}[1]{\mathify{\mathbf{Pr}\left[#1\right]}}
\newcommand{\Exp}[1]{\mathify{\mathbf{E}\left[#1\right]}}
\newcommand{\Var}[1]{\mathify{\mathbf{Var}\left[#1\right]}}
\newcommand{\Cov}[1]{\mathify{\mathbf{Cov}\left[#1\right]}}
%\newcommand{\set}[1]{\mathify{\left\{ #1 \right\}}}
\newcommand{\cset}[2]{\set{#1\ :\ #2}}  % a conditional notation to define sets
\newcommand{\lset}[2]{\mathify{\set{#1,\ldots,#2}}} % set {from,...,to}
\newcommand{\pair}[1]{\mathify{\left\langle#1\right\rangle}}
\newcommand{\suchthat}{\vert}
\newcommand{\st}{\suchthat}
\newcommand{\der}[2]{\frac{d #1}{d #2}}
\newcommand{\partialder}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\ceil}[1]{\mathify{\left\lceil #1 \right\rceil}}
\newcommand{\floor}[1]{\mathify{\left\lfloor #1 \right\rfloor}}

% 
% For pseudo-code
%

\newcommand{\FOR}{{\bf for}}
\newcommand{\TO}{{\bf to}}
\newcommand{\DO}{{\bf do}}
\newcommand{\WHILE}{{\bf while}}
\newcommand{\AND}{{\bf and}}
\newcommand{\IF}{{\bf if}}
\newcommand{\THEN}{{\bf then}}
\newcommand{\ELSE}{{\bf else}}



%
% Useful environments-- theorem-like
%


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}


%
% abbreviations
%
\newcommand{\ie}{\em i.e.}
\newcommand{\etc}{\em etc.}
\newcommand{\eg}{\em e.g.}
\newcommand{\WLOG}{\textit{w.l.o.g.}}
\newcommand{\cf}{\em cf.}
\newcommand{\viz}{\em viz.}

\newcommand{\eqdef}{\stackrel{\rm def}{=}}       % ``equals by definition''
\newcommand{\hint}{{\em Hint}:\ }              % for in-line hints
\newcommand{\note}{{\em Note}:\ }              % for in-line notes
\newcommand{\remark}{{\em Remark}\/:\ }              % for in-line remarks  



%
% 6.045/theocomp specific symbols
%

\newcommand{\bigO}[1]{\ensuremath{O\left(#1\right)}}
\newcommand{\bigOt}[1]{\ensuremath{\tilde{O}\left(#1\right)}}
\newcommand{\littleO}[1]{\ensuremath{o\left(#1\right)}}
\newcommand{\bigTheta}[1]{\ensuremath{\Theta\left(#1\right)}}
\newcommand{\bigOmega}[1]{\ensuremath{\Omega\left(#1\right)}}
\newcommand{\littleOmega}[1]{\ensuremath{\omega\left(#1\right)}}
\newcommand{\emptystring}{\epsilon}              % empty string
\newcommand{\bit}{\set{\mathtt{0},\mathtt{1}}}
\newcommand{\strings}{\bit^*}
\newcommand{\kstrings}{\bit^k}
\newcommand{\DFA}{\mathify{\mathsf{DFA}}}
\newcommand{\NFA}{\mathify{\mathsf{NFA}}}
\newcommand{\REX}{\mathify{\mathsf{REX}}}
\newcommand{\CFL}{\mathify{\mathsf{CFL}}}
\newcommand{\CFG}{\mathify{\mathsf{CFG}}}
\newcommand{\PDA}{\mathify{\mathsf{PDA}}}
\newcommand{\TM}{\mathify{\mathsf{TM}}}
\newcommand{\NTM}{\mathify{\mathsf{NTM}}}
\newcommand{\LBA}{\mathify{\mathsf{LBA}}}
\renewcommand{\P}{\mathify{\mathsf{P}}}
\newcommand{\NP}{\mathify{\mathsf{NP}}}
\newcommand{\BPP}{\mathify{\mathsf{BPP}}}
\newcommand{\PPT}{\mathify{\mathsf{PPT}}}
\newcommand{\IP}{\mathify{\mathsf{IP}}}
\newcommand{\RP}{\mathify{\mathsf{RP}}}
\newcommand{\NC}{\mathify{\mathsf{NC}}}
\newcommand{\RNC}{\mathify{\mathsf{RNC}}}
\renewcommand{\L}{\mathify{\mathsf{L}}}
\newcommand{\NL}{\mathify{\mathsf{NL}}}
\newcommand{\coNL}{\mathify{\mathsf{coNL}}}
\newcommand{\TIME}[1]{\ensuremath{\mathsf{TIME}\left(#1\right)}}
\newcommand{\NTIME}[1]{\ensuremath{\mathsf{NTIME}\left(#1\right)}}
\newcommand{\SPACE}[1]{\ensuremath{\mathsf{SPACE}\left(#1\right)}}
\newcommand{\NSPACE}[1]{\ensuremath{\mathsf{NSPACE}\left(#1\right)}}
\newcommand{\EXPTIME}{\mathify{\mathsf{EXPTIME}}}
\newcommand{\EXPSPACE}{\mathify{\mathsf{EXPSPACE}}}
\newcommand{\NEXPTIME}{\mathify{\mathsf{NEXPTIME}}}
\newcommand{\NEXPSPACE}{\mathify{\mathsf{NEXPSPACE}}}
\newcommand{\PSPACE}{\mathify{\mathsf{PSPACE}}}
\newcommand{\coNP}{\mathify{\mathsf{coNP}}}

%
% problems and subproblems
%

\newif\ifpageperproblem
\newcommand{\pageperproblem}{\pageperproblemtrue}
\newenvironment{pset}{\ifpageperproblem \else \psetheader\fi}{}


\newcounter{problem}
\newcounter{subproblem}[problem]
\newcounter{subsubproblem}[subproblem]
%\newcounter{subproblem}
\renewcommand{\theproblem}{\arabic{problem}}
\renewcommand{\thesubproblem}{\alph{subproblem}}
\renewcommand{\thesubsubproblem}{\roman{subsubproblem}}
\newenvironment{problem}[1][\theproblem]{\stepcounter{problem}
  \ifpageperproblem{
    \handout{\psetnum-#1}{\textbf{\subjnum}}{\textbf{\psetauthor}}
    {\textbf{\subjname}}{\texttt{\psetauthoremail}}
    {\psetdate}{\psetcollab}
    {Problem \psetnum-#1}}
  \else
    {\noindent\textbf{Problem #1:}}\vspace{.5em}\par\noindent
  \fi
}
{\ifpageperproblem\newpage\else\vspace{2em}\fi}
\newenvironment{subproblem} {\stepcounter{subproblem} 
   \noindent\textbf{\thesubproblem)}} {\vspace{.1in}}
\newenvironment{subsubproblem} {\stepcounter{subsubproblem} 
   \noindent\textit{\thesubsubproblem)}} {\vspace{.05in}}
\newenvironment{solution} {\textbf{Solution
    \theproblem}:} {\vspace{.1in}}

% 
% machines
%
\newcommand{\rep}[1]{\left\langle #1 \right\rangle}

%
% Turing machine description environment
%
\newcounter{tmdepth}
\newcounter{tmi}\newcounter{tmii}\newcounter{tmiii}\newcounter{tmiv}
\newsavebox\tmbox
\newenvironment{turing}[2]%
{\sbox\tmbox{#1 = ``}
 \usebox\tmbox
 \stepcounter{tmdepth}
  #2
  \begin{list}{\textbf{\arabic{tm\roman{tmdepth}}.}}
    {\usecounter{tm\roman{tmdepth}}
      \setlength{\topsep}{-1em}
      \setlength{\itemsep}{-\parsep}
      \addtolength{\leftmargin}{\wd\tmbox}
%      \addtolength{\leftmargin}{1em}
    }}%
{''\end{list}\addtocounter{tmdepth}{-1}
\edef\tempa{0}\edef\tempb{\arabic{tmdepth}}
\ifx\tempa\tempb\vspace{1em}\fi}


%
% Set/domain theory macros
%
\newcommand{\bottom}{\ensuremath{\perp}}
\newcommand{\lub}{\sqcup}
\newcommand{\biglub}{\bigsqcup}
\newcommand{\dom}[1]{\ensuremath{\text{#1}}}
\newcommand{\cross}{\times}
\newcommand{\weaker}{\sqsubseteq}




% 
% Languages for listings
%
\lstdefinelanguage[MIT]{Scheme}{%
  morekeywords={%
    access,and,begin,case,cond,cons-stream,declare,default-object?,define,%
    define-integrable,define-structure,define-syntax,delay,do,%
    er-macro-transformer,fluid-let,if,lambda,let,let*,let*-syntax,let-syntax,%
    letrec,letrec-syntax,local-declare,named-lambda,%
    non-hygienic-macro-transformer,or,quasiquote,quote,rsc-macro-transformer,%
    sc-macro-transformer,set!,syntax-rules,the-environment},%
  morekeywords={[2]\#t,\#f,nil},%
  keywordstyle={[2]\textit},%
  alsoletter=-!*\#+,%
  sensitive=true,%
  morecomment=[l]{;},%
  morecomment=[s]{\#|}{|\#},%
  morestring=[d]{"}%
}
\lstset{defaultdialect=[MIT]Scheme}


\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\J}{\mathbb{J}}
\newcommand{\riemann}{\mathscr{R}}

\let\psetnumvar\relax
\newcommand{\psetnum}[1]{\def\psetnumvar{#1}}
\let\psetauthor\relax
\let\oldauthor\author
\renewcommand{\author}[1]{\oldauthor{#1}\def\psetauthor{#1}}
\let\psetauthoremail\relax
\newcommand{\authoremail}[1]{\def\psetauthoremail{#1}}
\let\psetdate\relax
\renewcommand{\date}[1]{\def\psetdate{#1}}
\let\psetcollab\relax
\newcommand{\collab}[1]{\def\psetcollab{#1}}
\def\psetheadertitlevar{Problem Set}
\newcommand{\psetheadertitle}[1]{\def\psetheadertitlevar{#1}}

\newcommand{\psetheader}{
  \handout{\psetnum}{\textbf{\subjnum}}{\textbf{\psetauthor}}
  {\textbf{\subjname}}{\texttt{\psetauthoremail}}
  {\psetdate}{\psetcollab}
  {\psetheadertitlevar{ }\psetnumvar}}

\makeatletter
% Tuple typesetting
% Adds triangle brackets and spaces commas.  ie $\tup{1,2,3}$
% Arguments can be enclosed in braces or angle brackets
\def\tup{%
  \def\tupInside\tupStart##1,##2\tupEnd{%
    ##1
    \def\tempa{}\def\tempb{##2}
    \ifx\tempa\tempb\else
    ,\;\tupInside\tupStart##2\tupEnd
    \fi}
  \def\tupBraces##1{\left\langle\tupInside\tupStart##1,\tupEnd\right\rangle}
  \def\tupBrackets<##1>{\tupBraces{##1}}
  \@ifnextchar<\tupBrackets\tupBraces}
\makeatother

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