% 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} % % 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} } % % 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{\TIME}{\mathop{\rm TIME}\nolimits} \newcommand{\NTIME}{\mathop{\rm NTIME}\nolimits} \newcommand{\SPACE}{\mathop{\rm SPACE}\nolimits} \newcommand{\NSPACE}{\mathop{\rm NSPACE}\nolimits} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} %\newcommand{\implies}{\Rightarrow} % % Useful functions % \newcommand{\abs}[1]{\mathify{\left| #1 \right|}} \renewcommand{\Pr}[1]{\mathify{\mbox{Pr}\left[#1\right]}} \newcommand{\Exp}[1]{\mathify{\mbox{E}\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]{\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{\wlogg}{\em 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{\emptystring}{\epsilon} % empty string \def\P{{\sf P}} \def\NP{{\sf NP}} \def\PP{{\sf BPP}} \def\IP{{\sf IP}} \def\RP{{\sf RP}} \newcommand{\bit}{\set{\mathtt{0,1}}} \newcommand{\strings}{\bit^*} \newcommand{\DFA}{\mathify{\mathsf{DFA}}} \newcommand{\NFA}{\mathify{\mathsf{NFA}}} \newcommand{\CFL}{\mathify{\mathsf{CFL}}} \newcommand{\CFG}{\mathify{\mathsf{CFG}}} \newcommand{\PDA}{\mathify{\mathsf{PDA}}} \newcommand{\TM}{\mathify{\mathsf{TM}}} \newcommand{\LBA}{\mathify{\mathsf{LBA}}} % % problems and subproblems % \newif\ifpageperproblem \newcommand{\pageperproblem}{\pageperproblemtrue} \newenvironment{pset}{\ifpageperproblem \else \psetheader\fi}{} \newcounter{problem} \newcounter{subproblem}[problem] %\newcounter{subproblem} \renewcommand{\theproblem}{\arabic{problem}} \renewcommand{\thesubproblem}{\alph{subproblem}} \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:}\paragraph{}\noindent} \fi } {\ifpageperproblem\newpage\else\vspace{.2in}\fi} \newenvironment{subproblem} {\stepcounter{subproblem} \noindent\textbf{\thesubproblem)}} {\vspace{.1in}} \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} % 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\}} % % 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\psetnum\relax \newcommand{\psetnum}[1]{\def\psetnum{#1}} \let\psetauthor\relax \renewcommand{\author}[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}} \newcommand{\psetheader}{ \handout{\psetnum}{\textbf{\subjnum}}{\textbf{\psetauthor}} {\textbf{\subjname}}{\texttt{\psetauthoremail}} {\psetdate}{\psetcollab} {Problem Set \psetnum}} %%% Local Variables: %%% mode: latex %%% TeX-master: t %%% End: