CS 70 at UC Berkeley

# Discrete Mathematics and Probability Theory

Lecture: MTWTH 3:00pm-4:30pm PDT, Zoom

## Instructor Khalil Sarwari

khalil.sarwari (at) berkeley (dot) edu

Office Hours: TuTh 4:30-5:30 pm

## Instructor Shahzar

shahzar (at) berkeley (dot) edu

Office Hours: M 8-9 pm, W 7-8 pm

### Week 0 Overview

## Logic and Proofs

- Note 0 : Sets and Mathematical Notation
- Note 1 : Propositional Logic
- Note 2 : Proofs
- Note 3 : Induction
- Discussion 01a
- Discussion 01b
- Discussion 01c
- Discussion 01d
- Homework 00

## Notes

There is no textbook for this class. Instead, there is a set of comprehensive lecture notes. Make sure you revisit the notes after every lecture. Each note may be covered in one or more lectures.

When you read the notes, try covering up the proofs and examples and working through them yourself. Only continue reading the notes once you have either figured things out for yourself or gotten stuck. This will give you a much deeper understanding of the material than if you read passively.

See Policies for more information.## Discussions

Discussions will be held over Zoom. The discussion sections are specifically designed to consolidate the material covered in lectures and in the notes. It is highly recommended that you attend all discussions each week. There will be three types of discussion sections: two large discussion sections per day which anyone may attend whenever they want to, a number of small discussion sections which you must sign up for, and pre-recorded discussion videos uploaded to YouTube. If you sign up for a small discussion section, make sure you attend it since TA hours are limited. All discussion sections will cover the same material. See Policies for more information.

- Discussion 01a: Introduction, Logic
- Discussion 01b: Intro to Proofs
- Discussion 01c: Induction, Strong Induction
- Discussion 01d: Sets and Functions

## Homeworks

There will be weekly required homeworks, again designed to consolidate your understanding of the course material. It is highly recommended that you attempt all homeworks. Your lowest homework score will be dropped, but this drop should be reserved for emergencies. No additional allowances will be made for late or missed homeworks: please do not contact us about missed homeworks or late submissions. See Policies for more information.

- Homework 00: Logistics and Review

## Lecture Schedule

- Lecture 1A (6/21): Introduction & Logic
- Lecture 1B (6/22): Proofs
- Lecture 1C (6/23): Induction
- Lecture 1D (6/24): Sets and Functions
- Lecture 2A (6/28): Cardinality and Computability
- Lecture 2B (6/29): Graphs
- Lecture 2C (6/30): Modular Arithmetic 1
- Lecture 2D (7/1): Modular Arithmetic 2
- Lecture Cancelled (7/5): Holiday
- Lecture 3A (7/6): Cryptography
- Lecture 3B (7/7): Polynomials
- Lecture 3C (7/8): Counting 1
- Lecture Cancelled (7/12): Midterm Exam
- Lecture 4A (7/13): Counting 2
- Lecture 4B (7/14): Introduction to Probability
- Lecture 4C (7/15): Conditional Probability
- Lecture 5A (7/19): Independence
- Lecture 5B (7/20): Random Variables
- Lecture 5C (7/21): Variance and Covariance
- Lecture 5D (7/22): Distributions
- Lecture 6A (7/26): Continuous Probability
- Lecture 6B (7/27): Continuous Distributions 1
- Lecture 6C (7/28): Continuous Distributions 2
- Lecture 6D (7/29): Joint Distributions
- Lecture 7A (8/2): Concentration Inequalities 1
- Lecture 7B (8/3): Concentration Inequalities 2, Confidence Intervals
- Lecture 7C (8/4): Markov Chains 1
- Lecture 7D (8/5): Markov Chains 2
- Lecture 8A (8/9): Review
- Lecture 8B (8/10): Review
- Lecture 8C (8/11): Review
- Lecture Cancelled (8/12): Final Exam