\documentstyle[12pt]{article}
\input{headerhack}
\setlength{\textwidth}{6in}
\setlength{\textheight}{8in}
\setlength{\evensidemargin}{0.25in}
\setlength{\oddsidemargin}{0.25in}
\setlength{\footskip}{.5in}
\setlength{\topmargin}{0.0in}
\renewcommand{\baselinestretch}{1.0}
\setlength{\parskip}{2\parskip plus 2pt minus 1pt}
\begin{document}

\doheading{2}{title}{Last Revised: September, 1993}
\htitle{Introduction to Discrete Applied Mathematics}

We will discuss many areas of discrete mathematics in this course with
emphasis on topics which have direct application in the real world.
Each lecture will emphasize some particular technique or problem and often
we will discuss an algorithm or procedure for efficiently 
realizing this technique. We begin with some mathematical analysis of 
some simply posed questions involving weighing of objects such as coins.
Next we discuss a variety of sorting problems including a highly
efficient algorithm called Batcher's Algorithm. We then move to the subject
of coding theory where we will study three different types of coding problems:
Coding for efficiency of data storage, coding for error correction and coding
for secrecy.

Later in the course will we will deal with an assortment of different
algorithms and some problems in operations research. Among the topics
covered will be the Fast Fourier Transform and how it can be used
to multiply large numbers quickly, algorithms for fast matrix multiplication
and linear programming, as well as some topics in game theory, mathematical
economics and statistics.

Although many kinds of subjects are considered, there are 
common ideas that appear throughout. The mathematical content of this course
involves some linear algebra, probability theory, algebra,
and topics from a variety of other fields. It is hoped that the brief exposures
we give to these topics will motivate you to want to learn more about
them. We will from time to time digress to cover background
material that will be used later in
the course. We will try to go deeply enough into each area
to reach significant and interesting results and not merely give definitions
and easy consequences.

The requirements for this course include handing in weekly homework
assignments, submitting a paper (which we will discuss below), and
taking two quizzes. The content of the quizzes will be made fairly
precise before they take place.

The homework will cover much of the material in detail and represents the
most important part of the grade. The class will cover material quite
rapidly, and it will be almost impossible to assimilate the material 
without reading these notes and doing the homework. Hearing alone is only
one exposure; hearing and reading also are not enough for most people.

Some of the assignments involve writing programs. If you know a programmming
language and have access to a machine to run it, then write and run it.
If you can write in a language but do not have access to a machine
to run it then do what you can. If, on the other hand, you know no language, you
may write in {\em pseudocode} which means you give an explicit
logical description of your procedure in concise English. It's a good
idea to learn enough about a real programming language to write
code even if you do not run it. If you need help with this see 
your instructor, the TA, or fellow students.

The paper, which should be on a topic related in some way to the
course, can have several formats. One is the following: Imagine that you
were to give two lectures to the class on your selected topic. The topic
paper could be a lucid and well organized set of notes on what you
would say. The material for these lectures could be looked up in 
appropriate references. Another format for the paper is to write a 
program to do something related to the course. If you choose to do this
you should explain what you are doing, give an overview including any
comments on certain difficult points and present clear and well-documented
code. If you choose this option you should learn a particular programming 
language. If you have a better idea, then you may pursue it.
The topic for the paper should be selected by midterm in general with an
outline at least by Thanksgiving. Students often choose to use the paper
to fulfill the MIT writing requirement. We will provide a list of 
possible topics in a later section of notes.

Consider it appropriate to discuss homework problems with classmates
and friends (as well as the TA and the lecturer) after you've made
an effort to think about them by yourself for a while.
It is worthwhile for you to develop the habit and ability to 
discuss mathematics with others and discussions can be a valuable way to 
gain insight and familiarity. On the other hand, merely copying papers
circumvents the learning process and is not allowed.  A good way to
proceed is to work out the {\it idea\/} of a solution with classmates,
but then write it up alone, in your own words, without relying on
detailed notes (you should have absorbed the key ideas and internalized
them).  If your final write-up looks too much like your collaborators',
chances are you're leaning on the group too much in the writing-phase 
and thereby missing out on the valuable experience of writing up something
on your own.  (Employers of scientists and engineers regard communication 
skills as having as much importance as mathematical skills, so it literally 
pays to develop these skills.) 

You should get into the habit of including in each assignment you hand in
a list of the people you worked with on that problem.  {\it This
information will in no way be used in grading.}  It is intended
to help you get into the life-long habit of citing sources and
avoiding plagiarism.  (Remember, plagiarism isn't copying, it's
copying without acknowledgment.)

The class notes that are being handed out are taken from lecture notes
of Dan Kleitman's, revised and edited by him and his TAs over the
past couple of years (Debbie Berkovitz, Mike Hawrlycz, Lenore Cowen,
Richard Ehrenborg and Jennifer Huang),
plus Jim Propp and his TAs (Wayne Goddard and David Gupta).
Additional material is taken from presentations made by
guest lecturers Joe Killian and Mark Haiman.

\end{document}

