\documentstyle[12pt,twoside]{article}
\input{../macros-course}

\begin{document}


\handout{recitation}{\mbox{}}{Jan 24, 1996}

\section{First Recitation}

\begin{itemize}
\item What do we expect from you by way of a proof?
\item Direct proof. 
\item Proof by contradiction. $\sqrt{2}$ is irrational.
\item Proof by cases. $irrational^{irrational} = rational$ through
  $\sqrt{2}^{\sqrt{2}}$.
\item Nonconstructive proof. Infinity of primes.
\item Fallacy.
$1 = \sqrt{1} = \sqrt{(-1)(-1)} = -1$.
\end{itemize}

\section{Second Recitation}

\begin{itemize}
\item Induction misconceptions. 
  \begin{enumerate}
    \item All horses are the same color.
    \item I can lift all the sand in the world.
  \end{enumerate}
\item $15 | 2^{4n} - 1$.
\item Proof by induction that every well-formed arithmetic expression
  has the same number of left and right parentheses.
\end{itemize}

\section{Third Recitation}

\begin{itemize}
\item Definition of equivalence relations.
\item Examples of equivalence relations.
\item Partitions and equivalence relations are the same.
\item Composition of relations.
\item Fast exponentiation - explained.

\end{itemize}

\section{Fourth Recitation}

\begin{itemize}
\item Composition of functions.
\item Composition of bijective, injective and surjective functions.
\item In $7, 77, 777, \ldots $ there is a number divisible by $1997$
  but not by $1995$ - use of divisibility, mod as an equivalence
  relation and pigeon-hole principle.
\item Bijection from $(0,1)$ to the reals.
\item Pigeonhole - any st of $101$ numbers from $1 .. 200$ contains
  $x$ and $y$ such that $x | y$.
\end{itemize}

\section{Fifth Recitation}

\begin{itemize}
\item Go over topics for quiz and field questions.
\item Planar graphs are 6-colorable.
\item Algorithm and proof of transitive closure.
\item Connectivity and closure.
\item Trees have $n-1$ edges.
\end{itemize}

\section{Sixth Recitation}

\begin{itemize}
\item Asymptotic notation.
\item Bounds on $n!$ and $\log n!$ thru integrals.
\item Bounds on $\Sigma n^k$ thru integrals.
\item Sum $\Sigma_i \Sigma_j x^iy^j$.
\end{itemize}

\section{Seventh Recitation}

\begin{itemize}
\item Induction for big-Oh notation has pitfalls.
\item The tree method for $T(n) = T(2/3n) + T(n/4) + 5n$.
\item Change of variable for $T(n) = T(\sqrt{n}) + \log n$.
\item Solving recurrences by iteration.
\end{itemize}

\section{Eighth Recitation}

\begin{itemize}
\item No of different shortest paths from $(0,0)$ to $(m,n)$ and
  binomial coefficients.
\item Number of terminal zeros in $100!$.
\item Number of ways for occupants to leave $n$ houses in a row so
  that for all but the last a neighbor can check on the house once the
  occupant has left.
\item Number of surjective functions.
\item Number of derangements.
\item 

\end{itemize}

\section{Ninth Recitation}

\begin{itemize}
\item $\Sigma_{k=0}^r (n+k {\mbox choose } k) = (n+r+1 {\mbox choose } r)$.
\item Combinatorial and algebraic arguments for $\Sigma k (n {\mbox
    choose } k) = n2^{n-1}$.
\item Use of differentiation and integration in generating functions.
\item A bunch of generating function problems.
\end{itemize}

\section{Tenth Recitation}

\begin{itemize}
\item Birthday problem illustrated by failure probability of a
  spaceship which gets knocked out if there are two faults in a
  component.
\item Law of total probability, emphasize it doesn't work with
  conditioning.
\item Conditional probability illustrated using the OJ example.
\item Conditional probability illustrated using the Berkeley
  discrimination case.
\end{itemize}

\section{Eleventh Recitation}

\begin{itemize}
\item Prob of opening door on the last key w/wo replacement.
\item Coupon collecting problem with conditional probability stressed.
\item Problem of drawing balls from an urn without looking.
\item Zero probability events in infinite sample spaces, eg
  probability of never getting a head with a fair coin.
\item Paradox, of picking envelopes and switching to the higher one.
\end{itemize}

\section{Twelfth Recitation}

\begin{itemize}
\item Example with covariance with and without independence.
\item Variance of $n$ independent Bernoulli events.
\item Chebyshev - an example.
\item Chernoff - an example.
\item The normal distribution - some properties.
\item Poisson distribution - motivation and some properties.
\end{itemize}

\end{document}
