MIT 6.042/18.062J Mathematics for Computer Science

Fall 2010


Most of this site is now password protected, but the material is available on the MIT OCW site.

  • Final Notes
    • This quiz is closed book, but you may have two 8.5"x11" sheets with notes in your own handwriting on both sides.
    • Calculators are not allowed.
    • You may assume all of the results presented in class.
    • Please show your work. Partial credit cannot be given for a wrong answer if your work isn't shown.
    • Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. Please keep your entire answer to a problem on that problem's page.
    • Be neat and write legibly. You will be graded not only on the correctness of your answers, but also on the clarity with which you express them.
    • If you get stuck on a problem, move on to others. The problems are not arranged in order of difficulty.
    • The exam ends at 4:30 PM.
  • 2004 final exam and solutions are now up!
  • 2006 final exam and solutions are now up!
  • Rec 23 (Dressing and Tranches), Problems and Notes
  • Problem Set 12 Solutions
  • The 2008 final exam and solutions have been released for practice.
  • Course evaluation site
  • Rec 22, Problems and Notes
  • Rec 21, Problems and Notes
  • Rec 20, Problems and Notes
  • Problem Set 11 Solutions
  • Problem Set 12 due 7pm Friday, 12/3/10. The corresponding reading is Chapter 17 this week, and Chapter 18 and Sections 19.1, 19.5.1-19.5.2 next week.
  • Problem Set 10 Solutions
  • Problem Set 11 (REVISED) due 7pm Monday.
  • Rec 19 (Bayes', DNA, Immortals), Problems and Notes
  • Rec 18 (Nerditosis, Barglesnort), Problems and Notes
  • Read Ch 15 & 16
  • Drop day tomorrow! (November 17, 2010)
  • Stellar site
  • Recitations Friday, 11/12, are cancelled! Huzzah!
  • Rec 17 (Game Trees, Let's Make A Deal), and Rec 17 Notes
  • Problem Set 9 Solutions
  • Problem Set 8 Solutions
  • Problem Set 10 is now posted!
  • Rec 16 (Combinatorial Proof), and Rec 16 Notes
  • Rec 15 (BOOKKEEPER), Rec 15 Notes
  • Rec 14, Rec 14 Notes
  • Problem Set 9, aka Counting, Counting, Counting
  • Problem Set 8 was accidentally taken down, but now it's back up! Problem 2b has been updated (to be clear, as this announcement was so late, the graders will be instructed to go very easy on this problem). And it's still due on Tuesday at 7pm.
  • Midterm, and Midterm Solutions
  • Problem Set 7 Solutions
  • A revised copy of Problem Set 7 is up.
  • Rec 12 and Rec 12 notes have been updated to be clearer.
  • Problem 6 Solutions
  • Midterm Practice Problems, and Solutions
  • Rec 13, Rec 13 Notes
  • Rec 12, Rec 12 Notes
  • Midterm is closed book -- no calculators
  • You may bring one 2-sided, 8.5x11 crib sheet in your original handwriting.
  • Problem Set 7 is out. Seeing as the midterm is next week, it may be prudent to start (and finish) the pset as early as possible, to allow yourselves time to study for the exam.
  • The corresponding reading is Chapter 9.
  • Rec 11, Rec 11 Notes
  • PS6, problem 3 clarification: the partial orders are weak partial orders. Problem set 6 has been updated to reflect this.
  • The point subtotals for Problem Set 6 problem parts now all sum to 20 points, as they should.
  • Oscar's office hours have been updated on the right.
  • A student pointed out that problem 2d on Problem Set 6 is ill-defined if N is taken to include 0. For the specific problem, N is the set {1, 2, 3, ...}. The problem set has been updated accordingly with this clarification.
  • Problem Set 5 Solutions
  • Rec 10, Rec 10 Notes
  • Let us know ASAP if you have a conflict with the midterm.
  • Nick's office hours have been updated on the right.
  • Problem Set 6
  • Rec 9, Rec 9 Notes
  • Problem Set 5 DUE ON TUESDAY (as Columbus Day is a holiday).
  • Rec 8, Rec 8 Notes
  • Problem Set 5, The corresponding reading for problem set 5 is Chapter 5.4-5.7, 6.1-6.2.
  • Problem Set 4 Solutions
  • Rec 6, Rec 6 Notes, Rec 7, and Rec 7 Notes
  • Update to problem set: n in problem 5 refers to the number of boys, or the number of girls, for a total of 2n people. File has been updated.
  • Updated problem set: added a possibly helpful definition to problem 1.
  • Matching Algorithm Handout
  • Martyna's office hours updated--check right.
  • Final ice-cream study session time updated
  • Problem set 4 points now add up to 100. Link updated.
  • Final time and location updated (on the right).
  • Problem Set 4 The corresponding reading for problem set 4 is Chapter 5, sections 0 through 3, 5.2.2 optional.
  • Problem Set 3 Solutions
  • Rec 5, and Rec 5 Notes
  • From now on, office hours will end strictly at 6PM on Mondays. Plan ahead!
  • Stav has office hours on Thursdays from 5-6:30pm in 24-316. The times on the right have been updated accordingly.
  • Darren's 3PM recitation is now in 34-303!
  • Rec 4, and Rec 4 Solutions
  • Problem Set 2 Solutions.
  • Problem Set 3 is posted here. The corresponding reading for problem set 3 is Chapter 4.
  • Rec 3, and Rec 3 Notes.
  • Top 10 (bad) Proof Techniques
  • Recitation 2, and Recitation 2 Solutions.
  • Problem Set 1 solutions are posted here!
  • Problem Set 2 is posted here, and will be due Monday at 7pm. The corresponding reading for problem set 2 is Chapter 3 (sec 3.5 is optional).
  • 10 point bonus on Problem Set 2 for seeing your TA during office hours. If you absolutely can't make the office hours your TA is hosting, then let him/her know, go to another office hours, and check in with an on-duty TA.
  • See Marten if you are not scheduled in a recitation (or a TA).
  • In the future, Nick's recitations are now in 24-307, for 9am and 10am.
  • Stav's office hours have been updated! See under Staff and Office Hours.
  • Special one-night engagement! Martyna is offering office hours at 7:30-8:30pm tonight outside 32-123.
  • Welcome to the Fall 2010 edition of 6.042! Check out the course info.
  • Here's a (roughly) final version of the textbook (7 MB).
  • Office hours are on the right
  • Recitations:
  • Problem set 1 is out! The reading for problem set 1 is chapters 1 and 2 of the textbook.
  • Recitation 1, and Recitation 1 Solutions

Times and Locations

Lecture: TR 2.30-4, 32-123
Recitation: WF
Midterm ice-cream study session: Tue, Oct 26th, 7-9pm 32-G5 Lounge
Midterm Wed, Oct 27th, 7:30-9:30 pm Walker (50-340)
Midterm makeup Thu, Oct 28th, 7:30-9:30pm 36-153
Final  ice-cream study session: Mon, Dec 13th, 7-9pm 32-G5 Lounge
Final: Tue, Dec 14th, 1:30-4:30pm Johnson Track

Staff and Office Hours

Tom Leighton

TR, 4:30-6pm, or by appt

Marten van Dijk
By appointment only
Stav Braun
sbraun at
M, 4:30-6pm
Th, 5-6:30pm
David Chen
davidc_9 at
M, 3-6pm
Nick Joliat
njoliat at
M, 3-4:30pm
F 4-5:30pm
Martyna Jozwiak
martynaj at
Th, 7:30-8:30pm
M, 3-5pm
Oscar Moll
orm at
Sat, 5-6:30pm
Sun, 6-7:30pm
Darren Yin
darreny at
Sun, 6-9pm

Course Overview

Welcome to 6.042! In this course, we'll teach you some mathematics that we think you'll find useful in your study of computer science. 6.042 covers applications of Discrete Mathematics to Computer Science. The only prerequisite is 18.01. If you have already taken 18.310 or 6.046, then you should not take 6.042. There are 90-minute lectures on Tuesday and Thursday in 32-123. There are also mandatory 1-hour recitations on Wednesday and Friday focused on solving problems in small groups.


The text is Mathematics for Computer Science. A draft copy is available here. Reading will be assigned each week with the problem sets.

Problem Sets

There is a problem set each week, for a total of 12. Problem sets are generally released on Tuesday, due the following Monday evening at 7 PM in the locked boxes at the elevator lobby in 32-G5 and returned in recitation on Friday. Be neat! Graders may deduct for sloppiness. Late homework is generally not accepted, but talk to your recitation instructor if a special circumstance arises. Please do not refer to course materials from previous terms. You may work with other students, but your writeup must be entirely your own. On the top of your homework, list:

  • all collaborators, other than course staff
  • all written sources that you consulted, other than the text and course handouts from this term

If you had no collaborators and consulted no written sources, then write, "I worked alone." Homework without a collaboration statement will not be graded.


There is one midterm exam on Wednesday, October 27, from 7:30-9:30pm, and there is a 3-hour final exam during finals week.


We compute a percentage score based on your coursework and then assign a letter grade as follows:

A88.0 - 100%
B75.0 - 87.9%
C60.0 - 74.9%
D50.0 - 59.9%
Fbelow 50.0%

Your percentage score is the weighted average of your scores in four areas: homework, recitation, midterm, and the final 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 skip part of recitation (that includes falling asleep!) 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%)
We'll cut 10% off the weight of your weakest exam. 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!

Copyright © 2010 M. van Dijk & F.T. Leighton. All rights reserved. Last modified: Wed Sep 08 02:42:21 EDT 2010