Courses:

The syllabus provides the course's prerequisites, required readings, format, policies, objectives, and expected outcomes.

• Introduction
• Objectives
• Outcomes
• Prerequisites and "Antirequisites"
• Textbooks and Reading
• Weekly Activities (Lectures, Online Reading Problems, Problem Sets)
• Collaboration
• Exams and Grades

This is an introductory course in Discrete Mathematics oriented toward Computer Science and Engineering. The course divides roughly into thirds:

1.Fundamental concepts of Mathematics: definitions, proofs, sets, functions, relations.
2.Discrete structures: modular arithmetic, graphs, state machines, counting.
3.Discrete probability theory.

The goals of the course are summarized in a statement of Course Objectives and Educational Outcomes. A detailed schedule of topic coverage appears in the Course Calendar. The catalogue description of the course also mentions recurrences and generating functions, but these will not be covered this term.

Objectives

On completion of 6.042, students will be able to explain and apply the basic methods of discrete (noncontinuous) mathematics in Computer Science. They will be able to use these methods in subsequent courses in the design and analysis of algorithms, computability theory, software engineering, and computer systems.

In particular, students will be able to:

1. Reason mathematically about basic data types and structures used in computer algorithms and systems; distinguish rigorous definitions and conclusions from merely plausible ones; synthesize elementary proofs, especially proofs by induction.
2. Model and analyze computational processes using analytic and combinatorial methods.
3. Apply principles of discrete probability to model and solve elementary problems of reliability and estimation.
4. Work in small teams to accomplish all the objectives above.

Students will be able to:

1. Use logical notation to define and reason about fundamental mathematical concepts such as sets, relations, functions, and integers.
2. Evaluate elementary mathematical arguments and identify fallacious reasoning (not just fallacious conclusions).
3. Synthesize induction hypotheses and simple induction proofs.
4. Apply graph theory models of data structures and state machines to solve problems of connectivity and constraint satisfaction, e.g., scheduling.
5. Apply the method of invariants and well-founded ordering to prove correctness and termination of processes and state machines.
6. Derive closed-form and asymptotic expressions from series and recurrences for growth rates of processes.
7. Calculate numbers of possible outcomes of elementary combinatorial processes such as permutations and combinations.
8. Calculate probabilities and discrete distributions for simple combinatorial processes; calculate means and variances.
9. Solve problems of estimation and error tolerance by applying theorems on deviation from the mean.
10. Problem solve and study in a small team with fellow students.

The prerequisite for the course is 18.01. The MIT catalogue lists 18.02, but this is incorrect. You should be familiar with sequences and series, limits, and integration and differentiation of univariate functions. Most of you are already familiar with logical notation, elementary set theory, and elementary facts about numbers. To make sure that you are up to speed on this material, you should look over the background reading assignment for Problem Set 1 during the first week of the course.
If you have taken 18.063 or 18.310 you should not take this course. 18.063 may be substituted for 6.042 in the EECS M.Eng. and S.B. requirements. For such students interested in learning probability, we recommend 6.041 or 18.440.

The required texts for the course are:

• Course Notes, which will be posted on the website each week
• Rosen, Kenneth H. Discrete Mathematics and its Applications. 4th ed. New York, NY: McGraw-Hill, Inc., 1999. ISBN: 0072899050. There is a website for this book with additional problems and information.

The required reading will be assigned from both the Rosen text and the Course Notes; readings for the last third of the course on Probability Theory will be mainly from the Notes.

A supplementary text that may be useful for study of basic proof techniques is

Velleman, Daniel J. How to prove it: A Structured Approach. Cambridge, England: Cambridge University Press, 1994. ISBN: 0521441161.
However, in contrast to past terms, the Velleman text is not required, and no reading will be assigned from it.

This term the weekly schedule will usually be:

• Monday: Lecture & Group Problem Solving.
  Previous week problem set due at beginning of lecture. 
• Wednesday: Lecture & Group Problem Solving.
  Current week Online Reading Problems due by 11am. 
• Friday: Lecture & Group Problem Solving

