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

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

\handout{quiz1topics}{Topics for Quiz 1}{Oct. 16, 1994}
\medskip

This is a list of many of the topics we have covered in the 
past five weeks that we expect you to know, 
as well as some hints and cautionary notes, for the upcoming quiz.

\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$

\item
Taylor series expansions, esp. for $e^x$ and $\ln (1+x)$

\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}


\end{enumerate}


\section*{Hints and Cautionary Notes}

\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
Don't forget to 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
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
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 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 
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
If you aren't sure about something, ask.

\end{enumerate}


\end{document}


