Courses:

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 papers (which we will discuss below), and taking two exams (a 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 in Ses #L16. It will be returned by Ses #L24 and the final version is due by Ses #L29. 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.

There is no text to buy for this course. We will rely on the lecture notes on the course Web site.

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 about material is only one 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.

There will be 10 homework assignments which will cover much of the course material in detail. Some of the assignments will involve your use of a spreadsheet. You should 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). Then go through Chapter 0 of 18.013A which is on the OCW Web site. 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.

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 them. 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.

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.

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

The two term 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 serious consequences.

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 Ses #L11 and for the final paper by Ses #L24.

Some possible paper topics, which were used in the dim past are listed projects page. 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.