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:
- 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.
Your lovely staff
|
Weekly Schedule
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.
- https://inst.eecs.berkeley.edu/~cs70/su13/
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://www.pandagrader.com/courses/152
All homework will be submitted through PandaGrader, and all homework and exam grades will be given back through PandaGrader. - https://piazza.com/berkeley/summer2014/cs70/
We will use Piazza as the "one-stop 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. (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.
- Note 1
- Note 2
- Note 3
- Note 4
- Note 5
- Note 6
- Note 7
- Note 8
- Note 9
- Note 10
- Note 11
- Note 12
- Note 13
- Note 14
- Note 15
- Note 16
- Note 17
- Note 18
- Note 19
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:
- Thursdays, 3pm-6pm (Wozniak Lounge)
- Fridays, 11am-3pm (11-1:30: 540 Cory; 1:30-3: Wozniak Lounge)
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:
- Use LaTeX. This is the recommended method since it is powerful and convenient to use for typesetting mathematics, and it produces nice-looking 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 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:
- Give credit. You must list any students you worked with, as well as other sources of information you used, on the first page of your homework.
- Don't share solutions. Working together means clarifying concepts and discussing possible approaches. Never look at any part of someone else's solution (including online) and never share any part of your own work with another student.
- When in doubt, ask. If you're not sure whether a particular situation constitues cheating, ask a TA or the instructor.
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 PartyLecture |
|
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.