18.310 General Information (Fall 2007)

18.310 General Information (Fall 2007)


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.

Course Requirements

The requirements for this course include handing in weekly homework assignments, submitting papers (which we will discuss below), and taking two exams (possibly combinations of in class and take-home). 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 such-and-such a reason, so if I had time I'd go back and check my work,'' rather than to bluff. There will be two papers that you must write for this course, the first is a short paper a draft of which is due October 15. It will be returned by November 2 and the final version is due by November 16. The term paper is roughly 10 pages in length on a topic you learn about on your own and is due at the end of the term. It can be, but need not be, an elaboration of the first paper.


Lecture Notes are on the course website: <math.mit.edu/18.310>. There will be revisions and supplements but no text to buy.

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. There are actually several versions of these notes on this website (and on OCW) and they have various sorts of flaws. If one set confuses you, try another and point out the confusion to us. We will try to fix it.

Hearing about material is only way to learn it but it is usually insufficient for retaining knowledge of it. Hearing and reading about it also, is better, but is usually not enough for the student to be able to use the material comfortably.. Doing the homework is needed by most to satisfactorily learn this material. Explaining it to someone else is even more useful for doing so.


Your grade will consist of 1/3 from homework, 1/3 from the exams, and 1/3 from your papers.


There will be 10-12 homework assignments which will cover much of the course material in detail. Some of the assignments will involve your use of a spreadsheet. If you are not familiar with one, we will be happy to show you how to do everything you will need to know to use one. Ask! You should also locate one that is available to you: (Microsoft Excel is one of the best around; but there are many others that are ok; xess, Microsoft works, star office and any other are useable. However they differ slightly in how you copy in them and how you make various instructions) 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 pseudo-code 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.

Consider it appropriate to discuss homework problems with classmates and friends (as well as the TA, instructor, or 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.

Collaboration on assignments is perfectly OK; but DO NOT copy someone else's work in what you hand in. Write whatever you want by yourself. Merely copying papers from others circumvents the learning process and you should avoid it. A good way to proceed is to work out the 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' write-up, 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. If submissions by two students are identical, each will get 0 credit for the assignment. If two submitted spreadsheets are arranged identically on the worksheets, there will be the same result.

Employers of scientists and engineers regard communication skills as having as much importance as mathematical skills, so it definitely pays to develop these skills as far as you can. This year this course is designated a C type course which means that it can be used to satisfy a (written) communications requirement, and also that it includes requirements that you submit one or more papers that are submitted as drafts, reviewed by staff and then final versions submitted. The nature of these requirements will be described below..

If you find you are spending too much time on an assignment then get help. You may talk to friends; or send an email to us asking questions. If you have difficulties with the homework, the TAs, and lecturers are available for help. We might schedule a recitation hour if needed.

You are strongly encouraged to redo and turn in revised versions of homework or exams in which you made serious mistakes. If you do so, you will receive up to half the lost credit that you failed to receive the first time. You have 2 weeks after the graded homeworks are handed back to turn in redone work.

You should get into the habit of including in each assignment you hand in a list of the people you worked with on that assignment. 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 using sources; it is doing so without acknowledgment, or copying entire solutions.)

You may turn in any assignment late IF you request permission to do so before it is due. Such requests can be made in person or by email.

When an assignment involves a spreadsheet, email transmission of the solution is the preferred method of submission.

One important comment: a modern spreadsheet goes on and on in two directions. When you make one it is wise for you to reserve the top few rows for an index, in which you state where each of the parts of your effort appears. Otherwise you run the risk that the grader will not find parts of your work, and you will lose credit for tbem. You can produce the index after you have finished the assignment, but please make an effort to include an index listing your steps and where they are located.


The papers, which should be on topics related in some way to the course, can have several formats.

One possibility is as follows: Imagine that you were to give a lecture to the class on your selected topic. The topic paper could then be a lucid and well organized set of notes on what you would say, written out in detail as it might appear in a book. The writing must be grammatically correct. The material for such lectures could be looked up in appropriate references. The actual writing should be in your own words, after you have assimilated the relevant information which you organize yourself. Again, copying from a source or a fellow student without understanding is not acceptable and can lead to,

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. Results of applying it to some data should probably also be supplied. Again there should be prose written correctly in English. 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 one then you may pursue it. You should try to have a topic chosen and a plan of action by for the initial paper by October 1 and for the final paper by Nov 1.

We hope to supply further information about grammatical rules for dealing with equations soon.

Some possible paper topics, which were used in the dim past are listed. You may choose other topics as you see fit. If you doubt the suitability of a potential topic feel free to ask before you begin.

Actually, the hardest part of writing a paper is choosing a topic. It involves making a decision based on imperfect knowledge; something you will often be called upon to do in your future. Your getting practice at it is very definitely worth while. Once you have one, finding out what you should know about it, digesting that information, and organizing and writing about it are straightforward tasks.