Computer Science 70 - Discrete Mathematics and Probability Theory - Spring 2011
Time and Location
Announcements
bSpace
Overview
The goal of this course is to introduce students to ideas and techniques from
discrete mathematics and probability that are widely used in EECS.
The course aims to present these ideas "in action"; each one will be geared
towards a specific significant application. Thus, students will see the purpose
of the techniques at the same time as learning about them.
Math55 and CS70
cover overlapping material; Math55, however, typically covers a wider range
of topics in less depth and with fewer applications, and is less closely
tailored to EECS. L&S Computer Science majors,
and EECS students admitted
in Fall 2010 or later, must take CS70.
Double majors in Math and EECS may take either CS70 or Math55.
Instructor
Teaching Assistants and Sections
Enrollment Questions
Head GSI Nick Knight
is responsible for implementing enrollment changes.
If you want to switch to another discussion section, you must
first contact the GSI for the section you wish to switch to,
to request approval. You may only switch with the approval of
the GSI for the section to which you want to switch. We will not
approve switches into sections that are full.
Homework
See the Announcements above for when homework is due.
Turn in your homework in the boxes labeled "CS70" on the 2nd floor of Soda Hall.
See the detailed instructions at the top of Homework 1 below on how to label
and turn in your homework.
Please begin your answer to each problem on a new sheet of paper,
and make sure that each sheet is labeled with your name, section number,
GSI name, the assignment number, the problem number, and "CS70--Spring 2011".
Reason: Different problems may be graded in parallel by different readers.
Warning: You risk receiving no credit, or losing points,
for any homework that does not conform to the above regulations!
Please take the time to write clear and concise solutions;
we will not grade messy or unreadable submissions.
No late homeworks will be accepted.
We will drop the lowest two homework scores.
Exams
There will be two midterms (in the evening, not in class) and a final:
A makeup final will only
be given for (1) unexpected circumstances beyond your control,
documented by a signed note from a physician or equivalent,
(2) conflict with another scheduled exam
(3) a religious holiday.
Contact us as soon as possible in cases (2) and (3).
There will be no makeup midterms;
instead your final exam grades will be used
as described under Grading.
You are required to a bring a student photo ID to all exams.
Grading
The grades will be computed as follows:
Text Book
You should purchase the course notes,
Discrete Mathematics and Probability Theory
at Copy Central on Hearst Ave near Euclid.
We will cover most all of these notes in the order given.
See below under Readings for other suggested references.
Course Policies
Prerequisites:
Sophomore mathematical maturity, and programming experience equivalent to
that gained in CS3 or the Advanced Placement Computer Science A course
(e.g., CS 3, E 7, CS 61A). If you lack any of these prerequisites,
you may only take the class with special permission from the instructor.
The work in the class will be pencil-and-paper exercises.
Readings:
Lecture notes will be posted on bSpace on or before the day of the
relevant class. For additional background and examples,
it is recommended that students consult the books
Discrete Mathematics and its Applications, by Kenneth Rosen
(6th ed., McGraw-Hill, New York, 2007) and Introduction to Probability,
by Bertsekas and Tsitsiklis (2nd ed., Athena Scientific, Massachusetts, 2002).
Lecture Notes:
Contact Information:
The instructor and GSIs will post announcements, clarifications, hints, etc.
on bSpace. Hence you must check bSpace frequently throughout the semester.
If you have a question, your best option is to post a message to the Forum
on bspace. The staff (instructor and GSIs) will check the forum regularly,
and if you use the forum, other students will be able to help you too.
When using the forum, please avoid off-topic discussions, and please do
not post answers to homework questions before the homework is due.
For informal discussions with other students, you are also welcomed to use
the chat room on bspace. The chat room will NOT be monitored on a
regular basis by the staff.
If your question is personal or not of interest to other students,
you may send email to cs70@inst.eecs. Email to this address is
forwarded to the instructor and all GSIs. We prefer that you use
this address, rather than directly emailing the instructor and/or your GSI,
as it will usually get a faster response and also helps to ensure
consistency in our treatment of students. If you wish to talk with
one of us individually, you are welcome to come to our office hours.
If the office hours are not convenient, you may make an appointment
with any of us by email. Please reserve email for the questions you
can't get answered in office hours, in discussion sections, or
through the newsgroup.
In a class this large, it can be challenging for the instructor to gauge
how smoothly the class is going. We always welcome any feedback on
what we could be doing better. If you would like to send anonymous comments
or criticisms, please feel free to use an anonymous remailer like this
one to avoid revealing your identity.
Collaboration:
You are encouraged to work on homework problems in study groups of
no more than 3 people; however, you must always write up the solutions
on your own, and you must never read or copy the solutions of other students.
Please write the names of your collaborators on your homework.
Similarly, you may use books or online resources to help solve
homework problems, but you must always credit all such sources in
your writeup and you must never copy material verbatim.
Warning: Your attention is drawn to the Department's Policy
on Academic Dishonesty. In particular, you should be aware that
copying solutions, in whole or in part, from other students in the class
or any other source without acknowledgment constitutes cheating.
Any student found to be cheating risks automatically failing the class
and being referred to the Office of Student Conduct.
Regrading Policies:
Regrading of homeworks or exams will only be undertaken in cases where
you believe there has been a genuine error or misunderstanding.
Bear in mind that our primary aim in grading is consistency,
so that all students are treated the same; for this reason,
we will not adjust the score of one student on an issue of
partial credit unless the score allocated clearly deviates from
the grading policy we adopted for that problem. If you wish to
request a regrading of a homework or exam, you must return it to
your section GSI with a written note on a separate piece of paper
explaining the problem. The entire assignment may be regraded,
so be sure to check the solutions to confirm that your overall
score will go up after regrading. All such requests must be
received within one week from the date on which the homework
or exam was made available for return.
Discussion sections
If you want to switch to another discussion section, you must
first contact the GSI for the section you wish to switch to,
to request approval. You may only switch with the approval of
the GSI for the section to which you want to switch. We will not
approve switches into sections that are full.
Helpful Hints
The following tips are offered based on our experience with
undergraduate classes in CS Theory. If you follow these guidelines,
you will make life much easier for yourself in this class.
1. Don't fall behind! In a conceptual class such as this,
it is particularly important to maintain a steady effort throughout
the semester, rather than hope to cram just before homework deadlines
or exams. This is because it takes time and practice for the ideas
to sink in. Make sure you allocate a sufficient number of hours every
week to the class, including enough time for reading and understanding
the material as well as for doing assignments. (As a rough guide,
you should expect to do at least one hour of reading and two hours
of problem solving for each hour of lecture.) Even though this class
does not have any major projects, you should plan to spend as much time
on it as on any of your other technical classes.
2. Take the homeworks seriously! The homeworks are explicitly
designed to help you to learn the material as you go along. Although
the numerical weight of the homeworks is not huge, there is usually
a strong correlation between homework scores and final grades in the class.
Also, regardless of how well you did on the homework, read the sample
solutions, even for the problems you got right. You may well learn a
different way of looking at the problem, and you may also benefit from
emulating the style of the solutions. (In science people learn a lot
from emulating the approach of more experienced scientists.)
3. Make use of office hours! The instructor and GSIs hold office
hours expressly to help you. It is often surprising how many students
do not take advantage of this service. You are free to attend as many
office hours as you wish (you are not constrained just to use the
office hours of your section GSI). You will also likely get more out of
an office hour if you have spent a little time in advance thinking about
the questions you have, and formulating them precisely.
(In fact, this process can often lead you to a solution yourself!)
4. Take part in discussion sections! Discussion sections are
not auxiliary lectures. They are an opportunity for interactive learning,
through guided group problem solving and other activities. The success
of a discussion section depends largely on the willingness of students
to participate actively in it. As with office hours, the better prepared
you are for the discussion, the more you are likely to get out of it.
5. Form study groups! As stated above, you are encouraged to form
small groups (no more than 3 people) to work together on homeworks and
on understanding the class material on a regular basis. In addition to
being fun, this can save you a lot of time by generating ideas quickly and
preventing you from getting hung up on some point or other. Of course,
it is your responsibility to ensure that you contribute actively to
the group; passive listening will likely not help you much. And recall
the caveat above that you must write up your solutions on your own.