Princeton University
Computer Science Department

Computer Science 341
Discrete Mathematics

Rob Schapire

Fall 2006


General Information | Schedule & Readings | Assignments & Exams | Precepts

Course Summary

This course is an introduction to important mathematical tools and techniques relevant to computer science.  An emphasis is placed on the development of rigorous mathematical skills and methods of proof.  The course is intended primarily for computer science undergraduates with possibly modest mathematical background.

Here is a tentative list of topics, which might be shortened if we run out of time:

Staff and administrative information


TTh, 11-12:20, Friend Center, room 009.


M 6:30-7:30pm or Tu 7:30-8:30pm, 102 CS Building.  (See below for more information.)


Rob Schapire:  407 CS Building, x8-7726, schapire@cs
Office hours: by appointment (via email), or just stop by.


Mohammad Mahmoody Ghidary (full-time):  001B CS Building, x8-1781, mohammad@cs
Office hours:  Wednesday 10-11am;  Thursday 10-11am.

Siddhartha Brahma (half-time):  001C CS Building, x8-7418, sbrahma@cs
Office hours: Wednesday, 4-6pm.

Note that Mohammad is a full-time TA for this course, but Siddhartha is only half-time.  For this reason, if you need help or have a question, you usually should go to Mohammad first.  Questions should be directed to Siddhartha only if they are about homework questions that he graded, or if it is not possible to ask Mohammad (for instance, because you are unable to go to his office hours).

Office hours and precepts will begin the week of September 25, but you should feel free to contact me or the TA's if you have questions before that time.

Undergraduate Coordinator: 

Donna O'Leary:  410 CS Building, x8-1746, doleary@cs



MAT 103 and MAT 104, or equivalent, or permission of instructor.


Instead of a text, we will be using:

Mathematics for Computer Science
Eric Lehman and Tom Leighton

These are the unpublished notes from a similar course taught at MIT, which we are using with the authors' permission.  They are available in PDF from the link above.  The notes are 339 pages long, so you might consider printing them out in chapters as we get to them rather than all at once.  We will have copies made for students who indicate an interest in purchasing one by Sunday, September 17.  See HW#0 for more information.

I believe that these notes will be quite sufficient, but if for some reason you want to do additional reading, you might consider the following book which has been used for this course in the past:

Discrete Mathematics and Its Applications, 6th edition
Kenneth H. Rosen
McGraw Hill, 2006

A copy of this book is being placed on reserve at the Engineering Library.


There will be weekly precepts focusing mainly on problem solving.  These also will be an opportunity to ask questions about course material or homework.  Some new material may sometimes be presented at the precepts.

Based on the results of the precept scheduling survey, we will hold precepts at the following times:

You can attend either precept.  Precepts will be held in room 102 of the Computer Science Building, and will begin the week of September 25.

Grading, exams and workload

Regular homework assignments will be given roughly once a week, and will consist of written exercises and problems (no programming).  There will be a take-home midterm exam and a take-home final exam.

Homeworks will be worth roughly 65% of your grade (plus or minus 5%).  The exams will be worth the remainder.  Failure to complete any significant component of the course may result in a grade of D or F, regardless of performance on the other components.

Final grades may also be adjusted slightly upward for regular and positive class and precept participation.

See the Assignments page for important information on the late policy and collaboration policy.

Getting help

The TA's and I are here to help, so don't hesitate to contact us or come see us if you are having trouble.  Because they can be challenging, it is very important that you start the homeworks early, not only so that you have enough time to finish them, but also so that you can get help if you have questions or difficulties.  You should not assume that someone will be available to help you at the very last minute (especially on weekends or at night).

Although I do not have fixed office hours, I encourage students to come see me.  You can send me email to set up an appointment, or just stop by.


As soon as possible, please join the course mailing list by visiting and following the instructions for subscribing.  When signing up for the mailing list, please provide your name, especially if you are using a non-Princeton email address.  To prevent spam, email addresses that I cannot identify as legitimate will be removed from the list.

This list will be used by the course staff for general announcements, such as last minute corrections to the homeworks, changes in due date, etc.  This list can also be used by students for discussing course material, general-interest questions about the homeworks, etc.  The TA's will attempt to monitor and respond to questions on this list.  Of course, if your question is specific to your own work, you will probably want to contact me or the TA's directly, and you should be careful not to give away partial or complete solutions to homework problems when posting to the entire list.

You can post to the list by sending mail to  (Note that, to prevent spam, you can only post to the list using the email address you used to subscribe to it.)