# 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

**Optional Textbook Reading:**

Epp, Sections 1.2 and 6.1.

Rosen, Section 2.1.

## 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

**Additional Video Resources:**

Set Theory: Applications and De Morgan’s Laws

**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

**Additional Video Resources:**

Another video worth watching is The Rules of Sum and Product.

The Additive Principle and The Multiplicative Principle

Counting Rules including Sum, Product, and Difference

Worked Permutation Examples

**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.

**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 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

**Additional Video Resources:**

An introduction to Combinations.

Binomial coefficients and the binomial theorem. (Up to timestamp 19:42.)

Many worked examples of combinations

**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

**Additional Video Resources:**

Introduction to Multisets

Multichooses (Up to timestamp 17:20.)

Combinations with Repetition Worked Examples

A discussion of Stars and Bars on Numberphile!

Another explanation of stars and bars

A multichoose example

**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 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

**Additional Video Resources:**

Domain and range of a function defined as a table, graph, or arrow diagram

**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 log_{2}, ln, and log_{10}.

**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

**Additional Video Resources:**

Basics of Logarithms

Fundamental Properties of Logarithms

Three Rules of Logarithms

**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

**Additional Video Resources:**

Introduction to Sequences

The formal definition of a sequence

**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 *Z _{n}*. I can find powers of numbers in

*Z*by applying rules of exponents, the technique of repeated squaring, and Fermat’s Little Theorem.

_{n}**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

**Additional Video Resources:**

Modular Arithmetic

The Method of Repeated Squaring

Techniques of Modular Arithmetic

**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

**Additional Video Resources:**

Definitions of a Prime and 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

Examples of computing number of 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

**Additional Video Resources:**

Recommended: Properties of the GCD and LCM related to prime factorization

Example computing GCD from Prime Factorizations (Starts at time 5:30)

Example computing LCM from Prime Factorizations

**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.