\documentstyle[11pt, fullpage]{article}
\addtolength{\parskip}{1ex}
\setlength{\parindent}{0in}

\newcommand{\ignore}[1]{}
\newcommand{\remark}[1]{[{\small{\bf Editorial Remark: }#1}]}


\title{\vspace{-0.5in}
\bf 15-451 Algorithms, Fall 2000\\ Problem Set 1}
\author{\bf Al Gore-ithm\thanks{Presidential candidate and amateur hacker.}}
\begin{document}

\maketitle

\section{Problem 1}
In order to compile this, run {\bf latex sample.tex} on your favorite unix
machine.  This will create a file called {\em sample.dvi}.  In order to view
this, run {\bf xdvi sample.dvi}.  You can leave this running and it will
automatically update when you re-run latex on your revised document.
Alternatively, you can then produce postscript with {\bf dvips -o
sample.ps sample.dvi} and view the postscript with ghostview (gv).  To
print your document, create the postscript file and run it through
lpr.  Just edit this file to do your
next assignment. 

\section{Problem 2}
You can make numbered lists like this:
\begin{enumerate}
\item Here is the first step of my amazing algorithm.
\item Here is the second step.
\item Don't all algorithms have to have 3 steps?
\end{enumerate}
and bulleted lists like this:
\begin{itemize}
\item blah blah blah...
\item ...and furthermore, dividing both sides by $e^{x^2}$ gives us the
final result.
\end{itemize}
The ``description'' environment is also handy:
\begin{description}
\item[Base case:] The base case of the algorithm is the case $n <
	23$ in which case the result follows by a simple calculation.
\item[Inductive case:] We now show that the result follows for
general values of $n$ by induction on the height of the tree and
fragrance of the leaves.
\end{description}

\section{Problem 3}
Here is some of the mathematical stuff you can do.  Inline formulae are done
with \$ signs, like this $x, x^2, x_i, x_{i+1}, \sqrt{x+y}, f(x) = O(n \log
n)$ and $f(x) = \Omega(n \log n)$, therefore $f(x) = \Theta(n \log n)$.  There
are lots of built-in symbols: $\leq \div \star \dagger \in \subseteq
\rightarrow
\spadesuit \alpha \beta \gamma$ and built-in functions and operators: 
$\ln \log \sum \int \max$.

You can also do formulae on a line by themselves with double \$ signs:
$$\sum^n_{i = 1} \frac{{n\choose i}}{n!}$$
There is truly no end to the magic.

You can even write pseudo-code if you import the special {\bf code.tex} file:
\input{/afs/cs.cmu.edu/academic/class/15451-f00/www/Sample/code.tex}

\begin{small}
\codebox{%
\<$\procdecl{Count}(L,R,l,r)$\\
\li \If $L=R+1$\\
\li \Then \If $l=\const{nil}$ and $r=\const{nil}$ \\
\li \>\>\Then \Return 1 \\
\li \>\>\Else \Return 0 \\
\li \Else $\id{total}\gets 0$ \\
\li \>\>\For $W\gets L+1$ \To $R-1$ \\
\li \>\>\Do \While $i > 0$\\
\li \>\>\>\>\Do\If $l\neq\const{nil}$ and $left[d]\neq\const{nil}$ and
                                       $\proc{Match}(l,left[d])$ \\
\li \>\>\>\>\>\>\Then$\id{leftcount}\gets\proc{Count}(L, W,
                          \id{next}[l],\id{next}[\id{left}[d]])$ \\
\li \>\>\>\>\>\>\Else$\id{leftcount}\gets 0$ \\
\li \>\>\Return$\id{total}$
}
\end{small}

\end{document}
