Welcome to MATH 120

Discrete Mathematics for Computer Science

MATH 120 provides fluency in foundational mathematical concepts that appear in future courses in computer science.
This course is destined for computer science majors; it does not count toward a major in mathematics.

On this page you will find the video lectures for this class and the sections of the textbook you should be reading for each day of the semester. 
You are expected to read the indicated textbook sections and watch the videos each day BEFORE class.

The textbook for this class is the OER text Discrete Mathematics: An Open Introduction.

Additional optional textbook resources are provided below the day’s videos. They reference the textbooks Discrete Mathematics with Applications by Susanna Epp (5th edition) and Discrete Mathematics and Its Applications by Kenneth Rosen (7th edition).

Use your class discussion board to ask questions about the videos and other topics from the course.


Welcome to MATH 120

What is Discrete Mathematics? Read more in our textbook and on Wikipedia.

Topic 1: Sets

Day 1

Learning Objective 1.1. Definitions and Notation. I understand the concepts of definitions and notation. Given a mathematical term, I can write down the precise definition, my personal understanding, an example, and a non-example. Given a mathematical symbol, I can understand its context in a mathematical expression, and translate its meaning and use into English.

Video 1.1A: Definitions and 
The Definition Exercise
Video 1.1B: Notation and 
The Notation Exercise

Dive deeper: Read more about definitions on this website and on Wikipedia.

Additional Video Resources:
A definition of even and odd integers

Optional Textbook Reading:
Epp, Sections 1.1, 1.2, and 4.4.
Rosen, Section 2.1.

Day 2

Learning Objective 1.2. Set Notation. I can represent a set in roster notation and set-builder notation. I can determine if an object is an element of a set. I can determine whether two sets are equal or subsets of one another. I understand the difference between a finite and infinite set.

Background Reading: Read Section 0.3 of our textbook up to but not including the part labeled “Operations on Sets”.
Also recommended is Hammack’s Book of Proof. See Sections 1.1 and 1.3.

Video 1.2A: The Definition of a Set
Video 1.2B: More about sets
Video 1.2C: Equality and Containment
Video 1.2D: Example: Which Sets are Contained in Each Other?
Video 1.2E: Set-builder Notation

Day 3

On this day there will be a quiz on learning objectives 1.1 and 1.2.

Learning Objective 1.3. Set Operations and Venn Diagrams. I can perform operations on sets (intersection, union, complement, difference) and represent the operations as Venn Diagrams. I can compute the power set of a set and the Cartesian product of multiple sets.

Background Reading: Read the remainder of Section 0.3 of our textbook.
Also recommended is Hammack’s Book of Proof. See Sections 1.5, 1.6, 1.2, and 1.4.

Video 1.3A: Relationships between sets
Video 1.3B: Cartesian Products and the Power Set
Video 1.3C: Venn Diagrams

Optional Textbook Reading:
Epp, Sections 1.2, 6.1, and 6.2.
Rosen, Sections 2.1 and 2.2.

Day 4

Learning Objective 1.4. Set Operations as English Language. I can convert between real-world situations involving collections of objects and abstract expressions involving sets. I can determine the English equivalent of the complement of a set. I can apply De Morgan’s Laws when finding the complements of expressions involving AND or OR.

Background Reading: This page has information about translating between English words and set operations. There are sections on “Subsets and the words ‘all’ and ‘if … then’”, “Complement and the word ‘not’”, “Intersection and the word ‘and’”, and lastly, “Union and the word ‘or’”. Learn more about De Morgan’s Laws.

Video 1.4A: Solving Word Problems & Word Problems Involving AND
Video 1.4B: Word Problems Involving OR
Video 1.4C: Word Problems Involving Negation
Video 1.4D: Word Problems Involving Sequences and Subsets
Video 1.4E: Word Problems Involving Conditioning

Optional Textbook Reading:
Epp, Sections 1.1, 6.2, and 6.3.
Rosen, Sections 1.1 and 2.2.

Topic 2: Combinatorics

Day 5

On this day there will be a quiz on learning objectives 1.3 and 1.4.

Learning Objective 2.1. Addition, Multiplication, and Permutations. I can use the additive principle when counting disjoint sets. I can use the multiplicative principle when counting sequences of independent events. I can count the number of permutations and k-permutations of a set of n objects.

Background Reading: Read Section 1.1, up to and including Multiplicative Principle (with sets).
Section 1.3 up through but not including Example 1.3.4.

Video 2.1A: Introduction to Combinatorics
Video 2.1B: The Addition Principle
Video 2.1C: The Multiplication Principle
Video 2.1D: When the Multiplication Principle Doesn’t Work
& Combining the Principles
Video 2.1E: Counting Permutations and k-Permutations

