\documentclass[11pt]{article}
\usepackage{amsmath}
\input{macros-course}

\begin{document}

%\handout{}{Appendix for Quiz 2}{November 4, 1999}


The following appendix will be attached to Quiz 2 on November 4, 1999, so
you need not include these facts on your crib-sheet.

\section*{Appendix}

A \textbf{simple graph} is an undirected graph with no self loops and at
most one edge between any two nodes.

An \textbf{Eulerian circuit} in a graph is a path beginning and ending at
the same vertex and containing each edge exactly once.

The \textbf{complete graph}, $K_n$, is the simple graph with $n$ vertices and
with an edge between every two vertices.

The \textbf{degree} of a vertex in a graph is the number of edges at the vertex.

\textbf{Lexicographic order}, $\preceq$, on pairs of natural numbers is
defined by the rule that
\[
(n_1,n_2) \preceq (m_1,m_2) \quad \mbox{iff} \quad [(n_1 < m_1) \mbox{ or } (n_1
= m_1 \mbox{ and } n_2 \leq m_2)].
\]

\[
\sum_{i=0}^n r^i = \frac{r^{n+1} - 1}{r-1}.
\]

\[
\sum_{i=0}^{n} ir^i = \frac{{r - (n+1) r^{n+1} + n r^{n+2}}}{(1-r)^2}.
\]

\[
\int \ln x dx = x \ln (x/e).
\]

\textbf{Stirling's formula}:
\[
n! \sim  \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n.
\]

\textbf{The Principle of Inclusion-Exclusion}:
\[
\card{\Union_{i=1}^n A_i}
= \sum_{S \subset \set{1,\dots,n}}
           (-1)^{\card{S}} \card{\Intersect_{j \in S} A_j}
\]

\newpage
\section*{Topics for Quiz 2}
\begin{itemize}

\item Graphs and Trees, 
\item Relations and Posets,
\item State Machines,
\item Sums and Series,
\item $O(), \Theta()$, and Stirling's Formula,
\item Linear Recurrences,
\item Permutations + General inclusion-exclusion (very lightly)

\end{itemize}

\end{document}
