## CS70: Discrete Mathematics and Probability Theory, Spring 2016

### Instructors:

Lecture: T-Th 12:30-2:00 PM, Wheeler Auditorium Jean Walrand

email: walrand at berkeley (.) edu

Office: 257 Cory Hall.

Office hours:

TuW-2:30-3:30

Satish Rao

email: satishr at cs (.) berkeley (.) edu

Office: 687 Soda Hall.

Office hours:

MoTh-3:00-4:00.

### Notes

There is no textbook for this class. Instead, there is a set of fairly comprehensive lecture notes. The notes are undergoing revisions this semester, so notes posted well in advance of lecture may change closer to the date. So make sure you revisit the notes after lecture. Note 0 is background material that you should make sure you understand before the first lecture. Each note may be covered in one or more lectures. We are still working on some new notes for late in the semester; they will appear later.- Note 0: Review of Math Notation
- Note 1: Propositions and Quantifiers
- Note 2: Proofs
- Note 3: Induction
- Note 4: Stable Marriage
- Note 5: Graph Theory
- Note 6: Modular Arithmetic
- Note 7: Bijections and RSA
- Note 8: Polynomials
- Note 9: Error Correcting Codes
- Note 10: Infinity and Uncountability
- Note 11: Self-Reference and Uncomputability
- Note 12: Counting
- Note 13: Introduction to Discrete Probability
- Note 14: Conditional Probability
- Note 15: Two Killer Applications
- Note 16: Random Variables: Distribution and Expectation
- Note 17: Variance
- Note 18: Chebyshev's Inequality
- Note 19: Some Important Distributions
- Note 20: Continuous Probability
- Note 24: Markov Chains
- Note 25: Review of Probability
- Note 26: Estimation

### Videos

Lectures on Calcentral!

### Slides

Slides generally follow the notes.

- Lecture 1: slides; handout (6up) handout (1up) Propositions. Note 1.
- Lecture 2: slides; handout (6up) handout (1up) Proofs. Note 2.
- Lecture 3: slides; handout (6up) handout (1up) Induction. Note 3.
- Lecture 4: slides; handout (6up) handout (1up) Induction. Stable Marriage. Note 4.
- Lecture 5: slides; handout (6up) handout (1up) Graphs.
- Lecture 6: slides; handout (6up) handout (1up) Graphs: Coloring, Trees, Hypercubes.
- Lecture 7: slides; handout (6up) handout (1up) Note 6. Modular Arithmetic, Euclid, and Extended Euclid.
- Lecture 8: slides; handout (6up) handout (1up) Note 6. Modular Arithmetic, Euclid, and Extended Euclid.
- Lecture 9: slides; handout (6up) handout (1up) Midterm Review
- Lecture 10: slides; handout (6up) handout (1up) Secret Sharing/Polynomials.
- Lecture 11: slides; handout (6up) handout (1up) Error Correction/Polynomials.
- Lecture 12: slides; handout (6up) handout (1up) Finish Berlekamp-Welch. Countability
- Lecture 13: slides; handout (6up) handout (1up) Finish Countability. Computability.
- Lecture 14: slides; handout (6up) handout (1up) Counting.
- Lecture 15a: slides; handout (6up) handout (1up) Finish Counting.
- Lecture 15b: slides; handout (6up) handout (1up) Probability Space.
- Lecture 16: slides; handout (6up) handout (1up) Conditional Probability and Bayesâ€™ Rule.
- Lecture 17: slides; handout (6up) handout (1up) Bayes; Balls, Bins and Coupons
- Lecture 18: slides; handout (6up) handout (1up) Random Variables and M2 Probability Review
- Lecture 19: slides; handout (6up) handout (1up) Random Variables; Expectation
- Lecture 20: slides; handout (6up) handout (1up) Distributions, Independent Random Variables.
- Lecture 21: slides; handout (6up) handout (1up) Variance, Markov, Chebyshev
- Lecture 22: slides; handout (6up) handout (1up) Confidence Intervals and Linear Regression
- Lecture 23: slides; handout (6up) handout (1up) Conditional Expectation
- Lecture 24: slides; handout (6up) handout (1up) Markov Chains
- Lecture 25: slides; handout (6up) handout (1up) Markov Chains: Distributions
- Lecture 26: slides; handout (6up) handout (1up) Continuous Probability
- Lecture 27: slides; handout (6up) handout (1up) CLT + Random Thoughts
- Lecture 28: slides; handout (6up) handout (1up) Final Review: Discrete Math
- Lecture 29: slides; handout (6up) handout (1up) Probability Review

