Math 55 - Discrete Mathematics - Fall 2020

Lectures: MWF 2:00-3-00pm online

Professor: Sylvie Corteel

Lectures : on Zoom.

Office Hours: on Zoom.

Questions: on Piazza

Homeworks: upload on gradescope

Quizzes: on bCourses

Teaching assistants:



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

Course control number: 22283

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.


Quizzes: TBD, Midterm: TBD, Final Exam: Thurs 12/17/20 3–6 pm

For fun

Enrollment questions

Section enrollment/changes are performed via CalCentral. The instructors and GSIs have no control over enrollment. Because GSIs already face a heavy workload, you may not attend a discussion section that you are not registered for.

Course description

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.

Problem Sets

Homework will be assigned weekly. About twenty problems covering the lecture material of each week will be due the following week. The homeworks will be uploaded and graded on gradescope. No late homework can be accepted. Your GSI will verify that you are working the assigned problems, but only one or two of the problems (marked after the due date by a star) is fully graded. Homework solutions will be posted on the due date.

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.


This course covers a tremendous amount of material, so it's imperative that students prepare for each lecture by reading the assigned sections in advance. In lecture, I will outline what is important, give my own perspective on some topics, present examples.


WeekDateTopics BookHomework problems
Week 1 08/26, 08/28, 08/31Propositional 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 Assignments