\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}

\newcommand{\lcm}{\mbox{lcm}}
\begin{document}

\handout{examtopics}{Topics for the Exam}{December 18, 1994}
\medskip

This is a list of many of the topics we have covered in the 
class that we expect you to know, 
as well as some hints and cautionary notes, for the exam.


\section*{Topics}

\begin{enumerate}

\item
Proof Structure
\begin{itemize}

\item
Truth Tables

\item
When does $A \implies B$? $A \iff B$? $A \iff B \iff C$?
How can we prove these?  

\item
Proof techniques: contradiction, contrapositive, case analysis

%\item
%What is a proposition?

\item
Rules of inference: syllogism, modus ponens, modus tollens

\item
Predicates and their negation; interpretation as sets.

\item
Quantifiers:
\begin{itemize}

\item
``for all'' ($\forall$) and ``there exists'' ($\exists$), and their negations

\item
Universal generalization

\end{itemize}

\end{itemize}

\item
Induction and Well-Ordering
\begin{itemize}

\item
Equivalence of strong and weak induction and well-ordering

\item
Structural induction

\end{itemize}

\item
Number Theory (theory of $\integers$ and $\nats$)
\begin{itemize}

\item
Divisibility: definition and simple theorems ($a,b,c \in \integers$)
\begin{itemize}
\item $a \divides b \implies a \divides bc$ for all $c$
\item $a \divides b \land b \divides c \implies a \divides c$
\item $a \divides b \land a \divides c \implies a \divides (bx+cy)$ 
for all $x,y \in \integers$
\item $a \divides b \land b \divides a \implies a = \pm b$
\item $a \divides b \land a,b > 0 \implies a \leq b$ 
\end{itemize}

\item
Division algorithm

\item
GCD: definition and basic theorems ($a,b \in \integers$)
\begin{itemize}

\item 
$\gcd(a,b) = \gcd(a, a+b)$

\item
$\gcd(a,b) = ax + by$ for some $x,y \in \integers$ (least positive such value)

\item
$d \divides a \land d \divides b \implies d \divides \gcd(a,b)$

\item
Euclid's algorithm

\end{itemize}

\item
Prime numbers and Unique Prime Factorization

\item
Word problems and solving Diophantine equations
\begin{itemize}

\item
Extending Euclid's algorithm: the tabular method

\item
Finding the general solution (within specified constraints)

\end{itemize}

\end{itemize}

\item
Graphs (Undirected and Directed)
\begin{itemize}

\item
Basic definitions:
\begin{minipage}[t]{3in}
\begin{tabbing}
vertices and edges \\
adjacency (incidence)  \\
degree, indegree and outdegree \\
paths, simple paths, path length\\
connected \\
cycles, simple cycles\\
acyclic \\
free tree \\
bipartite
\end{tabbing}
\end{minipage}

\item 
Handshaking Lemma

\item
Equivalent {\em free tree} definitions

\item
DAGs and topological sort

\item
Trees: free, rooted, ordered, positional, binary, k-ary
\begin{itemize}
\item
Structural induction for k-ary trees
\end{itemize}

\item
Adjacency matrix representation

\item
Representation of (finite) relations

\item
Computing paths of length k, reflexive and transitive closure

\end{itemize}

\item
Relations
\begin{itemize}

\item
Properties:
\begin{minipage}[t]{3in}
reflexivity \\
symmetry \\
transitivity \\
antisymmetry \\
total
\end{minipage}

\item
Equivalence relations, equivalence classes, and partitions

\item
Partial orders and posets (representation as dag)

\item
Reflexive and transitive closure (again!)

\end{itemize}

\item
Functions
\begin{itemize}

\item
Definition; domain, codomain = range, image

\item
Composition

\item
Injections, surjections, bijections

\item
Inverses

\end{itemize}

\item
Pigeonhole Principle (including Strong Pigeonhole Principle)

\item
Countability
\begin{itemize}

\item
Finite and infinite sets; definition of infinity and countability

\item
Uncountability and diagonalization

\item
Which sets are countable: $\nats$, $\integers$, $\rationals$, $\reals$, 
$\reals - \rationals$

\end{itemize}

\item
Asymptotic notation
\begin{itemize}

\item
Definitions of $O$, $\Omega$, $\Theta$, $o$, $\omega$, $\sim$

\item
Comparing orders of growth: $e^x > x^k > \log x$ as $x \rightarrow \infty$

\end{itemize}

\item
Series
\begin{itemize}

\item
Geometric and arithmetic series

\item
Proving closed form by induction

\item
Guessing the form of the solution

