Syllabus

Course Meeting Times

Lectures: 3 sessions / week, 1.5 hours / session

Contents

• Introduction
• Prerequisites
• Course Schedule
• Team Problem Solving
• Problem Sets
• Online Tutor Problems
• Collaboration and Outside Sources
• Exams and Grades
• Course Objectives and Outcomes

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 calendar section.

Prerequisites

The prerequisite for the course is 18.01. You should be familiar with sequences and series, limits, and integration and differentiation of univariate functions.

Course Schedule

Lecture/Team Problem-solving Sessions

Lectures will be interleaved with team problem-solving sessions and demos. TA's and lecturers will act as coach/facilitators during problem-solving sessions. Lecture/Problem-solving session attendance is mandatory. There are no separate recitations.

Reading and Problem Sets

Reading from Class Notes and Problem Sets are generally assigned on Mondays, with Problem Sets due the following Monday, but this varies with holidays and quizzes. See the calendar section for exact schedule. There is no textbook.

Short Online Problems and Email Comments

These are generally assigned on Monday and due Wednesdays by 1pm.

Team Problem Solving

Approximately half the class meeting time will be devoted to problem-solving in teams of 5-7 students. A TA will act as a team coach, providing hints and explanations as requested. We believe that the team problem solving activity is a key learning experience. Problem-solving participation counts for 25% of the grade and will be graded mainly on degree of active, prepared participation, rather than problem-solving success.

Problem Sets

Problem Sets are normally due at the beginning of Monday lecture.

Doing the problem sets is, for most students, the best way to master the course material. Problem sets will count for up to 30% of the final grade. However, there is no penalty for incorrect or omitted problems: any credit you miss on problems will be reallocated to your quizzes and/or final. So problem sets enable you to lock in partial credit towards an "A", but cannot harm your grade.

Solutions to the problem sets will be provided immediately after the due date. Late problem sets will not be accepted.

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 on the cover page:

"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 sources other than the class material from this term and Fall '02)".

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

Problem Set Grading

Submissions which are unduly hard to follow (or illegible) will get little credit 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.

Online Tutor Problems

Online Tutor Problems consist of straightforward questions about the assigned reading and should take about 20 minutes after you finish the reading. A standard question on the reading appears every week and an email answer is required.

*Required* Comments for Reading:

Cite a passage in the reading - including its page number - and explain, in at most three sentences, why you found it

1. Most difficult, or
2. Most surprising, or
3. Would like to have discussed more fully it in the next lecture.

Most weeks, the Tutor Problems and Reading Comments will be due by 11am before Wednesday class. We try to slant the lectures in response to student email on the reading.

Collaboration and Outside Sources

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 course text and handouts and the Fall '02 course materials published on OpenCourseWare, be sure to include a proper scholarly citation of the source.

We discourage, but do not forbid, use of materials from prior terms other than Fall '02 to which a student may have access. We repeat, however, that use of such material requires a proper scholarly citation; omission of such citation will be taken as a priori evidence of plagiarism.

Plagiarism, cheating, and similar anti-intellectual behavior are serious violations of academic ethics and will be penalized. However, we understand the pressure that students may experience while at MIT, and we try to respond to such incidents in a balanced way.

If you are concerned about a possible violation of this kind, please talk with your TA and/or a Lecturer. It is better if you take the initiative to contact us in such cases, rather than vice-versa.

Exams and Grades

There will be two in-class quizzes and a regular three-hour final exam.

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

Course Objectives and Outcomes

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 (such as numbers, sets, graphs, and trees) 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 calculate probabilities and expectations of simple random processes.
4. Work in small teams to accomplish all the objectives above.

Learning Outcomes

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. Prove elementary properties of modular arithmetic and explain their applications in Computer Science, for example, in cryptography and hashing algorithms.
5. Apply graph theory models of data structures and state machines to solve problems of connectivity and constraint satisfaction, for example, scheduling.
6. Apply the method of invariants and well-founded ordering to prove correctness and termination of processes and state machines.
7. Derive closed-form and asymptotic expressions from series and recurrences for growth rates of processes.
8. Calculate numbers of possible outcomes of elementary combinatorial processes such as permutations and combinations.
9. Calculate probabilities and discrete distributions for simple combinatorial processes; calculate expectations.
10. Problem solve and study in a small team with fellow students.