\documentclass[12pt]{article}
\usepackage{times}
\usepackage{amssymb,latexsym, amsmath,graphics}
\usepackage[dvips]{graphicx}
\topmargin=-.75in \oddsidemargin=0in \textwidth=6.5in
\textheight=9in

\begin{document}
\title{A Sample \LaTeX document}
\author{Chuck Cusack}
\date{January, 2008}
\maketitle

The purpose of this document is to serve as an example of using \LaTeX.
Pieces are taken from several documents, so the content will make no
sense.  The ideas is to give you an idea of the syntax for accomplishing
various things.\\

Here is a {\em numbered list} of stuff
\begin{enumerate}
\item 
Number one
\item
Number 2
\item
The third.
\end{enumerate}


Here is a {\bf bulleted list}.
\begin{itemize}
\item 
The first item.
\item 
The Second.
\end{itemize}

Somewhere near this text you should see a figure of a circuit.

\begin{figure}[ht]
\begin{center}
\scalebox{.6}{\includegraphics{Circuit1.eps}}
\end{center}
\caption{An instance of {\sc Circuit-SAT}}
\end{figure}

An example of cases:
$$
c(i,j) =
\begin{cases}
    0,  &\text{if } (i,j) \in E,\\
    1,  &\text{if } (i,j) \notin E.
\end{cases}
$$

A Simple Table:\\

\begin{tabular}{|c||r|l|c|c|}
\hline
Center &Right&Left&\multicolumn{2}{|c|}{I am two columns}\\
\hline
\hline
me&Justify&justify&Blah&foo\\
\hline
&me&me&&stuff\\
\hline
WHatever I want&This doesn't mean anything&Just taking up space&&stuff\\
\hline
\end{tabular}

\vspace*{.25in}

Here is a complicated table on the same line as me.
\begin{tabular}{|c|c|c|c|c|c}
\multicolumn{1}{c}{1}
&\multicolumn{1}{c}{2} &\multicolumn{1}{c}{3}
&\multicolumn{1}{c}{4} &\multicolumn{1}{c}{5}
&\multicolumn{1}{c}{}\\
\cline{1-5}
0&&&&&1\\
\cline{1-5}
\multicolumn{1}{l|}{}&0&&&&2\\
\cline{2-5}
\multicolumn{2}{l|}{}&0&&&3\\
\cline{3-5}
\multicolumn{3}{l|}{}&0&&4\\
\cline{4-5}
\multicolumn{4}{l|}{}&0&5\\
\cline{5-5}
\end{tabular}

Here is an array:
$$
\begin{array}[t]{|l|l|l|l|}
\hline
y_2&y_4&y_5&\varphi_{2,3}\\
\hline
\hline
0&0&0&1\\
\hline
0&0&1&0\\
\hline
\end{array}
$$

A matrix:
$W_1=\left[\begin{array}[]{llll}
1&0&1&0\\
0&0&1&1\\
0&1&1&0\\
1&0&1&0\\
\end{array}
\right]
.$

Some math:\\

