Help is available from the following people:
| Office Hours | Office | Phone | ||
| Prof. Tom Leighton | Wed 2:30-3:30pm | 2-377 | x3-3662 | ftl@math.mit.edu |
| NE43-328 | x3-5876 | |||
| Dr. Santosh Vempala | Mon 2:00-4:00pm | 2-335 | x3-7905 | vempala@theory.lcs.mit.edu |
| NE43-374 | x3-7553 | |||
| Alex Duran | Mon 2:00-5:00pm | NE43-338 | x3-7583 | amsduran@mit.edu |
| David Finberg | Mon 5:00-7:00pm | 2-342 | x3-4102 | dfinberg@math.mit.edu |
| Russell Schwartz | Mon 5:00-8:00pm | NE43-336 | x3-5971 | rsschwar@mit.edu |
| Gunnar Hoest | Tue 11:00am-2:00pm | NE43-370 | x3-6097 | gunnar@theory.lcs.mit.edu |
| Eric Lehman | NE43-336 | x3-5971 | e_lehman@mit.edu |
Contact Eric Lehman (e_lehman@mit.edu) for help with this web site and in obtaining handouts.
All tutorials are on Friday.
| Gunnar | 10-12 | 24-320 |
| 1-3 | 24-320 | |
| 3-5 | 24-310 | |
| Russell | 8-10 | 24-310 |
| 1-3 | 24-322 | |
| 3-5 | 24-322 | |
| David | 10-12 | 36-372 |
| 1-3 | 24-316 | |
| 3-5 | 24-316 | |
| Alex | 10-12 | 2-142 |
| 2-4 | 24-402 | |
| 4-6 | 24-402 | |
| Santosh | 9-11 | 2-338 |
| 1-3 | 2-338 |
Lecture notes will be posted here a few days after each class.
The only official prerequisite for the course is 18.01. Students should be familiar with sequences and series, limits, and integration and differentiation of univariate functions.
Most students will already be familiar with logical notation, elementary set theory, and elementary facts about numbers. In order to make sure that everyone is sufficiently familiar with this material, each student should read sections 1.1--1.5 and 2.3 of Discrete Mathematics and Its Applications during the first week of the course.
Students who have taken 18.063, 18.310, or 6.046 should not take this course. To learn probability, we recommend these students instead take 6.041, 18.440, 18.313, or 18.05. Students can substitute 18.063 for 6.042 in the EECS department M.Eng. and S.B. requirements.
Lectures will be held Tuesdays and Thursdays from 2:30 to 4:00 in Room 6-120. Attendance in lectures is highly recommended. Lecture notes from past years are available on the web, but the course is being revised this term and there will be substantial changes in the lecture material. Lecture notes for this term will be handed out in time for exams, but not in time to help with homework. So to keep up, students will need to attend lecture.
All students must attend a two-hour tutorial every Friday. ATTENDANCE WILL BE TAKEN. Each tutorial will consist of approximately twelve students, so there will be a good opportunity to ask questions and to interact with the staff. The emphasis of the tutorials is on techniques for solving problems, although new material will occasionally be presented. During the final hour or so, each individual tutorial group will be assigned a problem to solve as a group. The group is expected to work together as a team in solving the problem. The TA will then ask one member from one or more groups to present the solutions to the entire tutorial. If the presentation is not satisfactory, the TA may ask the entire group to write up the solutions.
In order to keep your handouts organized, get a loose-leaf notebook for the course. All handouts will be on standard three-hole punched paper and will be numbered consecutively. Handouts will be available in a file cabinet outside room NE43-309.
Handouts in postscript format can be obtained through the class web site at http://theory.lcs.mit.edu/classes/6.042. (Hey, here you are!) You can also reach them by anonymous FTP at theory.lcs.mit.edu in the directory pub/classes/6.042/fall97.
The required textbooks for the course are Discrete Mathematics and its Applications by Kenneth H. Rosen (Third Edition, McGraw-Hill, Inc., 1995) and The Nuts and Bolts of Proofs by Cupillari. The recommended textbook is The Essentials of Probability by Lutfiyya.
The Nuts and Bolts of Proofs SHOULD BE READ COVER-TO-COVER BY EVERY STUDENT DURING THE FIRST 2 WEEKS OF THE COURSE. Discrete Mathematics and its Applications will serve as a useful reference for most of the course. The Essentials of Probability will be useful near the end of the course. It does a good job of covering the later material (probability).
All texts will be available at The Coop under the heading 18.062.
Problem sets will be assigned on a weekly basis. They will usually be issued in lecture on Tuesday to cover that week's lectures and tutorial, and then due in lecture on Tuesday the following week. PROBLEM SETS WILL BE COLLECTED AT THE START OF CLASS. Any problem sets turned in past 2:35pm will be considered late. LATE PROBLEM SETS WILL BE PENALIZED 20% OF THE FINAL GRADE.
A PROBLEM SET WILL NOT BE ACCEPTED IF IT IS MORE THAN 2 DAYS LATE.
Solutions to the problem sets will usually be distributed in the lecture or tutorial following the one in which they were due. Please clearly mark your problem sets with (1) your name, (2) the date, (3) problem numbers, and (4) the name of your TA. Also, ACKNOWLEDGE ANY PERSONS YOU COLLABORATED WITH ON THE PROBLEM SETS. Your name should appear on every page.
Try to be as clear and precise as possible in your written solutions. Understandability of the solution is as desirable as correctness. Sloppy answers will be at a disadvantage and will receive fewer points even if they are correct. Do not use red ink to write up your homework, because red is our color for grading.
If you are unable to complete a homework by the date assigned, please talk to your TA in advance. If you are unhappy with the way that your homework has been graded, see your TA. Questions, suggestions, and complaints will be welcomed by the course staff.
When turning in a problem set, be sure to place it in the box that is labelled with the name of your tutorial instructor.
You are encouraged to collaborate in solving the homeworks. Study groups provide an excellent means to master the material of the course. You must write up solutions on your own, however. If you do collaborate on homeworks, you must cite all of your fellow collaborators on the written problem set. You must neither copy solutions nor provide solutions to be copied. YOUR WRITE-UP OF A PROBLEM SOLUTION MUST BE YOURS.
NO COLLABORATION WILL BE ALLOWED ON EXAMS. Plagiarism, cheating, and other anti-intellectual behavior will be dealt with severely. If you feel you may have violated this code of ethics, please talk with either Professor Leighton or Dr. Vempala. Note that it is far better if you contact us, rather than vice-versa, in cases where there is a violation of the code of ethics.
Lastly, please realize that we understand the pressure that you may experience while at MIT and that we will try to help you as best as we can.
The grade for the course will be based on your performance in tutorials, problem sets, and exams, as follows:
Each of the 13 tutorials will be worth 100 points. You will be assigned 100 points if you show up at tutorial and actively participate. You will get 0 points for failure to attend. The default grade will be 100 points, although the instructor can lower your score if he/she feels that you are not putting forth a valid effort. Your overall tutorial grade will be the average of your 12 best tutorial scores (i.e., the lowest tutorial score is dropped before averaging).
Each of the 13 problem sets will be worth 100 points. Your overall grade for problem sets will be the average of your 12 best scores (i.e., the lowest score will be dropped before averaging).
Each exam score will be normalized to 100 points. After normalization, 5 points will be automatically added to account for errors made in grading. (Any errors in grading that are subsequently discovered will be credited to your score but only by the amount that exceeds the 5 points already given.) Should the median adjusted score S of an exam fall below 70 points, your score will be multiplied by 70/S to account for the possibility that the exam was too hard. The maximum score for any exam is 100 points. A student that misses an exam without a valid reason will receive a score of 0.
The total score for the class will be computed by adding 20% of the tutorial and quiz scores with 30% of the problem set and final scores. All values will be rounded to the next highest multiple of 0.1. For example, we have illustrated the calculation of a typical total score below.
| Tutorials | 100 | X | 0.2 | = | 20.00 |
| Problem Sets | 87.4 | X | 0.3 | = | 26.22 |
| Quiz | 55.0 | X | 0.2 | = | 11.00 |
| Final Exam | 75.3 | X | 0.3 | = | 22.59 |
| Total | 79.81 (79.9) |
In consideration of students that perform well in the class except for a single exam, we will allow a student to adjust his/her total score by replacing one-half of the contribution of either the quiz or the final (but not both) with the unadjusted total score as computed above. For the example shown above, we would compute the adjusted total score as follows.
| Tutorials | 100 | X | 0.2 | = | 20.00 |
| Problem Sets | 87.4 | X | 0.3 | = | 26.22 |
| Adjusted Quiz | (55.0 + 79.9)/2 | X | 0.2 | = | 13.49 |
| Final Exam | 75.3 | X | 0.3 | = | 22.59 |
| Total | 82.30 (82.3) |
The exam score which is adjusted (if any) will always be selected so as to maximize the adjusted total score for the student. An exam score of 0 cannot be adjusted.
The adjusted total score will be converted into a final grade for the course using the following scale:
| 97.0 - 100.0 | A+ |
| 93.0 - 96.9 | A |
| 90.0 - 92.9 | A-- |
| 87.0 - 89.9 | A-- |
| 83.0 - 86.9 | B |
| 80.0 - 82.9 | B-- |
| 77.0 - 79.9 | C+ |
| 73.0 - 76.9 | C |
| 70.0 - 72.9 | C-- |
| 67.0 - 69.9 | D+ |
| 63.0 - 66.9 | D |
| 60.0 - 62.9 | D-- |
| 0.0 - 59.9 | F |
If a student has an adjusted total score that is within 2 points of the next grade level (e.g., 85.3), then the student's grade may be raised to the higher level. Such adjustment of the final grade will be made on a case-by-case basis.
(Yeah, this is the most hairy grading system I've ever seen, too.)
The exams will be hard in 6.042/18.062. It is imperative that students do well on the problem sets and tutorials in order to raise their average. Not only are the problem sets and tutorials essential to learning the material, they will be a significant part of your final grade.