**Professor: ** Sylvie Corteel

**Lectures : ** on Zoom.

**Questions: on Piazza**

**Homeworks: ** upload on gradescope

- Lectures will be a combination of pre-recorded and live elements given during the regularly scheduled lecture time (with total time not exceeding 3 hours per week). All recorded lectures will be posted.
- This course is not set up to allow time conflict enrollment
- Discussions will be hosted live during the scheduled time and students should sign up for a discussion that works for their schedule.
- Midterms and quizzes will be offered during the scheduled lecture time.
- The Final Exam will be offered during the regular Final Exam Group time.

Required text: 8th edition of the textbook Discrete Mathematics and its Applications,
by Kenneth H. Rosen, McGraw-Hill. Information.

**For extra help:** check out the Student Learning Center. You are also welcome to attend
the office hours of the instructor or of ANY GSI.

**ANNOUNCEMENTS: TBD**

- Applications of combinatorics at an Ethiopian restaurant in Berkeley: how many vegetarian combinations are there?

This course provides an introduction to logic and proof techniques, basics of set theory, elementary number theory and cryptography, combinatorial enumeration, discrete probability, and graph theory, with a view towards applications.

All solutions that you submit must be your own work and must not be copied from somewhere else. A solution that is blatantly copied from another source will receive zero credit. There will be serious consequences for repeat offenders. You ARE allowed to discuss the homework problems with other students, but if you do this, you must list at the top of your homework the names of any collaborators. If you used sources besides the textbook, you must list those as well.

There will be one in-class midterm and quizzes. *No books, notes, calculators, scratch paper or collaboration are permitted at any exam*. No make-up midterms will be given; instead, missing midterm scores will be overridden by the final exam score.

The final exam will be on Thursday, December 17, 3-6pm. Note that there are no makeups for the final exam.

Homework TBD, Quizzes TBD, Midterm TBD, Final TBD. Your lowest two homework scores will be dropped. Incomplete grades are rarely given, and only for a documented serious medical problem or genuine personal/family emergency, provided you have a C average on the previous coursework.

Check the College academic calendar, to know the last day to add or drop this course.

Week | Date | Topics | Book | Homework problems |

Week 1 | 08/26, 08/28, 08/31 | Propositional logic, quantifiers, rules of inference | Sections 1.1-1.6 | |

Week 2 | Proof techniques and proof writing | Sections 1.7-1.8 | ||

Week 3 | Sets, functions, countability and uncountable sets | Sections 2.1-2.5 | ||

Week 4 | Division algorithm, modular arithmetic, primes, GCD | Sections 4.1-4.3 | ||

Week 5 | Euclidean algorithm, modular exponentiation, solving congruences, Chinese Remainder Theorem | Sections 4.3-4.4 | ||

Week 6 | Induction and recursion, recursive algorithms | Sections 5.1-5.4; revisit 2.4 for summations | ||

Week 7 | Counting, pigeon hole principle, permutations and combinations, binomial coefficients, distributions, generalized permutations and combinations | Sections 6.1-6.5 | ||

Week 8 | Discrete probability theory, conditional probability, independence, random variables | Sections 7.1-7.2 | ||

Week 9 | Bayes' Theorem and applications. Expected value, variance, Chebyshev's inequality | Sections 7.3-7.4 | ||

Week 10 | Recurrence relations Inclusion-exclusion | Section 8.1-8.2, Section 8.5 | ||

Week 11 | Relations, transitive closure, equivalence relations, set partitions, partial orders | Sections 9.1, 9.4-9.6 | ||

Week 12 | Graphs, isomorphism, connectivity | Sections 10.1-10.4 |

- Homework 1