This schedule gets perturbed by holidays and quizzes. A detailed schedule including daily lecture topics is in the Course Calendar.

Each week there will be three one-and-a-half hour class meetings in which parts of lectures will be interleaved with group problem-solving. Monday's lecture will present an overview of the material. The idea is to get some familiarity with the basic concepts of that week and then to tackle more challenging concepts and problems in detail during the Wednesday and Friday meetings.

There will be a reading assignment and simple online reading problems due before Wednesday class. Wednesday and Friday meetings will be devoted to explaining the reading material more deeply and solving interesting problems, with students working in groups of typical size six. A TA will act as a group coach, providing hints and explanations as requested. We believe that the team problem solving activity is a key learning experience. In-class participation counts for 25% of the grade and will be graded mainly on degree of active, prepared participation, rather than problem-solving success.

Online Reading Problems will be simple problems that will be easy to do after a pass at the reading assignments. They will be due Wednesday morning by 11am along with a standard question on the reading:
"Indicate one or more of the following in at most three sentences,

1. which passage in the reading you found most difficult,
2. which passage you found most surprising,
3. what topic or example you would like to have discussed in Wednesday lecture."

We will try to tailor part of the Wednesday and Friday lectures based on email responses to the reading question.

There will be eleven (11) weekly Problem Sets. Solutions to the problem sets will be posted two days after the due date (except for Quiz weeks, when they are posted right after the due time).

The last page of each problem set has a cover page for use when you submit the problem set. Complete the information called for on the cover page and attach it as the first page of your submission. Be sure to complete the full collaboration statement of the form:

"I worked alone and only with course materials",
or

"I collaborated on this assignment with (students in class),
got help from (people other than collaborators and course staff),
and referred to (citations to texts and material other than the class texts, handouts and last term's bible)".

No problem set will be given a grade until it has a collaboration statement.

Late Policy: Problem sets turned in 30 minutes past the due time will be considered late. Late problem sets should be turned in to your TA by arrangement with him or her. Problem sets turned in within 24 hours of the due time will be penalized 10%; those turned in 24 to 48 hours late will be penalized 20%. Problem sets more than two days late may not get graded at all. If you are unable to complete a homework by the date assigned, please talk to your TA in advance.

Pset Grading: Submissions which are unduly hard to follow (or illegible) may be penalized even if the solutions are "correct". If you are unhappy with the way that your homework has been graded, first see your TA. If you're still unhappy after that, feel free to contact a Lecturer.

We encourage you to collaborate on homework as you do on in-class problems. Study groups can be an excellent means to master course material (besides, they can be fun and a good way to make friends.) However, you must write up solutions on your own, neither copying solutions nor providing solutions to be copied. If you do collaborate on homework, you must cite, in your written solution, all of your collaborators. Also, if you use sources beyond the course materials in one of your solutions, e.g., an "expert" consultant, another text, or material other than the text, handouts and last term's bible, be sure to include a proper scholarly citation of the source.

We discourage, but do not forbid, use of materials from terms prior to Spring 2002 to which a student may have access. Use of such material requires a proper scholarly citation; omission of such citation will be taken as a priori evidence of plagiarism subject to serious penalty.

Plagiarism, cheating, and similar anti-intellectual behavior are serious violations of academic ethics and will be correspondingly penalized. If you are concerned about a possible violation of this kind, please talk with your TA and/or a Lecturer. We understand the pressure that students may experience while at MIT, and we will try to help as best as we can. It is better if you take the initiative to contact us in such cases, rather than vice-versa.

Quizzes and Final

There will be two quizzes and a regular three-hour final. Quizzes will be held in the evening; one lecture will be cancelled and there will be an optional quiz review held during class time.

Problem Sets
There will be 11 problem sets, each about equal weight. Your lowest grade among the 11 will be ignored.

strong>GradesGrades for the course will be based on the following weighting:

In-class Participation: 20%
Online Reading Problems: 5%
Problem Sets: 30%
Quizzes (2): 25% (12% 13%)
Final: 20%