\item
Using derivatives to find solution

\item
Integral method (and bounding error term)

\item
Stirling's formula: $n! \sim (\frac{n}{e})^n \sqrt{2\pi n}$

\item
Harmonic numbers
\end{itemize}

\item Recurrences
  \begin{itemize}
	\item Techniques for solving
	  \begin{itemize}
	    	\item Guess and verify by induction
		\item Iteration (Substitution)
		\item Tree method
	  \end{itemize}
	\item Linear Recurrences
	  \begin{itemize}
	    	\item Determine characteristic equation
		\item Find homogeneous solution (know how
			to handle multiple roots)
		\item Find particular solution by guessing.
		For polynomials, try a similar polynomial; 
		and for exponentials, try a similar exponential.
		\item Combine homogeneous and particular solution
			to find total solution.
	  \end{itemize}
	\item Asymptotic behavior
  \end{itemize}


\item Combinatorics
  \begin{itemize}
	\item Sum, Product, and Division rules
	\item Permutations and Combinations 
	\item Pascal's formula and triangle
	\item Binomial coefficients, Binomial Theorem
	\item Multisets and combinations of multisets
	\item Distinguishable vs. indistinguishable balls/bins
	\item Use of the ``Stars and Bars'' technique
	\item Algebraic and combinatorial proofs
(e.g. for $\sum_{i=0}^n {n \choose i} =2^n$)
	\item Generalized binomial theorem
	\item Multinomial theorem
	\item Stirling's formula (again)
	\item Inclusion-Exclusion
  \end{itemize}

\item Generating functions
  \begin{itemize}
	\item Basic forms
	  \begin{itemize}
		\item $\frac{1}{1-ax}$
		\item $\frac{1}{(1-x)^2}$
		\item $\frac{1}{1-x^k}$
	  \end{itemize}
\item
Taylor series expansions, esp. for $e^x$ and $\ln (1+x)$
	\item Solving linear recurrences
	\item Convolution and counting
	combinations by multiplying generating functions.
	\item Basic operations---%
differentiation,
integration,
left/right shift,
convolution,
and prefix sum
	\item Partial fraction decomposition (to recover an expression for
the coefficient of~$x^n$)
	\item Catalan numbers
  \end{itemize}
	
\item Probability
  \begin{itemize}
	\item Basic definitions---sample space, outcome/sample point, and event
	\item Probability trees
	\item Monty Hall problem and variations
	\item Venn diagrams
	\item Basic probability laws:
	\begin{itemize}
		\item $Pr[\overline{A}]=1-Pr[A]$
		\item Boole's inequality: $Pr[\cup_i A_i] \leq \sum_i Pr[A_i]$
		\item inclusion/exclusion
	\end{itemize}
	\item Conditional probability
	\item Independence---$Pr[E_1 \wedge E_2]=Pr[E_1]\cdot Pr[E_2]$
	\item Difference between mutual and pairwise independence
	\item Uniform sample space (reduces probability to counting)
	\item Law of total probability and Bayes' Theorem
	\item Calculating upper and lower bounds.
	\item Asymptotics -- Remember 
	approximations for $e^x$ and $\ln(1+x)$ for $x$ small.
  \end{itemize}

\item Random variables
  \begin{itemize}
\item Maps points in sample space to real numbers
\item Expected value
\begin{itemize}
	\item $E[R] = \sum_r r Pr[R=r]$
	\item $E[R_1 + R_2] = E[R_1] + E[R_2]$ whether or not $R_1$ and $R_2$ are independent
	\item $E[a R] = a E[R]$ and $E[R+a] = E[R]+a$, where $a$ is a scalar
	\item If $R$ is always a natural number, $E[R] = \sum_{n=0}^{\infty}
Pr[R>n]$
	\item $E[R_1 R_2] = E[R_1] E[R_2]$ if $R_1$ and $R_2$ are independent
	\end{itemize}
\item Variance and Standard Deviation
\begin{itemize}
\item $Var[R] = E[(R-E[R])^2] = E[R^2] - E[R]^2$
\item $\sigma_R = \sqrt{Var[R]}$
\item $Var[aR] = a^2 Var[R]$ and $Var[R+a] = Var[R]$, where $a$ is a scalar.
\item $Var[R_1+R_2] = Var[R_1] + Var[R_2]$ if $R_1$ and $R_2$ are independent.
\end{itemize}
\item Different types of random variables: Bernoulli, binomial, Poisson
\item Markov's bound: If $R\geq 0$ then $Pr[R\geq x] \leq E[R]/x$
\item Chebyshev's bound: $Pr[|R-E[R]| \geq x] \leq Var[R]/x^2$
\item Chernoff type bounds: If $R$ is the sum of independent Bernoulli random
variables,
\begin{itemize}
\item $Pr[R=0] \leq e^{-E[R]}$
\item $Pr[R\geq cE[R]] \leq e^{-\alpha c E[R]}$ if $c\geq 1$ and $\alpha = \ln
c + 1/c -1$
\end{itemize}
\item Normal approximation to the binomial distribution
\item If $R$ is always a natural number, probability generating function
\item Moment generating function; relation to probability generating function
\item Gambler's ruin
 \end{itemize}
