Princeton University Computer Science Department

Computer Science 341 Discrete Mathematics Moses Charikar

Fall 2005

Course Summary

Textbook 

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

• Alex Golovinskiy - 103C CS Building - 258-0419  agolovin AT cs DOT princeton DOT edu
  Office hours: Tue 4:30-5:30
  
• Yury Makarychev -  217 CS Building - 258-0451  ymakaryc AT cs DOT princeton DOT edu
  Office hours:  Mon 6:30-7:30
  

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:
https://lists.cs.princeton.edu/mailman/listinfo/cos341

Homeworks

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.

Exams

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

Grading 

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

Collaboration

• Homework group policy:
  Collaboration on homeworks is welcome and warmly encouraged. You may collaborate in groups of at most 3 students. These groups must be disjoint and discussion across groups is not allowed.
• Write up your own solutions:
  Collaboration is limited to discussion of ideas only, and you must always write up the solutions entirely on your own.

  Simply copying a proof is not sufficient (and in fact, disallowed in this course); you are expected to write it up in your own words, and you must be able to explain it if you are asked to do so. Your proofs may refer to course material and to earlier homeworks in the semester. Except for this, all results you use must be proved explicitly.

• Cite your sources and collaborators:
  You may use references to help solve homework problems, but you must always cite your sources. In writing up your homework you are allowed to consult any book, paper, or published material. If you do so, you are required to cite your source(s).

  You will be asked to acknowledge all help you received from others. This will not be used to penalize you, nor will it affect your grade in any way. Rather, is intended only for your own protection. You must explicitly acknowledge everyone who you have worked with or who has given you any significant ideas about the homework. Not only is this good scholarly conduct, it also protects you from accusations of theft of your colleagues' ideas.

• Academic integrity, and general rules of academic conduct:
  You may not share written work with anyone else. You may not receive help on homework assignments from students who have taken the course in previous years, you may not review homework solutions from previous years and you may not search for solutions to problems on the web.

  Copying solutions, in whole or in part, from other students or any other source without acknowledgment constitutes plagiarism, and is a violation of academic integrity at Princeton. The consequences are quite severe.

  Explaining the meaning of a question, discussing a way of approaching a solution, or collaboratively exploring how to solve a problem within your group is an interaction that we encourage. On the other hand, you should never read another student's solution or partial solution, nor have it in your possession, either electronically or on paper. You should write your homework solution strictly by yourself.

  Presenting another person's work as your own constitutes plagiarism, whether that person is a friend, an unknown student in this class or a solution set from a previous semester's class, or an anonymous person on the Web who happens to have solved the problem you've been asked to solve. Everything you turn in must be your own doing, and it is your responsibility to make it clear to us that it really is your own work. The following activities are specifically forbidden in all graded course work:

  • Possession (or theft) of another student's solution or partial solution in any form (electronic, handwritten, or printed).
  • Giving a solution or partial solution to another student, even with the explicit understanding that it will not be copied.
  • Working together with anyone outside your homework group to develop a solution that is subsequently turned in (either by you or by the other person).
  • Looking up solution sets from previous semesters of this class or classes at other universities and presenting that solution, or any part of it, as your own.