### Discussion Worksheets

Week 1 1A;Sol 1B;Sol Week 2 2A;Sol 2B;Sol Week 3 3A;Sol 3B;/Sol Week 4 4A;Sol 4B;Sol Week 5 N/A 5B;Sol Week 6 6A;Sol 6B;Sol Week 7 7A;/Sol 7B;/Sol Week 8 8A;Sol 8B;Sol Week 9 9A;Sol 9B;Sol Week 10 N/A 10B;Sol Week 11 11A;Sol 11B;Sol Week 12 12A;Sol 12B;Sol Week 13 13A;Sol 13B;Sol Week 14 14A;Sol 14B;Sol

- The discussion sections will not cover new material, but rather will give you additional practice solving problems. You can attend any discussion section you like. However, if there are fewer desks than students, then students who are officially enrolled in that section will get seating priority.
- Short answers or solution sketches will be provided for you to check your solutions. They may not be sufficient to get full credits in homework or exams.

### Exams

Midterm 1 7-9 PM (Feb. 17) Midterm 2 6:30-8:30 PM (Mar. 29) Final Thursday (May 12) 3:00-6:00pm

- You can bring 1, 2, and 3 pages of single sided cheatsheet for Midterm 1, Midterm 2, and Final, respectively.

### Homework

HW Problem Due Date HW Solution Homework 1 January 28, 10PM Solution Homework 2 February 4, 10PM Solution Homework 3 February 11, 10PM Solution Homework 4 February 19, 10PM Solution Homework 5 February 25, 10PM Solution Homework 6 March 3, 10PM Solution Homework 7 March 10, 10PM Solution Homework8 March 23, 10PM Solution Homework 9 March 31, 10PM Solution Homework 10 April 7, 10PM Solution Homework 11 April 14, 10PM Solution Homework 12 April 21, 10PM Solution Homework 13 April 28, 10PM Solution Homework 14 n/a

**No late homework is accepted.**- Homework submission, grading, and regrading will be done through Gradescope. We may sample problems in grading.
- Lowest homework score is dropped.
- Points may be deducted for solutions that are unclear, do not show intermediate work, or are messy or improperly formatted.
- Regrades for homework assignments must be requested through Gradescope within five days 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).
- Homework parties are completely optional. TAs will be present in shifts. 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. 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.
- You are encouraged to work on homework in study groups, but you must write up the solutions on your own. Please check the Department's Policy on Academic Dishonesty. Any student found to be cheating risks automatically failing the class and being referred to the Office of Student Conduct.

### Homework Party/Office Hour Times

### Course Assessment Options

We are allowing students to not do homework if they choose not to have an assessment method for this approach.

You make the choice of how you wish proceed and to be assessed on bcourses after getting feedback on the first homework.

For both options, you are encouraged to access the course resources that are available to you all; help in hw parties, office hours that will be additionally staffed by readers, discussions, and piazza.

The Sundry item below is simply some questionaires which should take roughly half an hour. Both options require them.

#### Test only Option.

- Midterm 1: 25%

- Midterm 2: 25%

- Sundry: 1%

- Final: 49%

#### Homework Option.

- Homework: 15%

- Test-only Score: 85%

#### DISCUSSION OF COURSE OPTIONS

These two configurations correspond to the European test at the end approach, and the standard American approach where we force students to do homework to keep up.

There are clear arguments for each approach, and it is difficult for us to know what will produce the best results for students. This is an endeavor to let you choose.

Regardless of which option you choose, the course staff will support you: put together relevant homeworks for practice, along with solutions, have sections, with section worksheets, and solutions, homework parties, office hours with additional support beyond the teaching assistants, and some tutoring support.

#### The Curve.

We designed the curving methodology to be such you should choose the option that best fits your preferences on how to learn the material and how to organize your time.

### Links

- Piazza: 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. - Gradescope: All homework will be submitted through Gradescope, and all homework and exam grades will be given back through Gradescope.

### Advice

**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 or is zero, we work hard to make them instructive and interesting. Do read the sample solutions, even for the problems on which your recieved full points. 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.