\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\input{macros-course}

\def\cent{{\not\!\mathrm{c}}}
\renewcommand{\implies}{\longrightarrow}


%\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}

\begin{document}

\handout{objectives}{Objectives and Outcomes}{September 7, 2000}

\section*{Course Objectives}

This course introduces students to methods of Discrete (noncontinuous)
Mathematics in Computer Science and lays the foundation for subsequent
courses in Algorithms, Software Engineering, Computability Theory, and
Systems.

Upon completion of 6.042, students will be able to
\begin{enumerate}

\item \label{defs and proofs}
recognize and explain precise mathematical definitions, and to recognize,
explain, and synthesize elementary proofs in Discrete Mathematics,
especially proofs by induction.  They will be skillful at distinguishing
rigorously proven conclusions from merely plausible ones.

\item \label{optimization}
apply methods from Mathematical Logic, Graph Theory, Elementary Number
Theory, and Combinatorics to model and solve discrete optimization
problems.

\item \label{data and algorithms}
use these methods to model computational systems, and to verify
computational behavior of elementary data structures, algorithms, and
state machines.

\item \label{probability}
apply principles of discrete probability to model and solve elementary
problems of reliability and estimation.

\item \label{teams} work in a small team to accomplish all the objectives
above.

\end{enumerate}

\section*{Course Outcomes}
Students will be able to:
\begin{enumerate}

\item \label{soundness}  evaluate the soundness of elementary mathematical
arguments, identify fallacious \emph{reasoning} (not just fallacious
conclusions), and synthesize corrections to proofs.

\item \label{proofs} synthesize induction hypotheses and simple proofs in
discrete mathematics using the terminology of elementary mathematical
logic.

\item \label{combinatorics} apply methods of discrete mathematics to model
and solve elementary combinatorial optimization problems, in particular

   \begin{enumerate}

   \item \label{graph models} define and prove basic properties of
         finite graphs such as connectedness, colorability, acylicity.
         Use graphs to model data structures and state machines.

   \item \label{solve graphs} apply graph theory to solve elementary
         problems of scheduling and connectivity.

   \item \label{arithmetic} define and prove basic properties of prime
        numbers and modular arithmetic; calculate GCD's and evaluate
        arithmetic expressions in modular arithmetic.

   \item \label{closed forms} model current value of future
        income, population growth, and computational resource requirements
        using series and recurrences, and then derive closed-form
        solutions.

   \item \label{counting} count combinations and permutations of outcomes
   of discrete experiments such as dice rolls.

   \end{enumerate}

\item \label{correctness} apply principles of logic and discrete
mathematics to analyze, verify, and synthesize elementary algorithms and
state machines, in particular

   \begin{enumerate}

           \item \label{invariants} apply the method of invariants and
           well-founded ordering to prove correctness and termination of
           algorithms and state machines.

           \item \label{Big-O} use asymptotic notation to describe time
           and space complexity of algorithms.

   \end{enumerate}


\item
\label{calculate probability} apply principles of discrete
probability to model and solve elementary problems of reliability and
risk, in particular

   \begin{enumerate}

   \item \label{conditional probability} calculate probabilities and
   conditional probabilities of combinatorial experiments such as dice
   rolls.

   \item \label{mean-var} calculate means and variances for simple
   combinatorial experiments and for binomial, geometric, and similar
   discrete distributions.

   \item \label{estimation} state and determine applicability of the Weak
   Law of Large Numbers and similar estimates of deviation from the mean
   to problems of estimation and error tolerance.

   \end{enumerate}


\item \label{student teams} discuss and solve problems with fellow
students in a small team, and prepare and orally present solutions to
short problems.


\end{enumerate}

\iffalse

\begin{center}
Objectives
\end{center}

\ref{defs and proofs} Proofs, \ref{optimization} Combinatorics,
\ref{data and algorithms} Data and algorithms, \ref{probability}
Probability, \ref{teams} Teams.


\begin{center}
Outcomes: reflected Objectives
\end{center}

\ref{soundness} Recognize proofs: \ref{defs and proofs}

\ref{proofs} Synthesize proofs: \ref{defs and proofs}

\ref{graph models}: \ref{defs and proofs}, \ref{optimization}, \ref{data and algorithms}

\ref{solve graphs}: \ref{optimization}, \ref{data and algorithms}

\ref{arithmetic}: \ref{defs and proofs}, \ref{data and algorithms}

\ref{closed forms}: \ref{data and algorithms}, \ref{optimization}

\ref{counting}: \ref{optimization}, \ref{probability}, \ref{data and algorithms}

\ref{invariants}: \ref{defs and proofs}, \ref{data and algorithms}

\ref{Big-O}: \ref{data and algorithms}, \ref{optimization}

\ref{calculate probability}: \ref{probability}

\ref{student teams}: \ref{teams}
\fi


\end{document}
