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

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

\handout{quiz2topics}{Topics for Quiz 2}{November 28, 1994}
\medskip

These are the topics we have covered since the first quiz.  
Quiz 2 will emphasize this material.  
You are still responsible, however, for earlier material.  
For example, you should be able to prove the correctness of a recurrence by
induction or count the number of graphs with a specific property.

\section*{Topics}

\begin{enumerate}

\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
	\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 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:
	$Pr[\overline{A}]=1-Pr[A]$, Boole's inequality, inclusion/exclusion
	\item Conditional probability
	\item Independence (both mutual and pairwise)
	\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.
	\item Random variables
	  \begin{itemize}
		\item Partitions sample space into events
		\item Independence---$Pr[E_1 \wedge E_2]=Pr[E_1]\cdot Pr[E_2]$
  		\item Binomial distribution
	  \end{itemize}
  \end{itemize}
\end{enumerate}


\section*{Miscellaneous comments}

\begin{enumerate}

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

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

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

\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  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
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, or formulas that don't satisfy the base conditions.

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

\end{enumerate}



\end{document}