\end{enumerate}


\section*{Cautionary Notes}

\begin{enumerate}

\item
Beware of ``build-up errors'' in your induction proofs.  
When trying to construct a graph, or tree, or anything, 
you should always ask yourself, ``How do I know that 
every graph (or tree or whatever) can be constructed that way
(and have I proven that)?'' 

\item
Watch out for ``fence-post errors.'' 
Make sure you get the base case right.

\item
Know the differences between a relation, a function, an injection, a
surjection, and a bijection.  To show that a relation is an injection or a
surjection,  you must first demonstrate that it is a function.

\item
Be careful about using asymptotic notation with induction.

\item  After solving a recurrence, it helps to verify
it for a few small numbers.  Although this doesn't guarantee you
have the right answer, it will often catch a wrong answer.

\item
Don't assume events are independent without justification.
You can still prove upper and lower bounds without assuming
independence or uniformity.

\item Simplify your answers (i.e. cancel like terms, remove radicals
from the denominator).  This will help you catch answers, which
you know are wrong.  For example, probabilities that
are greater than one, sets with negative size, or formulas that don't satisfy
the base conditions.


\end{enumerate}


\section*{Hints}

\begin{enumerate}

\item
Make sure you understand the problem before tackling it.  
Always ask yourself, ``What does this mean?''

\item
Make the structure of your proof clear.
Say clearly what you are assuming and what you are trying to prove 
(especially the induction variable and hypothesis in induction proofs).

\item
Define clearly all terms and variables you use.  
Don't denote different things with the same variable in the same formula.

\item
Check that any definitions you make are well-defined, 
and that you don't assume two definitions are equivalent 
unless you (or we) have proven they are.

\item
When something is ``obvious,'' 
you don't need to say it is.  Just state it without preamble.  
If you feel the need to point this out, 
it probably isn't that obvious after all, 
and you should explain why it is true.

\item
Don't forget to use the proper quantifiers (``for all'' vs. ``for some'').

\item
When you ``work backwards'' in your proofs, 
make sure your implications are pointing the right way.  
They have to start from your assumptions, and end up at your conclusion.
 
\item
Remember that the meaning of {\em degree} depends on whether 
you are in a graph (or free tree) or a rooted tree.

\item
Don't confuse {\em connected} with {\em adjacent}.

\item
If $R$ is an equivalence relation on a set $S$, 
then for any $s \in S$, we denote the equivalence class of $s$ 
(under $R$) by $[s]$.  We often omit saying ``under $R$'' when 
there is only one equivalence relation.  The equivalence classes 
of $R$ are the sets $[s]$ for all the $s \in S$,
and they partition $S$.  So equivalence classes of $R$ are 
subsets of $S$, {\em not} of $S \times S$.  
Also, equivalence classes are only well-defined if $R$ is 
an equivalence relation.

\item 
To show two sets $A$ and $B$ are equal, we often show 
$A \subseteq B$ and $B \subseteq A$.

\item
To show that something is unique, 
we often show that if we had two of them, they must be equal.

\item Be careful with your exponentiation rules.
Remember that $2^{\log^2 n} \neq n^2$.

\item When doing asymptotics with exponentials, it often helps
to move all the variables into the exponent to make it easier to
compare terms.

\item  Remember to include the base conditions when
solving recurrences and using generating functions.

\item  Know the difference between, and when to use,
combinations and permutations, 
and distinguishable vs. indistinguishable items.

\item  Be careful about using asymptotic notation with induction.

\item  Remember that asymptotic bounds do not give actual upper or
lower bound for specific values; they represent rate of growth.

\item Clearly state any assumptions you make about the uniformity of
the sample space (e.g., in poker, you often assume that all possible
hands are equally likely) or about the randomness of choices (e.g.,
Monty reveals a door randomly and uniformly from the set of all losing
doors).

\item
If you aren't sure about something, please ask.

\end{enumerate}



\end{document}


