(original) (raw)

%% preamble.tex %% this should be included with a command like %% \input{preamble.tex} \setlength{\evensidemargin}{.25in} \setlength{\textwidth}{6in} \setlength{\topmargin}{-0.4in} \setlength{\textheight}{8.5in} \newcommand{\handout}[5]{ \renewcommand{\thepage}{#1-\arabic{page}} \noindent \begin{center} \framebox{ \vbox{ \hbox to 5.78in {{\sf CS 183, SPRING 2025} \hfill \sf #2 } \vspace{4mm} \hbox to 5.78in { {\Large \hfill #5 \hfill} } \vspace{2mm} \hbox to 5.78in { {\em #3 \hfill #4} } } } \end{center} \vspace*{4mm} } \newcommand{\lecture}[4]{\handout{#1}{$\copyright$ #2}{Lecture date: #3}{Scribe: #4}{Lecture #1}} \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} \newcommand{\qed}{\rule{7pt}{7pt}} \newcommand{\dis}{\mathop{\mbox{\rm d}}\nolimits} \newcommand{\per}{\mathop{\mbox{\rm per}}\nolimits} \newcommand{\area}{\mathop{\mbox{\rm area}}\nolimits} \newcommand{\cw}{\mathop{\rm cw}\nolimits} \newcommand{\ccw}{\mathop{\rm ccw}\nolimits} \newcommand{\DIST}{\mathop{\mbox{\rm DIST}}\nolimits} \newcommand{\OP}{\mathop{\mbox{\it OP}}\nolimits} \newcommand{\OPprime}{\mathop{\mbox{\it OP}^{\,\prime}}\nolimits} \newcommand{\ihat}{\hat{\imath}} \newcommand{\jhat}{\hat{\jmath}} \newcommand{\abs}[1]{\mathify{\left| #1 \right|}} \newenvironment{proof}{\noindent{\bf Proof}\hspace*{1em}}{\qed\bigskip} \newenvironment{proof-sketch}{\noindent{\bf Sketch of Proof}\hspace*{1em}}{\qed\bigskip} \newenvironment{proof-idea}{\noindent{\bf Proof Idea}\hspace*{1em}}{\qed\bigskip} \newenvironment{proof-of-lemma}[1]{\noindent{\bf Proof of Lemma #1}\hspace*{1em}}{\qed\bigskip} \newenvironment{proof-attempt}{\noindent{\bf Proof Attempt}\hspace*{1em}}{\qed\bigskip} \newenvironment{proofof}[1]{\noindent{\bf Proof} of #1:\hspace*{1em}}{\qed\bigskip} \newenvironment{remark}{\noindent{\bf Remark}\hspace*{1em}}{\bigskip} % \makeatletter % \@addtoreset{figure}{section} % \@addtoreset{table}{section} % \@addtoreset{equation}{section} % \makeatother \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}} % \renewcommand{\thefigure}{\thesection.\arabic{figure}} % \renewcommand{\thetable}{\thesection.\arabic{table}} % \renewcommand{\theequation}{\thesection.\arabic{equation}} \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{\tabcaption}[1]{\mycaption[]{#1}} \newcommand{\head}[1]{\chapter[Lecture \##1]{}} \newcommand{\mathify}[1]{\ifmmode{#1}\else\mbox{$#1$}\fi} \renewcommand{\Pr}[1]{\mathify{\mbox{Pr}\left[#1\right]}} \newcommand{\Exp}[1]{\mathify{\mbox{Exp}\left[#1\right]}} \newcommand{\bigO}O \newcommand{\set}[1]{\mathify{\left\{ #1 \right\}}} \def\half{\frac{1}{2}} \def\implies{\Rightarrow} \def\prob#1#2{{\mathop{{\rm Prob}}_{#1}}\left[#2 \right]} \def\var#1#2{{\mathop{{\rm Var}}_{#1}}[#2]} \def\expec#1#2{{\mathop{{\rm E}}_{#1}}[#2]} \def\sizeof#1{\left| #1\right|} \def\setof#1{\left\{ #1\right\} } \usepackage{psbox, amssymb} \textwidth=6in \oddsidemargin=0.25in \evensidemargin=0.25in \topmargin=-0.1in \footskip=0.8in \parindent=0.0cm \parskip=0.3cm \textheight=8.00in \setcounter{tocdepth} {3} \setcounter{secnumdepth} {2} \sloppy \newtheorem{example}{Example} % \P and \time are already used by LaTeX. :-( \newcommand{\ntime}{\hbox{NTIME}} \newcommand{\nspace}{\hbox{NSPACE}} \newcommand{\conspace}{\hbox{co-NSPACE}} \newcommand{\p}{\hbox{P}} \newcommand{\np}{\hbox{NP}} \newcommand{\pspace}{\hbox{PSPACE}} \newcommand{\lspace}{\hbox{L}} \newcommand{\conp}{\hbox{coNP}} \newcommand{\exptime}{\hbox{EXPTIME}} \newcommand{\elem}{\hbox{E}} \newcommand{\nl}{\hbox{NL}} \newcommand{\bpp}{\hbox{BPP}} \newcommand{\nregexp}{\hbox{NREGEXP}} \newcommand{\tqbf}{\hbox{TQBF}} \newcommand{\threesat}{\hbox{3SAT}} \newcommand{\cvp}{\hbox{CVP}} \newcommand{\stconn}{\hbox{STCONN}} \newcommand{\ispath}{\hbox{ISPATH}} %\newcommand{\class}{\hbox{$\mathbb{C}$}} \newcommand{\class}{\hbox{$\mathbf{C}$}} \newcommand{\lep}{\leq _{\hbox{P}}} \newcommand{\lel}{\leq _{\hbox{L}}} \newcommand{\aspace}[1]{{\rm ASPACE}(#1)} \newcommand{\atime}[1]{{\rm ATIME}(#1)} \newcommand{\spa}[1]{{\rm SPACE}(#1)} \newcommand{\ti}[1]{{\rm TIME}(#1)} \newcommand{\ap}{{\rm AP}} \newcommand{\al}{{\rm AL}}