CS 70: Discrete Mathematics and Probability Theory, Summer 2013
Description
In this course you should acquire fundamental logical reasoning and problem solving skills, including (1) the ability to formulate problems in precise mathematical terms, (2) the ability to distinguish valid arguments from invalid ones, (3) the ability to construct valid arguments, and (4) the ability to communicate your arguments in a clear and convincing way using proper mathematical style. These skills will be developed through explorations of several topics, which have applications to many areas of computer science. Specific topics include:
 Logic, mathematical proofs, and induction
 The stable marriage problem
 Modular arithmetic and the RSA cryptosystem
 Polynomials and their applications
 Graph theory
 Combinatorics
 Discrete probability: inference, expectation, and concentration
 Continuous probability
 Countability, diagonalization, and computability
The prerequisites for this course are some programming experience and basic calculus.
Personnel
Instructor:  Tom Watson 
Lectures:  MTWR 5:00pm6:30pm in 10 Evans Hall 
Contact:  tom AT cs dot berkeley dot edu 
Office hours:  W 12:30pm1:30pm in 651 Soda Hall 
R 12:30pm1:30pm in 651 Soda Hall  
TA:  Allen Huang 
Section 101:  MW 10:00am11:00am in 320 Soda Hall 
Section 105:  MW 11:00am12:00pm in 405 Soda Hall 
Contact:  hunallen AT gmail dot com 
Office hours:  F 11:00am12:00pm in 611 Soda Hall 
TA:  Victor Huang 
Section 102:  MW 1:00pm2:00pm in 320 Soda Hall 
Contact:  vortic AT berkeley dot edu 
Office hours:  T 1:00pm2:00pm in 611 Soda Hall 
W 2:00pm3:00pm in 611 Soda Hall  
TA:  Ajay Tripathi 
Section 103:  MW 3:00pm4:00pm in 320 Soda Hall 
Section 104:  MW 2:00pm3:00pm in 405 Soda Hall 
Contact:  chausies AT berkeley dot edu 
Office hours:  M 4:00pm5:00pm in 611 Soda Hall 
R 2:30pm3:30pm in 611 Soda Hall  
TA:  Daniel Wong 
Section 106:  MW 12:00pm1:00pm in 405 Soda Hall 
Section 107:  MW 4:00pm5:00pm in 405 Soda Hall 
Contact:  daniel_wong AT berkeley dot edu 
Office hours:  M 10:30am11:30am in 611 Soda Hall 
T 10:00am11:00am in 611 Soda Hall 
Communication
This course will use the following three websites.
 http://www.cs.berkeley.edu/~tom/cs70.html
