Princeton University
Computer Science Department

Computer Science 341
Discrete Mathematics

Moses Charikar

Fall 2005

General Information    Handouts

Course Summary

This course in an introduction to discrete mathematics, particularly to those branches that are useful in computer science. Topics include combinatorics, probability, algorithms, and rudiments of computation theory. Prerequisites: MAT 103 and MAT 104.


Required Text: 
Discrete Mathematics and Its Applications, 5th edition
Kenneth H. Rosen
McGraw Hill
ISBN 0-07-242434-6

Optional Reference:
Discrete Mathematics: Elementary and Beyond
L. Lovasz, J. Pelikan, and K. Vesztergombi
Springer-Verlag, 2003
ISBN 0-387-95585-2

Administrative Information

Lectures: MW 3:00-4:20, Room: 006 Friend Center

Precepts: M 5:00-6:00, 007 Friend Center
                 M 7:30-8:20, 
007 Friend Center
                 F 10:00-10:50,  007 Friend Center

Professor: Moses Charikar - 305 CS Building - 258-7477 moses AT cs DOT princeton DOT edu
                  Office hours: Tue 2:30-3:30 or by appointment

Secretary: Mitra Kelly - 323 CS Building - 258-4562 mkelly AT cs DOT princeton DOT edu

Undergraduate Coordinator: Donna O'Leary - 410 CS Building - 258-1746 doleary AT cs DOT princeton DOT edu

Teaching Assistants:

Course mailing list:

All students should subscribe to the course mailing list. We will use this to send out important announcements. To subscribe, visit this webpage:


Weekly homeworks will be assigned on Wednesdays. They will be due at the beginning of class the following Wednesday. Late homeworks submitted by 5pm Friday will be penalized 50%. No late homeworks will be accepted beyond 5pm Friday.

You will have eleven homeworks in all and we will drop your lowest homework score. All homework problems will carry equal weight unless otherwise stated. Points will be deducted for excessively verbose solutions. Some problems may specify limits on the length of your solution, and anything beyond the prescribed limits will not be graded.

You may collaborate in groups of at most 3 students on the homeworks (see clarifications regarding collaboration policy below).
Some problems or problem sets will be marked "no collaboration". You are supposed to work on such problems completely on your own.


One homework assignment will be designated as a take-home midterm.
There will be a take home final exam to be taken in any 24 hour period during finals week


65% homework, 10% take-home midterm, 25% final.