%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	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
\usepackage{cite} % A package for cite

%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 235 Homework Template\footnote{This document was created by Chris Bourke~\cite{Bourke04}.}}
\author{Jie Feng }
\date{Fall 2008}

%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.] Nothing else.

    \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.


Here is a mathematical expression: $(a + b)^{2k}_{n_{i}}
\frac{3x}{7y}$.  Note that it is written in line, in the text.

The following mathematical expression is displayed on a new line,
centered, but it is not assigned a number: \[(a + b )^{2k}_{n_{i}}
\frac{3x}{7y}\]


The equation~(\ref{eq:example1}) has a number and a label, which can
be referenced in the text.
   \begin{equation}
   (a + b){n_{i}} \frac{3x}{7y}
   \label{eq:example1}
   \end{equation}

The set of equations below are listed as an array.  Only two are numbered.
   \begin{eqnarray}
   (a + b)^2 & = &  a^2 + b^2 + 2ab\\
   (a + b)^2 & = &  a^2 + b^2 + 2ab\\ \nonumber
   (a + b)^3 & = &  a^3 + 3a^2b + 3ab^2 + b^3\\
 \end{eqnarray}



\problem Draw the graph $K_5$.

\answer  $K_4$ is shown in Figure~\ref{fig:k4}

% If you compile with the command `pdflatex', the figure should be a PDF file.
% If you compile with the command `latex', the figure should be an EPS file.
\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.6]{k5.eps}
\caption{\small A complete graph with 5 nodes.}
\label{fig:k4}
\end{center}
\end{figure}


\problem Define the semantics of the logical connective $\wedge$ in Propositional logic.

\answer Given two logical propositions $a$ and $b$, the semantics of $\wedge$ is defined in Table~\ref{tab:logical-and}:
\begin{table}[ht]
\caption{\small Definition of the logical connective $\wedge$.}
\begin{center}
\begin{tabular}{|cc|c|}\hline
a & b & a $\wedge$ b\\\hline\hline

0 & 0 & 0 \\

0 & 1 & 0 \\

1 & 0 & 0 \\

1 & 1 & 1 \\\hline
\end{tabular}
\end{center}
\label{tab:logical-and}
\end{table}

\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}

\bibliographystyle{plain}

\bibliography{BibliographyFile}

%This command tells LaTeX that our document is finished.
\end{document}