You are looking at this page right now. This is the course webpage, which contains all the logistical details. Please read this page thoroughly.  https://bspace.berkeley.edu/
Use bSpace to check your grades and to submit your homeworks. All homeworks will be submitted online through bSpace.  https://piazza.com/berkeley/summer2013/cs70/
We will use Piazza as the "onestop shop" throughout the semester: for a Q&A forum, for official announcements, and for posting content under the "Course Page" resources. Enrollment in Piazza is mandatory. If you have questions about anything related to the course, please post them on Piazza rather than emailing the instructor or TAs. Please do not post anything resembling a solution to a homework problem before it's due. If in doubt, you should make your post private (visible to instructors only). We always welcome any feedback on what we could be doing better.
Lectures
For the "textbook", we will use a set of lecture notes for CS 70 that have been developed over the years by the professors who have taught this course. We will gradually post the notes on Piazza throughout the semester. After each lecture, we will update a pinned Piazza post indicating which parts of the notes were covered in that lecture. We will take a 5 minute break in the middle of each lecture. If you miss a lecture (or even if you don't), you might find it helpful to view the webcasts of previous iterations of the course, although you are still responsible for knowing the material as it is presented in this iteration. The following books are not required for this course, but they can be consulted for supplementary reading and exercises: Discrete Mathematics and Its Applications by Rosen, Discrete Mathematics with Applications by Epps, and Introduction to Probability by Bertsekas and Tsitsiklis.
Sections
The discussion sections will not cover new material, but rather will give you additional practice solving problems. The best way to learn math is to do math, so you should take advantage of every opportunity to solve more problems. The section problems, as well as model solutions, will be posted on Piazza. There will be no sections on the first day of class. If you want to attend a different section than the one you are officially enrolled in, you may swap with someone from that section, but there is no need to try to swap sections on TeleBEARS. You may attend a different section without swapping with someone only if there is enough space in the classroom. If there are fewer desks than students, then students who are officially enrolled in that section (or have a swapping arrangement) will get seating priority.
Section 1Section 2
Section 3
Section 4
Section 5
Section 6
Section 7
Section 8
Section 9
Section 10
Section 11
Section 12
Section 13
Section 14
Section 15
Homeworks
There will be seven homeworks. Each homework will be released on a Wednesday evening and due the following Tuesday at 4:00pm. No late homeworks will be accepted under any circumstances. Model solutions to each homework will be released after the deadline. All homeworks and model solutions will be posted on Piazza. Each homework will mainly cover the material from the MondaythroughThursday lectures from the week preceding the due date. After each homework is graded, you will be able to use bSpace to view your grades as well as comments (if any) from the readers justifying point deductions. Points may be deducted for solutions that are unclear, do not show intermediate work, are unnecessarily complicated, or are messy or improperly formatted.
You will prepare all your homework solutions as pdf files and submit them online, through bSpace. Your solution to each problem of each homework should be in a separate pdf file, and will be handed in separately on bSpace. If a problem has more than one part, for example 1a, 1b, and 1c, then all of those parts should be together in the same pdf file. A sample template for your homework solutions can be found in the "Homework" folder on Piazza. You should put your name, student ID number, "CS 70, Summer 2013", the homework number, and the problem number at the top of the first page of each pdf file.
There are three main options for creating your pdf files:
 Use LaTeX. This is the recommended method since it is powerful and convenient to use for typesetting mathematics, and it produces nicelooking documents. The tradeoff is that there is a slight learning curve, and it is not WYSIWYG. LaTeX tutorials are easy to find online, by Googling "LaTeX tutorial". The LaTeX source for the sample template can also be found in the "Homework" folder on Piazza, and it can be compiled by running "pdflatex template.tex" on a Unix machine that has a LaTeX distribution installed.
 Use a word processor (with formula editor) and export the document as a pdf.
 Handwrite your solutions and scan them to create a pdf. See here for scanning instructions.
You are allowed to mixandmatch these methods. For example, you could use LaTeX for problem 1 and handwrite+scan for problem 2 in the same homework.
There will also be a special "Homework 0" that is due at 4:00pm on Thursday of the first week of class. Homework 0 does not count toward your grade, but it has two purposes. First, to make sure you know how to produce a pdf file with your solutions. Second, to make sure you know how to use bSpace to submit your homework and read your grades and your feedback from the readers.
We encourage you to collaborate with your fellow students (in small groups) on the homeworks. Clarifying concepts and discussing possible approaches to problems are acceptable forms of collaboration. However, you must write up all solutions on your own, without ever looking at or copying any fellow student's solutions. If you are tempted to look at someone else's solutions (this includes over the Internet), keep in mind that the exams carry much more weight than the homeworks, and there is a strong correlation between students' exam scores and the effort they put into the homework.
Homework 1Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Exams
Midterm 1: Friday, July 19, 5:00pm7:10pm in 2050 Valley LSBMidterm 2: Friday, August 2, 5:00pm7:10pm in 155 Dwinelle
Final exam: Friday, August 16, 5:00pm8:10pm in 2050 Valley LSB
The exams will start at 5:10pm sharp (in accordance with "Berkeley time"), but please arrive by 5:00pm sharp. You will have 2 full hours for each midterm and 3 full hours for the final. Contact the instructor immediately if you need an accommodation through DSP. Makeup exams will not be given.
For each of the midterms you may bring one doublesided sheet of notes, and for the final exam you may bring three doublesided sheets of notes (feel free to use your midterm sheets for two of them). Your sheets of notes may be typed. Take your sheets of notes with you at the end of an exam; do not turn them in. You may not use anything else during an exam; this means no calculators, smartphones, earbuds, or anything else. The exams will be printed singlesided, so there will be plenty of room for scratch work on the backs of pages. Attendance at the exams is mandatory. At the end of an exam, we will ask you to bring your exam to the front of the room and put it in the box yourself, to ensure that nothing gets lost. We expect to return your graded midterms to you at the end of your Monday section after the exam.
The first midterm will most likely cover the first 2.5 homeworks, the second midterm will most likely cover the next 2.5 homeworks, and the final will be cumulative. We will announce the exact coverage of the exams later. We will provide sample exams from previous iterations of the course (on Piazza) for you to practice with. There will be a review session (run by the TAs) during the lectures preceding the exams: for each midterm there will be one review session on the day before, and for the final there will be two review sessions on the Wednesday and Thursday before, respectively. Each review session may run for up to 2 hours (instead of the usual 80 minutes for lecture). The Wednesday discussion sections before the midterms will not be review for the exam; they will cover the current week's material.
Midterm 1Midterm 2
Final exam
Grading
Homeworks: 30%Midterm 1: 20%
Midterm 2: 20%
Final exam: 30%
Of the seven homeworks (excluding homework 0), each student's lowest homework score will be dropped at the end of the semester. Hence, the nondropped homeworks are each worth 5%. By default the course will be graded on a curve, according to the departmental guidelines. However, if we feel that students have performed better than expected overall, then we will be happy to make the curve more generous.
If you feel that there was a misunderstanding or clerical error in the grading of one of your homework or exam problems, you may submit a written regrade request to Ajay or Daniel (preferably in their office hours or sections). The request must be submitted within one week of you receiving the graded work. The request must consist of a sheet of paper identifying the problem number (and homework number, in the case of a homework) and explaining what you think the misunderstanding is. In the case of an exam, this sheet should be stapled to your graded exam. Note that points will only be awarded for misunderstandings or clerical errors, not in cases of "I think my solution deserves more partial credit"; this is because a consistent rubric of partial credit will be applied to all students, and we cannot change the rubric for one student. Ajay and Daniel will not do regrade requests on the spot; they will process them in batch mode, and their decisions will be final.
Cheating on homeworks or exams will be taken seriously. We refer you to the department's policy on academic dishonesty.
Calendar
Week 1  Mon 6/24  No discussion sections or office hours today Lecture 
Tue 6/25  Lecture  
Wed 6/26  Section 1 Lecture 

Thu 6/27  Homework 0 due Lecture 

Fri 6/28 
Week 2  Mon 7/1  Section 2 Lecture 
Tue 7/2  Homework 1 due Lecture 

Wed 7/3  Section 3 Lecture 

Thu 7/4  No lecture or office hours today (Independence Day)  
Fri 7/5 
Week 3  Mon 7/8  Section 4 Lecture 
Tue 7/9  Homework 2 due Lecture 

Wed 7/10  Section 5 Lecture 

Thu 7/11  Lecture  
Fri 7/12 
Week 4  Mon 7/15  Section 6 Lecture 
Tue 7/16  Homework 3 due Lecture 

Wed 7/17  Section 7 Lecture 

Thu 7/18  Review session in lecture  
Fri 7/19  Midterm 1 (5:00pm7:10pm in 2050 Valley LSB) 
Week 5  Mon 7/22  Section 8 Lecture 
Tue 7/23  Homework 4 due Lecture 

Wed 7/24  Section 9 Lecture 

Thu 7/25  Lecture  
Fri 7/26 
Week 6  Mon 7/29  Section 10 Lecture 
Tue 7/30  Homework 5 due Lecture 

Wed 7/31  Section 11 Lecture 

Thu 8/1  Review session in lecture  
Fri 8/2  Midterm 2 (5:00pm7:10pm in 155 Dwinelle) 
Week 7  Mon 8/5  Section 12 Lecture 
Tue 8/6  Homework 6 due Lecture 

Wed 8/7  Section 13 Lecture 

Thu 8/8  Lecture  
Fri 8/9 
Week 8  Mon 8/12  Section 14 Lecture 
Tue 8/13  Homework 7 due Lecture 

Wed 8/14  Section 15 Review session in lecture 

Thu 8/15  Review session in lecture  
Fri 8/16  Final exam (5:00pm8:10pm in 2050 Valley LSB) 
Advice
The following tips are based on our experience with CS 70.
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.
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.)
Don't wait until the last minute to start homeworks! Our best advice is to read through the homework problems as soon as they are available, and let them percolate in your brain. Think through possible approaches while you are waiting in line, or stuck in an elevator, or whatever. Sleeping on a problem has often helped people to come up with a creative approach to it. Definitely do not wait until the night before it is due to start working on the homework.
Make use of office hours! The instructor and TAs 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 TA). 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!) If you cannot make any of the scheduled office hours, you can also set up an appointment.
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.
Form study groups! As stated above, you are encouraged to form small groups (two to four 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.
Pay attention in lectures! As the semester proceeds, many of you will no doubt feel the urge to "daydream" during lectures, or to skip them altogether, on the grounds that you can catch up by reading the lecture notes. If you follow this strategy, you should be aware that reading mathematics is NOT the same as reading a novel or a news article: each page of mathematics needs to be read many times before it is fully understood, and needs to be backed up by examples and discussion. Following the material in class should save you several readings; even just watching it go by without fully understanding it makes your later reading easier. And you also get the benefit of student questions, examples etc. Exactly how you handle lectures is up to you. One strategy is to print out the lecture notes in advance, bring them to lecture, and add a few additional notes during class.