$$M[1,3]=\min
\left\{\begin{array}{l}
M[1,2]+M[3,3]+p_0p_2p_3=120+0+4\cdot 3\cdot 12 =264\\
M[1,1]+M[2,3]+p_0p_1p_3=0+360+4\cdot 10\cdot 12=840\\
\end{array}
\right.$$

\begin{eqnarray*}
x_{11}
&\wedge&[(x_1\wedge x_2) \leftrightarrow x_6]\\
&\wedge&[(\neg x_3) \leftrightarrow x_7]\\
&\wedge&[(x_9\vee x_{10}) \leftrightarrow x_{11}]
\end{eqnarray*}

Let $x\in A\cap\overline B$.  
Then $x\in A$ and $x\in \overline{B}$ by definition of intersection ($\cap$).
The skip some steps. Finally,
since $A-B\subseteq A\cap\overline B$ and $A\cap\overline B\subseteq A-B$,
$A-B = A\cap\overline B$.  Also, 
$\lceil x + m \rceil=\lceil x \rceil + m$.\\
Notice that 
\begin{tabular}[t]{lll}
$x\in A-B$& iff & $x\in A$ and $x\not\in B$\\
          & iff & $x\in A$ and $x\in\overline{B}$\\
          & iff & $x\in A\cap\overline B$
\end{tabular}\\

\noindent
{\em Show that $\sum_{i=1}^{n}(a_i-a_{i-1})=a_n-a_0$, where
$a_0$, $a_1$, $\ldots$, $a_n$ are real numbers.}\\
Show that ${\displaystyle \sum_{i=1}^{n}(a_i-a_{i-1})=a_n-a_0}$.
\begin{eqnarray*}
\sum_{i=1}^{n}(a_i-a_{i-1})
&=&\left(\sum_{i=1}^{n}a_i\right)-\left(\sum_{i=1}^{n}a_{i-1}\right)\\
&=&(a_1-a_1)+(a_2-a_2)+\cdots+(a_{n-1}-a_{n-1})+a_n -a_0\\
&=&a_n-a_0.
\end{eqnarray*}

\noindent
{\Large \bf Definitions}\\
We say that $f(n)$ is {\bf Big-O} of $g(n)$, written as 
$f(n) = O(g(n))$,
iff there are positive constants $c$ and $n_{0}$ such that
$$0\leq f(n)\leq c\,g(n)\mbox{ for all }n \ge n_{0}$$
If $f(n)=O(g(n))$, we say that $g(n)$ is an {\bf upper bound} on $f(n)$.\\

{\em 
\noindent
{\bf Theorem 1}\\ 
Let $f(n)$ and $g(n)$ be functions such that 
$$\lim_{x\rightarrow \infty}{f(n)\over g(n)} = A.$$
Then
\begin{enumerate}
\item If $A=0$, then $f(n)=O(g(n))$, and $f(n)\neq \Theta(g(n))$.
\item If $A=\infty$, then $f(n)=\Omega(g(n))$, and $f(n)\neq \Theta(g(n))$.
\item If $A\neq 0$ is finite, then $f(n)=\Theta(g(n))$.
\end{enumerate}
}

{\em
\noindent
{\bf Theorem 2: {\em l'Hopital's Rule}}\\
Let $f(x)$ and $g(x)$ be differentiable functions.
If ${\displaystyle \lim_{x\rightarrow\infty}f(x)=\lim_{x\rightarrow\infty}g(x)=0}$ or
${\displaystyle \lim_{x\rightarrow\infty}f(x)=\lim_{x\rightarrow\infty}g(x)=\infty,}$ then
$$
\lim_{x\rightarrow\infty} {f(x)\over g(x)}=
\lim_{x\rightarrow\infty} {f^{\prime}(x)\over g^{\prime}(x)}$$
}

\noindent
{\Large\bf Examples}\\
\begin{enumerate}
\item
If $f(x)=O(g(x))$, 
then there are positive constants $c_2$ and $n_{0}^{\prime}$ such that 
$$0\leq f(n)\leq c_2\,g(n)\mbox{ for all }n \ge n_{0}^{\prime}$$
We can divide this by $c_1^{\prime}$ to obtain 
$$0\leq \frac{1}{c_1^{\prime}}g(n)\leq f(n)\mbox{ for all }n 
\ge n_{0}^{\prime\prime}.$$
Setting $c_1=1/c_1^{\prime}$ and 
$n_0=\max(n_0^{\prime},n_0^{\prime\prime})$, 
we have 
$$0\leq c_1 g(n)\leq f(n)\leq c_2\,g(n)\mbox{ for all }n \ge n_{0}.$$
Thus, $f(x)=\Theta(g(x)).$

\item
Show that $n!=O(n^n)$\\
{\bf Proof:} \\
Notice that when $n\geq 1$, 
$0\leq n!=1\cdot 2\cdot 3\cdots n \leq n\cdot n\cdots n = n^n.$
Therefore $n!=O(n^n)$ (Here $n_0=1$, and $c=1$.)


\item
Find a tight bound on $f(x)=x^4-23 x^3 + 12x^2 + 15 x - 21$.\\

{\bf Solution \#1}\\
It is clear that when $x\geq 1$, 
$$x^4-23 x^3 + 12x^2 + 15 x - 21\leq x^4+12 x^2+15 x
\leq x^4+12 x^4+15 x^4= 28 x^4.$$
Also,
$$x^4-23 x^3 + 12x^2 + 15 x - 21\geq x^4-23 x^3 - 21\geq 
x^4 - 23 x^3 - 21 x^3= x^4 - 44 x^3\geq \frac{1}{2}x^4,$$
whenever 
$$\frac{1}{2}x^4\geq 44x^3 \Leftrightarrow x\geq 88.$$
Thus
$$\frac{1}{2}x^4\leq x^4-23 x^3 + 12x^2 + 15 x - 21\leq 28 x^4,
\mbox{ for all } x\geq 88.$$
We have shown that $f(x)=x^4-23 x^3 + 12x^2 + 15 x - 21=\Theta(x^4).$\\

{\bf Solution \#2}\\
From Solution \#1 we already know that $f(x)=\Theta(x^4)$.  We verify this by
noticing that 
\begin{eqnarray*}
\lim_{x\rightarrow\infty}
x^4-23 x^3 + 12x^2 + 15 x - 21
& =& \lim_{x\rightarrow\infty}
{x^4\over x^4} - {23x^3\over x^4} + {12x^2\over x^4} 
+ {15x\over x^4} - {21\over x^4}\\
& =& \lim_{x\rightarrow\infty}
1 - {23\over x}+ {12\over x^2} + {15\over x^3} - {21\over x^4}\\
&=& \lim_{x\rightarrow\infty}
1 - 0 + 0 + 0 - 0=1
\end{eqnarray*}
\hrulefill


\item
Show that $(\sqrt{2})^{\log n}=O(\sqrt{n})$, where $\log$ means $\log_2$.\\
{\bf Proof:}\\
It is not too hard to see that 
$$(\sqrt{2})^{\log n}=n^{\log \sqrt{2}}=n^{\log 2^{1/2}}=
n^{\frac{1}{2}\log 2}=n^{\frac{1}{2}}=\sqrt{n}.$$
Thus it is clear that $(\sqrt{2})^{\log n}=O(\sqrt{n})$.

\hrulefill
\item
Show that $2^x=O(3^x)$.\\
{\bf Proof \#1:}\\
This is easy to see since
${\displaystyle \lim_{x\rightarrow\infty} {2^x\over 3^x}
= \lim_{x\rightarrow\infty} \left({2\over 3}\right)^x
= \lim_{x\rightarrow\infty} 0.}$\\

{\bf Proof \#2:}\\
If $x\geq 1$, then clearly $(3/2)^x\geq 1$, so 
$$2^x\leq 
2^x\left({3\over 2}\right)^x=
\left({2\times 3\over 2}\right)^x=3^x.$$


\end{enumerate}


\end{document}