Optional Textbook Reading:
Epp, Sections 9.1, 9.2, and 9.3.
Rosen, Sections 6.1, 6.3, and 6.5.

Day 6

Learning Objective 2.2. Applications of Venn Diagrams. Given a counting word problem, I can develop an appropriate model involving set notation and Venn diagrams. I can apply the Principle of Counting the Complement and the Principle of Inclusion and Exclusion to solve counting problems.

Background Reading: Read the remainder of Section 1.1, starting with the subsection on the Principle of Inclusion/Exclusion. You may wish to refresh your understanding of sets and set operations as discussed on Days 3 and 4.

Video 2.2A: Counting the Complement
Video 2.2B: Applying Venn Diagrams to Counting Questions
Video 2.2C: The
Principle of Inclusion/Exclusion.

Day 7

On this day there will be a quiz on learning objectives 2.1 and 2.2.

Learning Objective 2.3. Combinations and Binomial Coefficients.I can count the number of ways to choose k objects from a group of n objects when repetition IS NOT allowed. I can count the number of bit strings of length n and weight k. I understand how these two concepts are related. I can calculate the binomial coefficient (n choose k). 

Background Reading: Read Section 1.2 and Section 1.3 starting here.

Video 2.3A: Counting Combinations
Video 2.3B: Application: Counting Subsets
Video 2.3C: Application: Counting Bit Strings
Video 2.3D: Application: Counting Lattice Paths
Video 2.3E: The Binomial Theorem and Pascal’s Triangle

Optional Textbook Reading:
Epp, Sections 5.1, 9.5, and 9.7.
Rosen, Sections 6.3, 6.4, and 6.5.

Day 8

Learning Objective 2.4. Multicombinations. I can count the number of ways to choose k objects from a group of n objects when repetition IS allowed. I can use the “stars and bars” method to count the number of ways to distribute objects among a group. I can calculate (n multichoose k).

Background Reading: Read Section 1.5.

Video 2.4A: Multisets and Multichoose
Video 2.4B: Counting Multisets
Video 2.4C: Applications of Multisets

Day 9

Learning Objective 2.5. Applying the correct method. I can determine whether a real-world scenario involves ordered or unordered objects, distinct or identical objects, and whether repetition is allowed or not allowed. I can then apply the correct method of counting.

Background Reading: Read Section 1.7.

Video 2.5A: Overview of Counting Techniques
Video 2.5B: Key Words Appearing in Counting Problems
Video 2.5C: Strategies for Solving Counting Problems

Additional Video Resources:
Highly Recommended: Many Worked Counting Problems

Optional Textbook Reading:
Epp, Section 9.6.
Rosen, Sections 6.5 and 6.6.

Day 10

Either on Day 10 or Day 11, there will be a quiz on learning objectives 2.3, 2.4, and 2.5.

There are no new video lectures for today.

The remainder of the class period: More practice with counting problems.

Day 11

Either on Day 10 or Day 11, there will be a quiz on learning objectives 2.3, 2.4, and 2.5.

The remainder of the class period: Review session for the first midterm.

Day 12

On this day is Midterm 1, covering Learning Objectives 1.1-1.4 and 2.1-2.5.

Topic 3: Functions

Day 13

Learning Objective 3.1. Defining Functions. I can determine whether a rule described in words is a function, including whether it is well defined.

Background reading: Read the sections of Chapter 0.4 up to but not including the definition of Recursively Defined Functions.

Video 3.1A: Definition of a Function
Video 3.1B: Describing Functions
Video 3.1C: When is a Rule a Function?

Additional Video Resources:
Describing Functions (Video working through our textbook)
What makes a function well defined?
Introduction to Functions

Optional Textbook Reading:
Epp, Sections 1.3 and 7.1.
Rosen, Sections 2.3.

Day 14

Learning Objective 3.2. Domain, Range, and Codomain. I can determine the domain, range, and codomain of a function, especially a discrete function defined using words.

Background Reading: Read the beginning of Chapter 0.4, which discusses domains, codomains, and ranges.

Video 3.2A: Domain, Codomain, and Range
Video 3.2B: Finding the Range of a Function

Optional Textbook Reading:
Epp, Section 7.1.
Rosen, Section 2.3.

Day 15

On this day there will be a quiz on learning objectives 3.1 and 3.2.

Learning Objective 3.3. Images and Preimages. I can determine the image of an element in the domain and a preimage of an element in the codomain.

Background Reading: Read the section of Chapter 0.4 that discusses images and pre-images.
Note: The book uses the words inverse image to mean the same thing as pre-image.


