18.310 Introduction

We will discuss many areas of discrete mathematics in this course with

emphasis on topics that 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 algorithms that are used for sorting data.

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 or transmission, 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 linear programming

and solution to network-flow problems, 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, combinatorics

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 (open book, open notebook) exams at least one of which will be a take home exam.

The content of the exams will be made fairly precise before they take place. Your grade on the exam will reflect the degree to which you demonstrate

an understanding of the material, so it pays to be honest; it's better to say ... This answer looks wrong for thus-and-such a reason, so if I had time I'd go back and check my work,'' rather than to bluff.

The homework will cover much of the material in detail and represents the

At least one third of your final grade. The paper will represent another third and the exams the rest.

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.

If you have difficulties with the homework either the TA or the lecturer are available for help. We also expect to schedule a recitation hour at which the TA can help you.

Some of the assignments will involve use of the spreadsheet. If you are not familiar with one, you may familiarize yourself with one by first locating one: (Microsoft excel is the best around; but there are many others that are ok; xess, Microsoft works, star office also are useable, though you have to figure out how to copy conveniently in them.) And then going through Chapter 0 of 18.013A which is on the website reachable by math.mit.edu/~djk. You will then be armed to do any of these assignments.

Some assignments may involve writing programs. If you know a programming 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 the lecturer, 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 a 90-minute 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 for a term paper (for instance, if you

think that one of the chapters in these Notes does a bad job of

explaining things, and that you could do a better job!), then you may pursue

it. The topic for the paper should be selected by midterm. You should try to have a topic chosen and a plan of action by October 31. Students often choose to

use the paper to fulfill the MIT writing requirement.

We have prepared a handout and will create a new one listing some possible paper topics, which represent topics chosen in the past.

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 from others circumvents the learning process and you should avoid it. 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

(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.)

Very many people have contributed to these notes in some way or other over the years, including Curtis Greene, Mark Haiman, Joe Killian, Debbie Berkovitz, Mike Hawrilycz, Lenore Cowen, Richard Ehrenborg, Jennifer Huang, Jim Propp, Wayne Goddard, David Gupta, Miklos Bona, Satomi Okazaki, and Esther Jesurum, and several current graduate students.