Massachusetts Institute of Technology Handout 1 6.042J/18.062J: Mathematics for Computer Science September 10, 1998 Professors Nancy Lynch and Srinivas Devadas

Course Information

1 Staff

Lecturers:  Prof. Srini Devadas  NE43-258  x3-0454

           devadas@mit.edu

Office Hours:  Fridays (NE43-258)  1–3pm
Prof. Nancy Lynch  NE43-365  x3-7225

          lynch@lcs.mit.edu

Office Hours:  Wednesdays (NE43-365)  4-5pm
Teaching Assistants:  Eric Lehman (Head TA)  NE43-336  x3-5971

e lehman@theory.lcs.mit.edu

Office Hours:  Mondays  2-5pm
Alex Duran  NE43-338  x3-7583

           amsduran@mit.edu

Office Hours:

Sarfraz Khurshid  i nsert email address

Office Hours:

Brian Dean  2-342  x3-4102

bdean@mit.edu

Office Hours:

Adam Gould

agould@mit.edu

Office Hours:

Alex Sherman

asherman@mit.edu

Office Hours:

TBA

i nsert email Office Hours:

Course Secretaries:  Joanne Talbot  NE43-366  x3-6054
joanne@theory.lcs.mit.edu Irena Sebada  NE43-201,  x3-2322

irena@supertech.lcs.mit.edu

2 Prerequisites and “antirequisites”

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

Most of you are probably already familiar with logical notation, elementary set theory, and elementary facts about numbers. In order to make sure that you are up to speed on this material, you should read Sections 1.1–1.5 and 2.3 of Rosen’s Discrete Mathematics and Its Applications during the first week of the course.

If you have taken 18.063, 18.310, or 6.046, you should not take this course. (To learn probability, we recommend that those 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.)

3 Lectures

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 there will be differences. Lecture notes for new material will be handed out in time for exams, but not in time to help with homework. So to keep up, you will need to attend lecture.

4 Tutorials

You must attend a two-hour tutorial every Friday. ATTENDANCE WILL BE TAKEN. Each tutorial will consist of approximately 12 students, so there will be a good opportunity for you to ask questions and to interact with an instructor. The emphasis of the tutorials is on techniques for solving problems, although new material will occasionally be presented. During the second hour or so, the students will work in groups of three or four and each group will be assigned a problem to solve as a team. The instructor 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 solution.

5 Handouts and course notebook

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. You can also reach them by anonymous FTP at

theory.lcs.mit.edu in the directory pub/classes/6.042/fall98.

6 Books

The required textbooks for the course, which can be purchased at the Kendall Coop are:

Kenneth H. Rosen. Discrete Mathematics and its Applications, Third Edition, McGraw-Hill, Inc., New York, 1995.

Antonella Cupillari. The Nuts and Bolts of Proofs, PWS Publishing Company, Boston MA, 1993.

YOU SHOULD READ The Nuts and Bolts of Proofs COVER-TO-COVER DURING THE FIRST 2 WEEKS OF THE COURSE. Discrete Mathematics and its Applications will serve as a useful reference for most of the course material.

Both texts are available at The Coop under the heading 18.062.

7 Exams

There will be one quiz from 7pm to 9pm on the evening of Wednesday, November 4. There will be a 3-hour final exam during the Final Exam Period at the end of the term.

8 Problem Sets

Problem sets will be assigned weekly. They will usually be handed out in lecture on Tuesday to cover that week’s lectures and tutorial, and then due in lecture on the following Tuesday. PROBLEM SETS WILL BE COLLECTED AT THE START OF CLASS. Any problem sets turned in past 2:30pm will be considered late. LATE PROBLEM SETS WILL BE PENALIZED 20% OF THEIR GRADE. Also: 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 tutorial instructor. Also, ACKNOWLEDGE, AT THE TOP, 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.

9 Collaboration

You are encouraged to collaborate in solving the homeworks. Study groups provide an excellent means of mastering the course material. (Besides, they are fun.) You must write up solutions on your own, however. If you do collaborate on homeworks, you must cite all of your 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 ENTIRELY 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 Prof. Devadas or Prof. Lynch. Note that it will be far better if you contact us, rather than vice-versa, in cases where there is a violation of the code of ethics.

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.

10 Your grade

Your grade for the course will be based on your performance in tutorials and on problem sets, and exams, as follows:

10.1 Tutorials–20%

Each of the 12 tutorials will be worth 100 points. You will get 100 points if you show up at tutorial and participate actively. You will get 50 points if you show up and sleep, and 0 points if you don’t show up. Your usual grade (we hope) will be 100 points, although your instructor can lower your score if he/she feels that you are not putting forth a serious effort. Your overall tutorial grade will be the average of your 11 best tutorial scores (i.e., the lowest tutorial score is dropped before averaging).

10.2 Problem Sets–30%

Each of the 11 problem sets will be worth 100 points. Your overall grade for problem sets will be the average of your 10 best scores (i.e., the lowest score will be dropped before averaging).

10.3 Exams (Quiz 20%, Final 30%)

Each exam score will be normalized to 100 points. If the median m of an exam turns out to be very low (below 70), the grades for that exam will by curved, by multiplying the by \frac{70}{m} to account for the fact that the exam was too hard. (However, you can’t get more than 100 points for any exam.) If you miss an exam without a valid reason, you will receive a score of 0.

10.4 Total Score

Your total score for the course will be computed by adding 20% of the tutorial and quiz scores and 30% of the problem set and final scores. All values will be rounded to the next higher multiple of 0.1. For example, here is the calculation of a typical total score:

Tutorials  100.0 × .2 = 20.00
Problem Sets 87.4 × .3 = 26.22
Quiz  55.0 × .2 = 11.00
Final Exam  75.3 × .3 = \underline{22.59}
Total Score  79.81 ⇒ 79.9

Because we have found that many students perform well in the class except for one exam, we will automatically take into account such an anomaly by replacing one-half of the contribution of either the quiz or the final (but not both) with the (unadjusted) total score. (One exceptions: We will not adjust an exam score of 0!) For the example above, we would compute the adjusted total score as follows:

Tutorials  100.0 × .2 = 20.00
Problem Set  87.4 × .3 = 26.22
Adjusted Quiz  \frac{55.0+79.9}{2} × .2 = 13.49
Final Exam  75.3 × .3 = \underline{22.59}
Adjusted Total Score  82.30 ⇒ 82.3

Whether or not to adjust, and if so, which exam score to adjust, will always be decided so as to maximize the adjusted total score. 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 B+
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- – 59.9 F

If your adjusted total score that is within 2 points of the next grade level (e.g., 85.3), then we reserve the option of raising your grade to the next higher level. Such an adjustment of the final grade will be made on a case-by-case basis.

10.5 How to get a good grade

The exams will be hard, so it is important that you do well on the problem sets and tutorials in order to raise your total score. We have arranged things this way on purpose, because we know that the problem sets and tutorials are essential to learning the material. Be sure to keep up day-to-day—the material has a lot of dependency, you can easily get lost otherwise.