Queens CUNY Lockup Mobile Logo

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.

Introduction

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.

The content below is not yet updated for the Spring 2023 semester. Check back later.

Day 4

Learning Objective 1.4. The Language of Logic. I can determine the negation of a proposition, including propositions involving AND or OR. I can convert between a word problem involving real world objects and set notation involving appropriate sets.

Background Reading: Read the first two parts of Section 0.2 (up to but not including Implications). Another resource is the first two pages of this link.

Video 1.3A: Word Problems Involving Sets

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 Cardinality of a union (2 sets).
Section 1.3 up through and including Example 1.3.4.

Video 4.1A: The Additive Principle
Video 4.1B: The Multiplicative Principle
Video 4.2A: Counting Permutations and k-Permutations

Additional Video Resources:
Another video worth watching is The Rules of Sum and Product.
Counting Rules including Sum, Product, and Difference

Additional Video Resources:

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 practical or theoretical word problem involving collections of objects that interact, I can develop an appropriate model for the problem using Venn diagrams of sets. I can apply the principle of counting the complement the Principle of Inclusion and Exclusion to solve counting problems.

Background Reading: Read

Video 1.3B: Applications of Set Operations
Video 1.3C: Applications of Venn Diagrams
Video 4.6A: Principle of Inclusion/Exclusion. (Three-Set PIE starts at timestamp 7:10.)
Video 4.6B: Start at Timestamp 6:20 for two applications of Three-Set PIE

Additional Video Resources:

Optional Textbook Reading:
Epp, Sections 6.1 and 9.3.
Rosen, Section 6.1.

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 4.3A: Counting Combinations
Video 4.3B: Application: Counting Subsets
Video 4.3C: Application: Counting Bit Strings
Video 4.3D: Application: Counting Lattice Paths
Video 4.3E: The Binomial Theorem and Pascal’s Triangle

Additional Video Resources:

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 4.4A: Multisets and Multichoose (You are not responsible for timestamps 3:40-7:20)
Video 4.4B: Counting Multisets
Video 4.4C: Applications of Multisets

Additional Video Resources:

Optional Textbook Reading:
Epp, Section 9.6.
Rosen, Section 6.5.

Day 9

Learning Objective 2.5. Applying the correct method. I can determine whether a real-world scenario concerns ordered or unordered objects and replacement or non-replacement and apply the correct method of counting.

Background Reading: Read Section 1.7.

Video 4.5A: Overview of Counting Techniques
Video 4.5B: Strategies for Solving Counting Problems
Highly recommended video: Many Worked Counting Examples

Additional Video Resources:

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

Day 10

On this day there will be a quiz on learning objectives 2.3, 2.4, and 2.5.

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

Day 11

On this day will be a 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.

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

Additional Video Resources:

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.

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

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

Additional Video Resources:

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 2.4A: Function Images
Video 2.4B: Function Preimages

Additional Video Resources:

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.

 

Video 2.5A: Injective Functions
Video 2.5B: Surjective Functions
Video 2.5C: Bijective Functions
Video 4.2B: Counting Bijections and Injections

Additional Video Resources:

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 integers a and b, I can use the division algorithm to find numbers q and r such that a=qb+r.

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

Video 2.3: Special CS Functions
Video 5.3A: Finding Quotients and Remainders

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

Topic 4: Algebra, Sequences, Series, and Products

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: What are Logarithms?
Video 4.1B: Fundamental Properties of Logarithms
Video 4.1C: Three Rules of Logarithms
Video 3.3D: Converting Between Logarithms of Bases 10, e, and 2.

Additional Video Resources:

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 3.1A: Introduction to Sequences
Video 3.1B: The Formal Definition of a Sequence
Video 3.1C: Computing Terms of a Sequence
Video 3.1D: Closed Form Formulas for Sequences
Video 3.1E: Alternating Sequences

Additional Video Resources:

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 3.2A: Series and Sigma Notation
Video 3.2B: Writing a Sum in Sigma Notation
Video 3.2C: Products and Pi Notation
Video 3.2D: Summing Arithmetic Series
Video 3.2E: More Series and Products
Note: There is an error in Video 3.2E, The special sum SUM_{i=0}^n (2i+1) IS (n+1)^2, NOT n^2. You can verify this by plugging in various values of n.

Additional Video Resources:

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 13. In addition, two-thirds of the way down this post there is a discussion of converting between sigma and pi notation using logarithms. If you are interested in seeing more examples of the manipulations, here is a video that does some sigma notation manipulations and here is a video that does some pi notation manipulations (do be aware: the presenter means the word “product” instead of the word “sum” in the examples).

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

Additional Video Resources:

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: Divisibility and Modular Arithmetic

Day 24

Learning Objective 5.1. 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.1A: Divisibility Basics
(Watch Up to Timestamp 4:40)
Video 5.3B: The Euclidean algorithm
Video 5.3C: Euclidean algorithm Example

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

Day 25

Learning Objective 5.2. 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, and LCM and its relationship with the GCD

Video 5.1A: Divisibility Basics
(Watch Up to Timestamp 4:40)
Video 5.1B: Definition of a Prime
Video 5.1C: Prime Factorization
(Watch Up to Time 5:30.
Continues as Video 5.2B.)
Video 5.1D: Prime Factorization Notation
Video 5.1E: Prime Factorization and Divisors

Additional Video Resources:
Recommended: Properties of the GCD and LCM related to prime factorization
Two worked examples finding all divisors of an integer: (1) No repeated primes (2) With repeated primes
Computing the number of divisors of an integer

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

Day 26

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

Learning Objective 5.3. 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:  Divisibility, GCD, Definition of a prime, Prime Factorization, and LCM and its relationship with the GCD

Video 5.2A: Prime Factorization and GCD, LCM
Video 5.2B: Example using Prime Factorization for GCD
(Continues Video 5.1C at time 5:30)
Video 5.2C: Example using Prime Factorization for LCM

Additional Video Resources:
Recommended: Properties of the GCD and LCM related to prime factorization
Two worked examples finding all divisors of an integer: (1) No repeated primes (2) With repeated primes
Computing the number of divisors of an integer

Optional Textbook Reading:
Rosen, Section 4.3.

Day 27

Learning Objective 5.4. 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. When performing modular arithmetic, I ensure that the same operations are performed on both sides of the congruence.

Background Reading. Modular Arithmetic and Modular Exponentiation

Video 5.4A: Modular Arithmetic
Video 5.4B: Repeated Squaring
Video 5.4C: Techniques of Modular Arithmetic

Additional Video Resources:

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

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.