Massachusetts Institute of Technology Handout 1 6.042J/18.062J: Mathematics for Computer Science September 7, 2000 Professors Nancy Lynch and Shlomi Dolev

Course Information

This handout contains useful information about the course, and our expectations for this

term. Check the class website at http://theory.lcs.mit.edu/classes/6.042/fall00 for

up-to-date information, including handouts and announcements. You should also be on the mailing list 6042-students@theory.lcs.mit.edu. Please inform your TA if you have not received mail from this list after the first week.

REGISTER ONLINE TODAY

for the course at http://theory.lcs.mit.edu/classes/6.042/fall00. This will make

sure we get your name and email address right.

1 Staff

Lecturers:  Prof. Nancy Lynch  NE43-365 x3-7225

                          lynch@theory.lcs.mit.edu

Prof. Shlomi Dolev  NE43-367 x3-5905

                          shlomi@theory.lcs.mit.edu

TAs:  Andrej Bogdanov  NE43-410 3-0702

                          adib@theory.lcs.mit.edu

Wesley Chao  NE43-206 x5-6035

                          cynic@theory.lcs.mit.edu

Dwaine Clarke  NE43-410 x3-0702

                          declarke@mit.edu

Andrew Glenn  TBA  TBA

                          aglenn@mit.edu

Moses Liskov  NE43-334 x3-5866

                          mliskov@theory.lcs.mit.edu

Zully Ramzan  NE43-311 x3-2345

                          zulfikar@theory.lcs.mit.edu

George Savvides  TBA  TBA

                          savvides@mit.edu

Nitin Thaper  NE43-338 x3-7583

                          nitin@theory.lcs.mit.edu

Course Secretary: Joanne Talbot  NE43-366 x3-6054

                          joanne@theory.lcs.mit.edu

You can send mail to entire course teaching staff at 6042-staff@theory.lcs.mit.edu. Check the website at

http://theory.lcs.mit.edu/classes/6.042/fall00 for office hours.

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 already familiar with logical notation, elementary set theory, and elementary facts about numbers. To make sure that you are up to speed on this material, you should review Sections 1.1, 1.2, 1.4, and 1.5 and 2.3 of Rosen’s Discrete Mathematics and Its Applications and Chapter 1 of Velleman’s How to Prove It during the first week of the course.

If you have taken 18.063, 18.310, or 6.046J, you should not take this course. 18.063 may be substituted for 6.042 in the EECS M.Eng. and S.B. requirements. For such students interested in learning probability, we recommend 6.041, 18.440, 18.313, or 18.05.

3 Lectures

Lectures will be held Tuesdays and Thursdays from 2:30 to 4:00 in Room 2-190. Lecture notes will be posted on the class web page after each lecture.

4 Reading

Most weeks, we will assign readings on small amounts of material that we do not cover in lecture. This material is required and will be covered on problem sets, exams, and miniquizzes.

5 Tutorials

You must attend a two hour tutorial every Friday. Each tutorial will consist of approximately twelve students, so there will be a good opportunity for you to ask questions and to interact with your TA. The emphasis of the tutorials is on techniques for solving problems.

Each tutorial will begin with a brief mini-quiz. This quiz will be easy for anyone who is up-to-date on the course material. If you arrive late to tutorial, you will miss the quiz; there is no make-up opportunity.

For the remainder of the tutorial, the students will be divided into groups of three or four and all student groups will be assigned a given set of problems to solve as a team. The TA will ask one member from one or more groups to present orally the solution to each problem. If the presentation is not satisfactory, the TA may ask the entire group to write up the solution.

Tutorials are Fridays 9–11, 10–12, 11–1, 1–3, 2–4, and 3–5.

6 Textbooks

There are two required textbooks for the course, available from Quantum Books (under the 6.042 heading) in Kendall Square:

Daniel J. Velleman. How To Prove It: A Structured Approach, Cambridge University Press, Cambridge, England, 1994.

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

Velleman will be the focus for the first part of the semester while Rosen will be the focus for the second. There is a website for the Rosen book: http://www.mhhe.com/rosen/. You can also find last term’s version of the lecture notes at

http://theory.lcs.mit.edu/classes/6.042/fall00/.

7 Handouts and Course Notebook

Get a loose-leaf notebook for the course to keep your handouts organized.

All handouts will be on standard three-hole punched paper and will be numbered consecutively. They will be passed out in class, and also available in a file cabinet outside NE43-309. PostScript files for the handouts will be available from the class website at

http://theory.lcs.mit.edu/classes/6.042, or by anonymous FTP at theory.lcs.mit.edu
in the directory pub/classes/6.042/fall00.

8 Exams

There will be two two-hour Wednesday evening quizzes, on October 18 and November 15, from 7:30-9:30PM. In addition, there will be a three-hour comprehensive final exam scheduled during the Final Exam Period.

9 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 be due at the beginning of lecture on the following Tuesday. Problem sets turned in past 2:35pm will be considered late, and be penalized 20% of their grade. Problem sets more than two days late will not be accepted. When turning in a problem set, be sure to place it in the box that is labeled with the name of your TA. If you are unable to complete a homework on time, talk to your TA in advance.

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, on the top of the first page, anyone you collaborated with on the problem sets. Your name should appear on every page.

Be as clear and precise as you can 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; red is our color for grading.

If you are unhappy with the way that your homework has been graded, see your TA. Questions, suggestions, and complaints are welcomed by the course staff.

10 Problem Solving

We encourage you to collaborate in doing the problem sets. Study groups are an excellent means of mastering the course material. Besides, they are fun. However, you must write up solutions on your own. If you do collaborate on problem sets, you must cite all of your collaborators at the front of your submitted solutions. You may neither copy solutions nor provide solutions to be copied. Your write-up of a problem solution must be entirely your own.

The use of bibles or other pre-packaged sources of solutions to the assigned problems is not permitted.

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 Prof. Lynch or Prof. Dolev. In cases where there has been a violation of the code of ethics, it will be far better if you contact us, rather than vice versa. We understand the pressure that you may experience while at MIT and we will try to help you as best as we can.

11 Grades

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

Tutorials: 20% Mini-quizzes: 5% Problem Sets: 35% Quizzes

Quiz 1: 10% Quiz 2: 10% Final: 20%

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

12 Course Objectives and Outcomes

See http://theory.lcs.mit.edu/classes/6.042/handouts/H01a-obj.ps.gz for a draft state-

ment of course “objectives and outcomes”. At the end of the course, we will try to determine how well we have met these objectives.