CS 70: Discrete Mathematics and Probability Theory, Summer 2014

Quick Links for Visitors from the Future

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:

The prerequisites for this course are some programming experience and basic calculus.

Your lovely staff

James Cook

Instructor: James Cook
jcook@cs
Lectures: MTWR 12:30-2:00pm in 2050 VLSB
OH: M 2:30-3:30pm - Soda 651,
W 4:30-5:30pm - Soda 751
"Math is the study of how twelve makes a dozen."

 

Head TA: Ajay Tripathi
chausies@berkeley.edu
Section: 107, 11-12n TuTh
OH: W 11-12n - 611 Soda
"Not-knowing is true knowledge.
Presuming to know is a disease.
First realize that you are sick;
then you can move toward health."
TA: Kate Rakelly
krakelly@berkeley.edu
Section: 105, 9-10am TuTh
OH: Th 10-11am - 122 Wheeler
"Sucking at something is the first step
to being sorta good at something."
TA: Palak Bhushan
palak@berkeley.edu
Section: 103, 5-6pm MW
OH: M 4-5pm - 411 Soda
"Meaning is overrated."
 
TA: Steven Bi
chenhsi@berkeley.edu
Section: 108, 2-3pm MW
OH: Th 2-3pm - 651 Soda
"Ipsa scientia potestas est."
TA: Steven Chen
mingchen@berkeley.edu
Section: 104, 6-7pm MW
OH: W 5-6pm - Bechtel Library
"Go Brazil!!!!"
TA: Anthony Polloreno
anthony.polloreno@berkeley.edu
Section: 101, 3-4pm MW
OH: M 5-6pm - 411 Soda
"1. Write down the problem.
2. Think very hard.
3. Write down the answer."
 
TA: Brielin Brown
brielin@berkeley.edu
Section: 106, 10-11am TuTh
OH: Th 11-12n - 748 Evans
"The best education consists of immunizing people against systematic attempts at education"
TA: Jerry Uejio
jerryuejio@gmail.com
Section: TuTh 109, 2-3pm, 405 Soda (Note: not listed on telebears)
OH: Tu 3-4pm - 405 Soda
"The words of truth are always paradoxical"
TA: Pandu Rendradjaja
pandu+cs70@berkeley.edu
Section: 102, 4-5pm MW
OH: F 10-11am - 411 Soda
"I wanted to buy a candle holder, but the store didn't have one. So I got a cake."

Weekly Schedule

Demo 4 - jQuery Week Calendar


Lab Assistant Office Hours

Time Lab Assistants Location
Monday
10-11AM Eric Kim & Davis Foote 411 Soda
11-12PM Olivia Wung & Yoojong Jin 411 Soda
Tuesday
10-11AM Olivia Wung & Davis Foote 411 Soda
11-12PM Olivia Wung & Eric Kim 411 Soda
3-4PM Albert Lin & George Li 651 Soda
Wednesday
9-10AM Brendan Hu & Olivia Wung 411 Soda
10-11AM Eric Kim & Davis Foote 411 Soda
3-4PM Albert Lin & George Li 651 Soda
Thursday
9-10AM Brendan Hu & Olivia Wung 411 Soda
Friday
9-10AM Brendan Hu & Olivia Wung 411 Soda


Communication

This course will use the following three websites.

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. (If you want to skip ahead, take a look at the lecture notes on the Spring 2014 website, although we won't follow those notes exactly.) After each lecture, we will update a pinned Piazza post indicating which parts of the notes were covered in that 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 Tele-BEARS. 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.

Note: In addition to the official sections listed at schedule.berkeley.edu, Jerry Uejio will be teaching a section on Tuesdays and Thursdays from 2-3pm in 405 Soda. There is nothing special about this section: just attend it if it's the most convenient for you.

Homework parties: Thursdays and Fridays

Times:

Every week, usually in the Wozniak Lounge (430 Soda Hall) there will be a "homework party". (On Fridays from 11am-1:30pm they will be in Cory 540, and then move to the Wozniak Lounge at 1:30pm. See the calendar below for other times when it will be in a different room.) Homework parties are completely optional. GSIs and lab assistants will be present in shifts (see above). Students are expected to help each other out, and if desired, form ad-hoc "pickup" homework groups in the style of a pickup basketball game.

The Woz is a relatively big space and if the weather is nice, we can also access the patio outside. But if the room is crowded, excercise good judgement and make room for others by leaving if you can find an alternative source of assistance. When the room is not crowded, people from the class are welcome to just hang out as long as they aren't bothering other people. Some social games might be available.

This is an experiment. For it to succeed, you all have to be very responsible in taking care of the room, not making messes, and putting things back the way they were.

Homework

There will be seven homework assignments. Each one will be released on a Tuesday evening and due the following Monday at 11:59:59pm. 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 Monday-through-Thursday lectures from the week preceding the due date. After each homework is graded, you will be able to use PandaGrader to view your grades and, in some cases, the reasons for them. Points may be deducted for solutions that are unclear, do not show intermediate work, are unnecessarily complicated, or are messy or improperly formatted.

Working Together

You must list all other students you collaborated with on the first page of your homework, as well as other sources of information you used. We encourage you to collaborate with your fellow students (in small groups) on the homeworks. If you don't have a group to work with, come to the homework parties! Clarifying concepts and discussing possible approaches to problems are good forms of collaboration. However, you must write up all solutions on your own, without ever looking at or copying any other 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.

Submitting Homework

You will prepare all your homework solutions as pdf files and submit them online, through PandaGrader. Make sure each of the problems are on separate pages, and pandagrader will allow you to choose which pages correspond to which problems. Problems of course don't have to take up the whole of a page, e.g. just half of a page — concise answers make everyone happy, as long as they're clear.

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 2014", the homework number, and the problem number at the top of the first page of your pdf file.

There are three main options for creating your pdf files:

You are allowed to mix-and-match these methods. For example, you could use LaTeX for problem 1 and handwrite+scan for problem 2 in the same homework.

There will 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 PandaGrader to submit your homework and read your grades and your feedback from the readers.

Regrade Requests

Regrades for homework assignments can be requested through PandaGrader no more than one week after you receive your grades. Regrade requests should include a clear explanation of which grading category of the rubric you believe yourself to fall under. We reserve the right to regrade your entire homework, and since we are taking a fresh look at it, it is possible you'll end up with a lower than you started with (though this doesn't usually happen). The regrade decision will be sent out via email a few days.

