This course covers elementary discrete mathematics for computer science and engineering. It emphasizes mathematical definitions and proofs as well as applicable methods. Topics include formal logic notation, proof methods; induction, well-ordering; sets, relations; elementary graph theory; integer congruences; asymptotic notation and growth of functions; permutations and combinations, counting principles; discrete probability. Further selected topics may also be covered, such as recursive definition and structural induction; state machines and invariants; recurrences; generating functions.
Lectures: 2 sessions / week, 1.5 hours / session
Recitations: 2 sessions / week, 1 hour / session
The text is Mathematics for Computer Science, available in the Readings section. Reading will be assigned each week with the problem sets.
There are 12 problem sets. Typically, a problem set is due a week after it is assigned. There are two exams: one 2-hour evening midterm, and a 3-hour final during finals week.
You are welcome to work with other students on homework, but your writeup must be entirely your own. Please do not refer to course materials from previous terms. On the top of your homework, list:
If you had no collaborators and consulted no written sources, then write, "I worked alone." Homework without a collaboration statement will not be graded. Collaboration on exams is not allowed. If you somehow violate the collaboration policy, your best option is to tell us before we notice. Mistakes you confess are forgivable.
We compute a percentage score based on your coursework and then assign a letter grade as follows:
A 88.0 – 100%
B 75.0 – 87.9%
C 60.0 – 74.9%
D 50.0 – 59.9%
F below 50%
Your percentage score is the weighted average of your scores in four areas: homework, recitation, midterm and the final exam. The weights listed below total 110%, but we'll cut 10% off the weight of your weakest exam. Scores in the four individual areas are determined as follows:
Homework (30%) We drop your lowest score. We may normalize an entire recitation section upward, if necessary to compensate for variations in grading standards.
Recitation (20%) Each recitation is worth 0, 1, or 2 points. If you attend for the full period and work constructively with your team, then you get 2 points. If you miss part of recitation or glaringly fail to work constructively with your team, then you get 1 point. If you are absent, you get 0 points. We drop your two lowest recitation scores.
Midterm (25%), Final (35%) If the class median on an exam is below 75% (which is typical), then we normalize all scores upward so that the median is 75%. We normalize by adding a fixed number of points to every score. Scores are not capped at 100%. If the median on an exam is above 75%, fantastic!
We want everyone to get the best possible grade within the bounds of fairness. There is no curve; in principle, everyone could get an A. Here are some suggestions on how you can do well:
Good luck and we hope you enjoy the class!
The mission of MIT is to advance knowledge and educate students in science, technology, and other areas of scholarship that will best serve the nation and the world in the 21st century.
The Institute is committed to generating, disseminating, and preserving knowledge, and to working with others to bring this knowledge to bear on the world's great challenges. MIT is dedicated to providing its students with an education that combines rigorous academic study and the excitement of discovery with the support and intellectual stimulation of a diverse campus community. We seek to develop in each member of the MIT community the ability and passion to work wisely, creatively, and effectively for the betterment of humankind.