%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Using LaTeX to typeset your homework example % Chris Bourke % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %In LaTeX, the percentage sign is used for comments %Here we declare our document type, article is usually the default \documentclass{article} %This section of the TeX document is called the preamble where we %can define page styles and other meta data. More importantly we can %import external packages \usepackage{epsfig} %A package for importing EPS graphics into your document \usepackage{amsmath} %A package for AMSMath fonts \usepackage{amssymb} %A package for AMSMath Symbols \usepackage{amsthm} %A package for mathematical environments %If we are going to have theorems, corollaries, etc, then we need to %declare them in the preamble. The first argument is the environment %name, the second is what will be displayed in bold-font, look at the %example in the document body. \newtheorem{theorem}{Theorem} %We can also define new commands. Instead of having to write %\textbf{Problem} %Each time we want it displayed, we can simplify it by defining our own command %The first argument is what we call the command, the second is what the command %executes for us. Again, see the document body to see this in action. \newcommand{\problem}{\vspace{.5cm}\textbf{Problem:~~}} %\vspace{} defines some vertical whitespace for us. \textbf{} gives the %text a bold-font. The tilda is a special character that gives us a single %space of whitespace \newcommand{\answer}{\vspace{.25cm}\emph{Answer:~~}} %\emph{} stands for emphasize and gives the text an italic font %Here we define our page style, this example will leave the header %and footer empty on every page \pagestyle{empty} %You can play with the following commands if you wish to reset the page %widths, margins, etc. More info can be found in a comprehensive tutorial %\textwidth 17cm %\textheight 9.5in %Personally, I don't like having my paragraphs indented, instead we define %the following: \setlength{\parindent}{0pt} \setlength{\parskip}{.25cm} %Now we can define some meta-data that is specific to the article %document class \title{CSE 310 -- Homework 0} \author{Chris Bourke} \date{Fall 2004} %This is the end of the preamble, now we can begin our actual document \begin{document} \maketitle %This prints out a nice looking title with all the meta-data %Now let's start our document by stating the problem \problem (Levitin 2.1.1) For each of the following algorithms, indicate (i) a natural size matrix for its inputs; (ii) its basic operation; (iii) whether the basic operation count can be different for inputs of the same size. %The enumerate environment is used for numbered lists. Each item in the list % is assigned a default numbering. To override this numbering, as we have here, % you simply give it an optional argument [] and whatever you want it numbered % nested enumerate environments are handled by latex \begin{enumerate} \item[a.]Computing the sum of $n$ numbers \answer \begin{enumerate} \item[i.] $n$ \item[ii.] addition of two numbers \item[iii.] no \end{enumerate} %if we don't properly end an environment, latex will give us an error \item[b.] Computing $n!$ %The power of latex is its ability to typeset mathematical %formula, to enter math-mode in a line of text, use single %dollar signs \answer \begin{enumerate} \item[i.] $\lceil \log{n} \rceil$ %many mathematical symbols are available, %check out a more extensive tutorial \item[ii.] Multiplication of two integers \item[iii.] no \end{enumerate} \item[c.] Finding the largest element in a list of $n$ numbers \answer \begin{enumerate} \item[i.] $n$ \item[ii.] Comparison of two numbers \item[iii.] no \end{enumerate} \end{enumerate} %we can force Latex to start a new page by using the following command: \newpage \problem Prove that $\frac{n(n^2)}{2} \in \Omega(n)$ \answer We have the following theorem from Levitin, page 57: %There are many mathematical environments like this one for theorem \begin{theorem} \label{theorem:asymptotics} %we can label theorems and make references to them later %on in the document, but we will have to run latex %several times for them to take effect Let $f(n)$ and $g(n)$ be two monotonically increasing functions, then %Here we are entering math-mode on an entire line, so we use double dollar signs $$\lim_{n\rightarrow \infty} \frac{f(n)}{g(n)} = \left\{ \begin{array}{ll} 0 & \Rightarrow f(n) \in \mathcal{O}(g(n))\\ c & \Rightarrow f(n) \in \Theta(g(n))\\ \infty & \Rightarrow f(n) \in \Omega(g(n)) \end{array}\right.$$ \end{theorem} We set up our limit appropriately: $$\lim_{n\rightarrow \infty} \frac{\frac{n(n-1)}{2}}{n} = {n-1} = \infty$$ Therefore, by Theorem \ref{theorem:asymptotics}, $\frac{n(n^2)}{2} \in \Omega(n)$ %Notice the \ref command above, making reference to the labelled theorem. \problem Give an algorithm to compute the sum of $n$ integers stored in an array $\mathcal{A}$. \answer The following algorithm computes the sum: %\textsc is a capitalization font. note that the double \\ forces a page break %NOT a paragraph break. \textsc{Summation}$(\mathcal{A}[0 \ldots n-1])$\\ \textsc{Input:} an integer array $\mathcal{A}$\\ \textsc{Output:} the summation $\sum_{i=0}^{n-1} \mathcal{A}[i]$\\ \hspace*{.5cm}sum = 0\\ \hspace*{.5cm}\textbf{for} $i = 0 \ldots (n-1)$\\ \hspace*{1cm} sum = sum + $\mathcal{A}[i]$\\ \hspace*{.5cm}\textbf{return} sum %the \hspace{} command inserts white space. The * option forces whitespace %even at the beginning of a line \section*{Compiling Your Document} Now that our document is finished, we need to compile it. If you are on CSE or any other system that has \LaTeX\ installed, then you compile this document from the command line as follows: \texttt{latex hw\_example.tex} %note that the underscore is a special symbol that needs to be escaped \LaTeX\ will do its thing and report any errors that you may have, otherwise it will successfully compile in to a dvi file named \texttt{hw\_example.dvi}. At this point you have several options. You can convert the dvi file into a pdf file or a postscript file by using either \texttt{dvipdf} or \texttt{dvips} respectively. Another alternative is to use \texttt{pdflatex} instead of \texttt{latex}, which automatically outputs a pdf file rather than a dvi file. If you have labels like our label, \verb"\label{theorem:asymptotics}", you will need to run \texttt{latex} or \texttt{pdflatex} 2 or three times to compile the proper references. \section*{Additional Tools} You can use a program called \texttt{ispell} from the command prompt to spell check your document. Conveniently, \texttt{ispell} ignores \LaTeX\ markup! If you are just getting used to the linux environment, one of the best text editors for \LaTeX besides emacs and xemacs is nedit. This text editor recognizes \LaTeX\ markup uses font and color offsets to help you out. \section*{Additional Resources} The main source for \LaTeX\ resources is the \emph{\TeX\ Users Group}: \texttt{http://www.tug.org} in particular, check out their page for beginners, \emph{Getting Started With \LaTeX} at \texttt{http://www.tug.org/begin}. One of the best tutorials is the \emph{Not So Short Introduction to \LaTeX\ 2e} which can be found at\\ \texttt{http://www.ctan.org/tex-archive/info/lshort/english/lshort.pdf} \begin{center} {\Large Good Luck on your \LaTeX ing} \end{center} %This command tells LaTeX that our document is finished. \end{document}