COS 340 Reasoning About Computation
Bernard Chazelle
Fall 2009
Course Summary
An introduction to mathematical topics relevant to computer science.
Combinatorics and probability will be covered in the context of computer science applications.
The course will present a computer science approach to thinking and modeling through such
topics as dealing with uncertainty in data and handling large data sets.
Students will be introduced to fundamental concepts such as NP-completeness and cryptography that arise from the world view of efficient computation.
Prerequisites: COS 126 and MAT 200, 202, or 204.
NO LAPTOP ALLOWED DURING LECTURES
Textbook
There is no textbook for the course. We will use reference material online.
Administrative Information
Lectures
- MW 3:00-4:20, Room: 006 Friend Center
Precepts
- M 4:30-5:20, 105 CS Building, P02
- M 7:30-8:20, 105 CS Building, P01
Professor:
- Bernard Chazelle
404 CS Building, 258-5380, chazelle AT cs DOT princeton DOT edu
Office hours: 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:
- Rong Ge
216 CS Building, 258-5389, rongge AT cs DOT princeton DOT edu
Office hours: 4:30pm - 5:30pm on Thursdays
- Yuri Pritykin
103A CS Building, 258-6795, pritykin AT cs DOT princeton DOT edu
Office hours: 5:30pm - 6:30pm on Mondays
- Sushant Sachdeva
313 CS Building, 258-6126, sachdeva AT cs DOT princeton DOT edu
Office hours: 4:30pm - 5:30pm on Tuesdays
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/cos340
Homeworks
Weekly homeworks will be assigned on Thursdays. 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 ten homework assignments. 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.
We may sometimes have bonus problems for extra credit. Rest assured that your
grade will not be affected negatively if you do not attempt such extra credit
problems. In the final grading process, we will assign initial grades without
taking extra credit into account. Your initial grade may be moved up if
you have extra credit (but will not be moved down if you don't).
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, it 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.
