CS 70 at UC Berkeley

# Discrete Mathematics and Probability Theory

Lectures: Tu/Th 12:30-2 pm, Wheeler 150

## Professor Alistair Sinclair

sinclair (at) berkeley (dot) edu

Office Hours: M 1-2 pm, Tu 2:15-3:15 pm, 677 Soda

## Professor Yun S. Song

yss (at) berkeley (dot) edu

Office Hours: M 11 am - 12 pm, 629 Soda; Tu 5-6 pm, 304B Stanley Hall

### Week 0 Overview

## Propositional Logic

### Week 1 Overview

## Proofs, Induction

### Week 2 Overview

## Stable Marriage, Graphs

### Week 3 Overview

## Graphs, Modular Arithmetic

### Week 4 Overview

## RSA, Polynomials

## 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, and multiple times thereafter: you should be aware that it will likely take several readings before you fully understand the material. Each note may be covered in one or more lectures. See Policies for more information.

- Note 0: Review of Sets, Notation
- Note 1: Propositional Logic
- Note 2: Proofs
- Note 3: Induction
- Note 4: Stable Marriage
- Note 5: Graph Theory
- Note 6: Modular Arithmetic
- Note 7: Public Key Cryptography
- Note 8: Polynomials

## Discussions

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 will be admitted to the section on a first-come first-served basis and others will have to attend an alternative section. See Policies for more information.

- Discussion 00b: Propositional Logic (solution)
- Discussion 01a: Proofs (solution)
- Discussion 01b: Induction (solution)
- Discussion 02a: Stable Marriage (solution)
- Discussion 02b: Graphs I (solution)
- Discussion 03a: Graphs II (solution)
- Discussion 03b: Modular Arithmetic I (solution)
- Discussion 04a: Modular Arithmetic II (solution)
- Discussion 04b: RSA (solution)

## Homeworks

Homeworks are graded for accuracy and it is highly recommended that you do them. Your lowest **two** homework scores will be dropped, but these drops 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.

- HW 00: Course Logistics (TeX) (Sol)
- HW 01: Propositional Logic, Proofs (TeX) (Sol)
- HW 02: Induction, Stable Marriage (TeX) (Sol)
- HW 03: Graphs (TeX) (Sol)
- HW 04: Modular Arithmetic (TeX)
- HW 05: RSA (TeX)

## Lecture Schedule

- Lec 1 (8/23): Intro & Propositional Logic ( Note 1 )
- Lec 2 (8/28): Proofs ( Note 2 )
- Lec 3 (8/30): Induction ( Note 3 )
- Lec 4 (9/4): Stable Marriage ( Note 4 )
- Lec 5 (9/6): Graph Theory I ( Note 5 )
- Lec 6 (9/11): Graph Theory II ( Note 5 )
- Lec 7 (9/13): Modular Arithmetic ( Note 6 )
- Lec 8 (9/18): RSA ( Note 7 )
- Lec 9 (9/20): Polynomials ( Note 8 )