\documentstyle[11pt]{article}

\setlength{\oddsidemargin}{-0.1 in}
\setlength{\evensidemargin}{-.3 in}
\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8in}

\setlength{\parskip}{\medskipamount}
\pagestyle{empty}

\begin{document}

\noindent
6.042 Course Outline \hfill \today

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Basic Background (4 weeks)}

This is simple definitional stuff that everyone should know for the
course, and that many will know some of when they enter.  It will be
review for some and a good way to get everyone on the same footing.

\begin{enumerate}
\setlength\itemsep{.5in}

\item Formal proofs and induction (2 lectures): \\
axioms, quantifiers, notation, predicates, Peano's postulates,
deduction, reasoning, strong and weak induction, well-ordering, proof
well-ordering = induction, emphasis on mechanics of induction. (0.7,
ch2 of MR).

\item Sets, relations, functions (1 lecture): \\
basic defs (0.1-0.2 of MR), set operations, DeMorgan's law,
equivalence, equivalence classes, proof of partition = equiv.
relation, definition of a function, emphasis on set-theoretic proofs.

\item Graphs, trees, and matrices (1 lecture): \\
defs, representing a graph as an adjacency matrix, tie in to relations
as graphs and matrices, dags, partial orders, examples with
combinational circuits and finite-state machines, equivalent defs of
trees.  (0.6, 3.1-3.2 of MR, 8.1-8.5 of B)

\item Algorithms and data structures (2 lectures): \\
defs, specification, correctness, running time, language, arrays,
stacks, queues, linked lists, recursion, tree structures (baby stuff
here just to make sure that we can draw examples from this domain in
the future) (ch2 from MR) Loop invariants, proving correctness (0.7,
ch2 of MR).

\item Functions and asymptotics (2 lectures): \\
O-notation, Omega, etc., important functions: absolute value,
ceiling/floor, factorial, Stirling's formula, mod, log, lg, ln,
exponential, polynomial.  Summation and product notation, evaluating
and bounding summations, sum of $i, i^2, 1/i, 1/i^2, 2^i, 1/2^i, \log
i$, etc., bounds obtained by integration.  (0.3-0.5 of MR) (CLR??)

\end{enumerate}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Counting and Combinatorics (4 weeks)}

Here we start real stuff and give a more integrated series of
lectures.

\begin{enumerate}
\setlength\itemsep{.5in}

\item Elementary counting (1 lecture): \\
bijections with the integers, countable infinite sets, sum, product
and division rules, Pigeonhole principle (4.1-4.3, 4.10 of MR,
2.4,3.1-3.2 of B)

\item Permutations and combinations (2 lectures): \\
defs, binomials and multinomials, combinatorial identities, binomial
thm, multinomial thm, balls and boxes problems, Pascal's Triangle
(4.4-4.7 of MR, 3.4-3.6, 4.1-4.3, 5.3, 5.5-5.6 of B)

\item Inclusion/Exclusion Principle (1 lecture): \\
(4.8 of MR, 4.4-4.5 of B)

\item Recurrences (2 lectures): \\
master thm from CLR, linear Fibbonaci-type recurrences, changing
variables, solution by induction, substitution (ch 5 of MR)

\item Generating functions (2 lectures): \\
defs, use of derivitives, ordinary and exponential(?), prefix sum:
multiplication by $1/(1-x)$ (no source yet, but perhaps Liu). We'll
keep it simple here--prepares the way for moment generating functions
later.

\end{enumerate}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Probability (5 weeks)}

Covers basics of probability from the discrete perspective with
applications drawn from CS and other sciences.  
Heavy reliance on counting material makes it fit well.  
Material covers 5 weeks of lecture over a 6-week period.  
It is expected that we will
cover some new material in the recitations toward the end.

\begin{enumerate}

%%	1.
\item Foundations (2 lectures):\\

sample spaces, events, assigning probabilities to events, Monty Hall
games, $P(A+B)=P(A)+P(B)-P(A\cap B)$, tie into set laws from 1st week,
notion of high probability, law of very many unlikely events: with
high probability, none of them will occur (6.2 of MR, 1.1 and 1.3 of
Ash)

%%	2.
\item Independence (1 lecture): \\

definitions, law of very many unlikely independent events: with high
probability, at least one will occur, card trick: mind reading game.

%%	3.
\item Conditional probabilities (1 lecture): \\

Bayes Thm. (6.3 of MR, include fallacies from 1.7 of Ash as
appropriate).

%%	4.
\item Random variables (1 lecture):\\

basic def, important distributions, functions of rvs, sums of rvs,
convolution (6.4 of MR).

%%	5. 
\item Expectation and variance (2 lectures):\\

Basic defs, Markov's thm, applications to hashing, inference by
polling, randomized algorithms (6.5-6.6 of MR).

%%	6. 
\item 	Chernoff Bounds (1 lecture):\\

moment generating functions, application to sums of Bernoulli rvs.

%%	7. 
\item Random walks (1 lecture):	\\

gambler's ruin, time to return to origin, mention of Markov chains,
reflection principle (?).

%%	8. 
\item Queueing theory (1 lecture):\\

basic defs, relation to random walks

\end{enumerate}


Applications areas:

\begin{itemize}

\item Computer Science (the main focus)
\item Biology (string matching, genetics)
\item Chemistry (rates of reaction, birth/death processes)
\item Social Science (polling and prediction)
\item Engineering (reliability and fault tolerance)

\end{itemize}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{18.063  Introduction to Discrete Applied Math II [U(1,2) 4-0-8]}

Prereqs: 18.062J

{\small
\begin{verbatim}

Date: Fri, 1 Oct 93 10:06:59 EDT
From: apm@math.mit.edu
To: ftl@math.mit.edu
Subject: 062

Thanks for the outline.  The breakdown 062-063 seems reasonable.  The only
question I had was on public-key cryptosystems:  I assume the RSA system
would be left for 063, since it depends on Fermat's theorem, the prime number
theorem, gcd algorithm; in 063 it has been a useful lecture showing that
the ideas of elementary number theory that have been studied up to that
point can all be used in a practical application.

The content of 062 doesn't seem excessive to me.

I think it should be planned as a 12-unit course; if there is a tutorial,
it could be 5-0-7; since a tutorial usually gives substantial problem set
help (as does the recitation now in 063).

I'm not in favor of calling 063 Part II of the year sequence; as currently
planned, the material on counting and probability is not really used in 063
and the basic material (sets, functions, induction) can easily be picked up
in a variety of other math courses (matrices are done in 18.02 and 18.03),
so that .063 should probably have an independent existence, so as not to 
scare people off who could manage it perfectly well.  Of course, if it will
be extensively redesigned, this could change.

Keep me posted.

Arthur
\end{verbatim}
}

Modified to contain four basic components:

\begin{enumerate}

\item Number theory (as done now)

\item Algebra (as done now)

\item Coding theory (as done now)

\item Graph theory (fleshed out)

\end{enumerate}






\end{document}