Homework Reflections

After each homework is due, the solutions will be posted and you will have three days to submit a "homework reflection", in which you should compare your homework solutions to the official solutions. For example, you could mention any mistakes you made, or cases where you found a different way to answer the problem, or if you think your solution is easier or harder to understand than the official solution. There's no need to comment on every question, but try to find three things to say.

A complete homework reflection (three comments) can improve your grade on the corresponding homework by up to 5%, but it won't push your grade over 100%. Note: the readers will grade these separately from your homework, so listing corrections to your homework answers won't improve your homework grade, except for the 5% you get for submitting a reflection.

Here is an example of a complete homework reflection: On question 4, I assumed E[XY]=E[X]E[Y], but forgot that X and Y might not be independent random variables. The official solution to question 6 is really long and all the details just make it confusing; I think my shorter solution is much clearer. I found a different way to solve question 7.

Exams

Midterm 1: Thursday, July 17, during lecture (rooms TBA)
Midterm 2: Thursday, July 31, during lecture (rooms TBA)
Final exam: Friday, August 15, 5:00pm-8:10pm in 1 Pimentel

The exams will start at 12:40pm sharp (in accordance with "Berkeley time"), but please arrive by 12:30pm sharp. You will have 80 minutes for each midterm and 3 full hours for the final. Contact the instructor at the start of the course if you need an accommodation through DSP. Make-up exams will not be given.

For each of the midterms you may bring one double-sided sheet of notes, and for the final exam you may bring three double-sided 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 (unless we've received an accomodation letter from DSP); this means no calculators, smartphones, earbuds, or anything else. The exams will be printed single-sided, 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.

The first midterm will most likely cover the first 2.5 homeworks, the second midterm will most likely cover the first five homeworks (focusing on the later ones) and the final will cover everything. 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 Wednesday lecture before each midterm. For the final there will be two review sessions during the lest two lectures of the course (August 13 and 14). The discussion sections before the midterms will not be review for the exam; they will cover the current week's material.

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 non-dropped 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.

Academic Honesty

Cheating on homeworks or exams will be taken seriously. We refer you to the department's policy on academic dishonesty. For homework, see the section on working together above. In particular, keep in mind the following:

Calendar

Week 1 Mon 6/23 Lecture
No discussion sections or office hours today
Tue 6/24 Lecture
No discussion sections or office hours today
Wed 6/25 Section 1
Lecture
Thu 6/26 Section 1
Homework 0 due
Homework Party (different room: go to Soda 310; we'll use Soda 405 for overflow)
Lecture
Fri 6/27 Homework party (different room: Cory 540)

Week 2 Mon 6/30 Section 2
Homework 1 due
Lecture
Tue 7/1 Section 2
Lecture
Wed 7/2 Section 3
Lecture
Thu 7/3 Section 3
Homework Party (in the Woz, which will be the usual room)
Homework 1 reflection due
Lecture
Fri 7/4 Independence day (no homework party)

Week 3 Mon 7/7 Section 4
Homework 2 due
Lecture
Tue 7/8 Section 4
Lecture
Wed 7/9 Section 5
Lecture
Thu 7/10 Section 5
Homework 2 reflection due
Lecture
Fri 7/11 Homework party

Week 4 Mon 7/14 Section 6
Homework 3 due
Lecture
Tue 7/15 Section 6
Lecture
Wed 7/16 Section 7
Review session in lecture
Thu 7/17 Section 7
Homework 3 reflection due
Midterm 1 during lecture (rooms TBA)
Fri 7/18 Homework Party

Week 5 Mon 7/21 Section 8
Homework 4 due
Lecture
Tue 7/22 Section 8
Lecture
Wed 7/23 Section 9
Lecture
Thu 7/24 Section 9
Homework 4 reflection due
Homework Party
Lecture
Fri 7/25 Homework Party

Week 6 Mon 7/28 Section 10
Homework 5 due
Lecture
Tue 7/29 Section 10
Lecture
Wed 7/30 Discussion sections converted to Office Hours
Lecture
Thu 7/31 Discussion sections converted to Office Hours
Homework 5 reflection due
Midterm 2 during lecture (rooms TBA)
Fri 8/1 Homework Party (different room: Cory 540)

Week 7 Mon 8/4 Section 12
Homework 6 due
Lecture
Tue 8/5 Section 12
Lecture
Wed 8/6 Section 13
Lecture
Thu 8/7 Section 13
Homework 6 reflection due
Homework Party
Lecture
Fri 8/8 Homework Party

Week 8 Mon 8/11 Section 14
Homework 7 due
Lecture
Tue 8/12 Section 14
Lecture
Wed 8/13 Section 15
Lecture
Thu 8/14 Section 15
Homework 7 reflection due
Review session in lecture
Fri 8/15 Final exam (5:00pm-8:10pm in 1 Pimentel)

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!)

Come to homework parties! We encourage collaboration on homeworks (but please read the homework policy above! all solutions must be your own). If you want to find a group to work with, or you and your friends want a nice place to work together, come to the homework parties.

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.