Jean Walrand

email: walrand at berkeley (.) edu

Office: 257 Cory Hall.

Office hours:

M 2:30-3:30.

W 2:30-3:30.

Satish Rao

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

Office: 687 Soda Hall.

Office hours:

M 2:30-3:30.

Th 2:00-3:00.

Please see the Reader/Tutor page for information about your Readers.

- 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: Counting
- Note 11: Infinity and Uncountability
- Note 12: Self-Reference and Uncomputability
- 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 21: Inference
- Note 22: Zipf's Law and power law distributions
- Note 23: How to lie with probability
- Note 24: Linear regression and conditional expectation

On Calcentral! The first lecture appears to be up!

Slides follow the notes, but I do try to pull out what I garner from my own close reading, re-reading, and re-reading (and occasional edit) of the notes to both prepare lectures and these slides.

- Lecture 1: slides; handout (6up) handout (1up) Propositions.
- Lecture 2: slides; handout (6up) handout (1up) Proofs.
- Lecture 3: slides; handout (6up) handout (1up) Induction.
- Lecture 4: slides; handout (6up) handout (1up) More Induction
- Lecture 5: slides; handout (6up) handout (1up) Stable Marriage
- Lecture 6: slides; handout (6up) handout (1up) Graph Theory to Eulerian Tour
- Lecture 7: slides; handout (6up) handout (1up) Graph Theory: complete, tree, and hypercube.
- Lecture 8: slides; handout (6up) handout (1up) Modular Arithmetic: Intro
- Lecture 9: slides; handout (6up) handout (1up) Modular Arithmetic: Extended Euclid
- Lecture 10: slides; handout (6up) handout (1up) Midterm Review
- Lecture 11: slides; handout (6up) handout (1up) RSA intro/Fermate
- Lecture 12: slides; handout (6up) handout (1up) RSA, Fermat, Correctness.
- Lecture 13: slides; handout (6up) handout (1up) Polynomials for Secret Sharing..
- Lecture 14: slides; handout (6up) handout (1up) Polynomial Reconstruction is Unique...
- Lecture 15: slides; handout (6up) handout (1up) Polynomials for Erasure Coding..
- Lecture 16: slides; handout (6up) handout (1up) Berlekamp-Welsh decoding!.
- Lecture 17: slides; handout (6up) handout (1up) Counting: first and second rules.
- Lecture 18: slides; handout (6up) handout (1up) Counting: stars and bars and combinatorial proofs.
- Lecture 19: slides; handout (6up) handout (1up) Countable and uncountable.
- Lecture 21: slides; handout (6up) handout (1up) Midterm Review 2
- Lecture 22: slides; handout (6up) handout (1up) Probability space, events.
- Lecture 23: slides; handout (6up) handout (1up) Learning from observations.
- Lecture 24: slides; handout (6up) handout (1up) Changing your mind?
- Lecture 25: slides; handout (6up) handout (1up) Collisions/Collecting
- Lecture 26: slides; handout (6up) handout (1up) Rand Variables
- Lecture 27: slides; handout (6up) handout (1up) Expectation
- Lecture 28: slides; handout (6up) handout (1up) Independence and Variance
- Lecture 29: slides; handout (6up) handout (1up) Variance and Coupons
- Lecture 30: slides; handout (6up) handout (1up) Markov, Chebyshev, Mini-Review
- Lecture 31: slides; handout (6up) handout (1up) Midterm Review 3
- Lecture 32: slides; handout (6up) handout (1up) Chernoff, ..., confidence intervals
- Lecture 33: slides; handout (6up) handout (1up) Linear Regression
- Lecture 34: slides; handout (6up) handout (1up) Conditional Expectation
- Lecture 35: slides; handout (6up) handout (1up) Continuous Probability
- Lecture 36: slides; handout (6up) handout (1up) Gaussian and CLT
- Lecture 37: slides; handout (6up) handout (1up) Statistics are confusing; next.
- Lecture 39: slides; handout (6up) handout (1up) Walrand final review.

Week 1 No Discussion. Week 2 2A;/Sol 2B;/Sol Week 3 3B;/Sol Week 4 4A;/Sol 4B;/Sol Week 5 Midterm 1 5B;/Sol Week 6 6A;/Sol 6B;/Sol Week 7 7A;/Sol 7B;/Sol Week 8 8A;/Sol 8B;/Sol Week 9 Midterm 2 9B;/Sol Week 10 10A;/Sol 10B;/Sol Week 11 11A;/Sol 11B;/Sol Week 12 12A;/Sol 12B;/Sol Week 13 Midterm 3 13B;/Sol Week 14 14A;/Sol Week 15 15A;/Sol 15B;/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.

Midterm 1 Monday (Sep 21) 8:00-9:30pm Midterm 2 Monday (Oct 19) 7:00-8:30pm Midterm 3 Monday (Nov 16) 7:00-8:30pm Final Tuesday (Dec 15) 11:30-2:30pm

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

HW Problem Due Date HW Solution Homework 14 NA Homework 13 Dec 2 (Wed) 10:00 PM Homework 12 Nov 18 (Wed) 10:00 PM Homework 11 Nov 11 (Wed) 10:00 PM Homework 10 Nov 04 (Wed) 10:00 PM Homework 9 Oct 28 (Wed) 10:00 PM Homework 8 Jan 26 (Mon) 12:00 PM Homework 7 Oct 14 (Wed) 10:00 PM Homework 6 Oct 7 (Wed) 10:00 PM Homework 5 Sep 30 (Wed) 10:00 PM Homework 4 Sep 23 (Wed) 10:00 PM Homework 3 Sep 16 (Wed) 10:00 PM Homework 2 Sep 9 (Wed) 10:00 PM Homework 1 Sep 2 (Wed) 10:00 PM

**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.

We are allowing students the choice of how to best approach the class and have designed an assessment method for each approach.

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

For all 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.

** At that point, the die is cast and you
cannot change your choice. **

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

- Midterm 1: 18%

- Midterm 2: 18%

- Midterm 3: 18%

- Sundry: 1%

- Final: 45%

- Homework: 15%

- Test-only Score: 85%

- Tutor grade: 15%

- Test-only Score: 85%

Th last option needs a bit of explaining. After each homework solution is out, each student in this category should read and understand the solutions to the homework, and then should meet with a oral quiz tutor who will test whether you understand the homework material. She or he will either check you off, or help you understand more, and ask you to try again either at that point, or after you go back and try to understand better on your own. The expectation is that the tutor option grade is 100\%.

These three configurations correspond to the European test at the end approach, the standard American approach where we force students to do homework to keep up, and the last moves toward checking in personally which has support in the education literature. To be sure, this is a brief summary of the thinking behind this.

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.

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.

Still, you may visit piazza to understand the curve. My feeling is that one question on a midterm or final makes more of a difference to your grade than the specifics of the curve, so your energy is better spent on making sure your learn the material.

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