Princeton University
Computer Science Department

Computer Science 341
Discrete Mathematics

Moses Charikar

Fall 2003

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.

Textbook (changed from last year)

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

Optional Reference:
Invitation to Discrete Mathematics
Jiri Matousek and Jaroslav Nesetril
Oxford University Press
ISBN 0-19-850207-9

Administrative Information

Lectures: MW 3:00-4:20, Room: 104 Computer Science Building

Precepts: M 5:00-6:00,  007 Friend Center
                 M 7:30-8:20,  112 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: Tina McCoy - 410 CS Building - 258-1746 tmmccoy 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, send mail to majordomo AT cs DOT princeton DOT edu with the text "subscribe cs341" in the body of the message.


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.


There will be a take home final exam to be taken in any 24 hour period during finals week


80% homework, 20% final.