Course Overview

Contents

• Introduction
• Course Schedule
• Course Website
• Prerequisites and "Antirequisites"
• Textbooks and Reading
• Weekly Schedule (Lectures, Online Reading Problems, Problem Sets)
• Collaboration
• Exams and Grades

Introduction

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.

Course Schedule

• MWF 2:30--4:00 in 26-152, the TEAL studio classroom, and again
• MWF 4:00--5:30 in 36-156.

6.042 emphasizes group problem solving, and the new TEAL room offers an important opportunity to support this style. There will be no separate tutorials/recitations; instead group problem solving will be interleaved with mini-lectures.

Course Website

The class has a comprehensive web site:

http://theory.lcs.mit.edu/classes/6.042

All course information such as course notes, problem sets, staff contact information, mailing list information, and announcements are available on this website. We will not be distributing any paper handouts besides in-class problems and quizzes. Course notes, problem sets and solutions, etc., will be posted on the course Handouts page. It is always worth checking the website for corrections and announcements before starting problem sets.

Prerequisites and "Antirequisites"

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.

Textbooks and Reading

The required texts for the course are:

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

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

Daniel J. Velleman. How to prove it: A Structured Approach, Cambridge University Press, Cambridge, England, 1994.

However, in contrast to past terms, the Velleman text is not required, and no reading will be assigned from it.

Weekly Schedule

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

Lectures and Group Problem Solving

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

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

Problem Sets

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.

Collaboration

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.

Exams and Grades

Quizzes and Final

• Quiz 1: Oct 10 7:30-9:30 i 54-100
• Quiz 2: Nov 14 7:30-9:30 in 34-101
• Final Exam: Wednesday, December 18, 9AM--NOON, 34-101.

Problem Sets

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

Grades

Grades for the course will be based on the following weighting:

Questions, Suggestions, and Complaints

You can send email to 6042-meyer@theory.lcs.mit.edu and several other choices on the contact page.

This document last modified Monday, 03-Feb-2003 18:01:50 EST

For website issues, contact the 6042-webmaster-fall02@theory.lcs.mit.edu Copyright © 2002, Prof. Albert R. Meyer and Dr. Radhika Nagpal , All rights reserved