Video 3.3A: Function Images
Video 3.3B: Function Pre-images

Additional Video Resources:
Images and Pre-images (Working through our textbook)

Optional Textbook Reading:
Epp, Section 7.2.
Rosen, Section 2.3.

Day 16

Learning Objective 3.4. Injective, Surjective, and Bijective Functions. I can determine whether a function is injective, surjective, or bijective.

Background Reading: Read the section of Chapter 0.4 that discusses Surjections, Injections, and Bijections.
Read these two examples: Counting Bijections and Counting Injections.

Video 3.4A: Injective Functions
Video 3.4B: Surjective Functions
Video 3.4C: Bijective Functions
Video 3.4D: Applications of Bijections
Video 3.4E: Counting Bijections and Injections

Additional Video Resources:
Surjective, Injective, and Bijective Functions (Working through our textbook)
Identifying Injective, Surjective, and Bijective Functions (Example 1) (Example 2)
Injective, Surjective, and Bijective functions
Counting Injective Functions

Optional Textbook Reading:
Epp, Sections 4.5, 4.6, and 5.1.
Rosen, Sections 2.3 an 4.1.

Day 17

On this day there will be a quiz on learning objectives 3.3 and 3.4.

Learning Objective 3.5. Special Functions. I can evaluate special computer science functions: floor, ceiling, factorial, DIV (//), and MOD (%).
Given an integer a and a positive integer b, I can find integers q and r such that a=qb+r and 0≤r<b.

Background Reading: Here is more information about the floor and ceiling and DIV and MOD functions.

Video 3.5A: Rounding, Floor, and Ceiling
Video 3.5B: Factorials
Video 3.5C: Quotients, Remainders, DIV, and MOD

Optional Textbook Reading:
Epp, Sections 4.5 and 4.10.
Rosen, Sections 4.1 and 4.3.

Topic 4: Algebra, Sequences, Series, and Products

Video 4.0: Introduction to Topic 4

Day 18

 Learning Objective 4.1. Exponents and Logarithms. I can convert between expressions involving exponents and expressions involving logarithms. I can apply exponential and logarithmic rules to expand or simplify expressions. I can convert between log2, ln, and log10.

Background Reading: This topic is not in our textbook. If you need a refresher about exponents and rules of exponents, here is a textbook section to read and here is a no-frills video. For logarithms, here is a textbook with a detailed explanation about logarithm basics and rules of logarithms and here is a different textbook with less-detailed explanations about logarithm basics and rules of logarithms. In addition to the videos shared here, there are many videos online with examples of solving exponential and logarithmic equations.

Video 4.1A: Exponents
Video 4.1B: Rules of Exponents
Video 4.1C: Logarithmic Functions
Video 4.1D: Converting Between Logarithms of Bases 10, e, and 2

Optional Textbook Reading:
Epp, Sections 7.1 and 7.2.
Rosen, Appendix A2.

Day 19

Learning Objective 4.2. Sequences. If I am given a function (as a formula or in words) that defines a sequence, I can determine the value of a specified term of the sequence. If I am given a constant sequence, arithmetic sequence, geometric sequence, or alternating sequence written using ellipses, I can find a formula for the sequence. I can determine the number of terms in a finite sequence

Background Reading: Read Chapter 2.1 (ignoring discussion of recursion) and the section of Chapter 2.2 that discusses arithmetic and geometric sequences

Video 4.2A: Sequences
Video 4.2B: Computing Terms of a Sequence
Video 4.2C: Closed Form Formulas for Sequences
Video 4.2D: Alternating Sequences

Optional Textbook Reading:
Epp, Sections 5.1 and 9.1.
Rosen, Sections 2.4.

Day 20

On this day there will be a quiz on learning objectives 4.1 and 4.2.

Learning Objective 4.3. Series and Products. I can write a finite or infinite sum in sigma notation. I can write a finite or infinite product in pi notation. I can interpret an expression written in sigma or pi notation correctly. I can find the sum of a finite arithmetic series. I can find the sum of a finite or infinite geometric series.

Background Reading: Our textbook discusses these topics in a very limited fashion in Section 2.1 and Section 2.2. Here is a simple explanation about sigma and pi notation. Here is a more detailed explanation of sigma notation. Here there is a discussion about sigma, pi, and set intersection notation. Here is a nice interpretation of sigma and pi notation in code

Video 4.3A: Series and Sigma Notation
Video 4.3B: Writing a Sum in Sigma Notation
Video 4.3C: Products and Pi Notation
Video 4.3D: Summing Arithmetic Series
Video 4.3E: Summing Geometric Series
Video 4.3F: Special Sums and Products, and a Discussion about Indices

Additional Video Resources:
Introduction to Sigma and Pi notation

Optional Textbook Reading:
Epp, Sections 5.1 and 5.2.
Rosen, Section 2.4.

Day 21

Learning Objective 4.4. Σ and 𝚷 Manipulations. I can do sigma and pi manipulations involving sums, products, exponentiation, and logarithms.

Background Reading: See the background reading from Day 20. In addition, two-thirds of the way down this post there is a discussion of converting between sigma and pi notation using logarithms

Video 4.4A: Sigma Notation Manipulations
Video 4.4B: Pi Notation Manipulations
Video 4.4C: Exponentiation and Logarithms with Sigma and Pi Notation

Additional Video Resources:
Sigma notation manipulations
Pi notation manipulations (Careful: the presenter means “product” instead of “sum”).

Day 22

On this day there will be a quiz on learning objectives 4.3 and 4.4.

The remainder of the class will be a review session for the second midterm.

Day 23

On this day is Midterm 2, covering Topics 3 and 4.
In other words, Midterm 2 assesses Learning Objectives 3.1-3.5 and 4.1-4.4.
This exam is not cumulative: It does not assess content that was assessed in Midterm 1.

Topic 5: Modular Arithmetic and Divisibility

Video 5.0: Introduction to Topic 5

Day 24

Learning Objective 5.1. Modular Arithmetic.  I can add, subtract, and multiply numbers in Zn. I can find powers of numbers in Zn by applying rules of exponents, the technique of repeated squaring, and Fermat’s Little Theorem.

Background Reading. Congruence mod n, Modular Arithmetic and Modular Exponentiation.

Video 5.1A: Introduction to Modular Arithmetic
Video 5.1B: Addition and Multiplication Modulo m
Video 5.1C: Exponentiation
Modulo m

Optional Textbook Reading:
Epp, Sections 4.5, 5.3, and 8.4.
Rosen, Sections 4.1.

Day 25

Learning Objective 5.2. Divisibility, GCD, and the Euclidean Algorithm I can determine if one number divides another. I understand the concept of the GCD of two numbers. I can use the Euclidean algorithm to find the GCD of two given numbers.

Background Reading: Divisibility Basics, GCD, Read Sections 11.4.1 and 11.4.2 of Applied Discrete Structures by Al Doerr and Ken Levasseur.

Video 5.2A: Divisibility
Video 5.2B: The Greatest Common Divisor and Least Common Multiple
Video 5.2C: The Euclidean Algorithm

Optional Textbook Reading:
Epp, Sections 4.5, 4.10, and 5.5.
Rosen, Sections 4.1 and 4.3.

Day 26

On this day there will be a quiz on learning objectives 5.1 and 5.2.

Learning Objective 5.3. Prime Factorization. I can determine the prime factorization of a positive integer and use this information to determine all divisors of an integer.

Background Reading:  Definition of a prime, Prime Factorization, Finding all divisors of a number, and computing the number of divisors of a number.

Video 5.3A: Prime Factorization
Video 5.3B: Prime Factorization and Divisors

Optional Textbook Reading:
Epp, Section 4.4.
Rosen, Section 4.3.

Day 27

Learning Objective 5.4. GCD and LCM via Prime Factorization. I can use the prime factorizations of two positive integers to determine the GCD and LCM of those numbers.

Background Reading:  LCM and its relationship with the GCD

Video 5.4A: GCD and LCM via Prime Factorization
Video 5.4B: Relatively Prime Numbers

Optional Textbook Reading:
Rosen, Section 4.3.

Day 28

On this day there will be a quiz on learning objectives 5.3 and 5.4.

The remainder of the class will be a review session for the final exam.

Final Exam Day

Congratulations! You’ve made it to the end of the semester.

Your instructor will inform you about when and where the final exam will be held.

The final exam IS cumulative. There will be questions assessing learning objectives from throughout the semester, including divisibility and modular arithmetic. Make sure you remember to study the materials from the beginning of the semester with your study group.

Course Acknowledgments

This course is the product of a collaboration between the Queens College Departments of Mathematics and Computer Science. We gratefully acknowledge the open education resources community, including the textbook author Oscar Levin, and the Grading for Growth community, especially Robert Talbert and his course on Discrete Structures for Computer Science at Grand Valley State University, which served as an inspiration for the structure of this course and much of its content.

Course content was created by Christopher Hanusa, Moshe Adrian, David Miller, Steven Goldman, Wjeewani Boteju, Kirsten Berger, and Adam Wang. This webpage was developed by Christopher Hanusa.