# 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.1B: Notation and The Notation Exercise

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

A definition of even and odd integers

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.2E: Set-builder Notation

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.

Also recommended is Hammack’s Book of Proof. See Sections 1.5, 1.6, 1.2, and 1.4.

##### Video 1.3C: Venn Diagrams

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

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.2A: Counting Permutations and k-Permutations

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

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.

##### Video 4.6B: Start at Timestamp 6:20 for two applications of Three-Set PIE

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

##### Video 4.3E: The Binomial Theorem and Pascal’s Triangle

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

##### Video 4.4C: Applications of Multisets

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.

##### Highly recommended video: Many Worked Counting Examples

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.1C: When is a Rule a Function?

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.2B: Finding the Range of a Function

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.4B: Function Preimages

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 4.2B: Counting Bijections and Injections

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.

##### Video 5.3A: Finding Quotients and Remainders

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 3.3D: Converting Between Logarithms of Bases 10, e, and 2.

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.1E: Alternating Sequences

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

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

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

## 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.3C: Euclidean algorithm Example

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.1E: Prime Factorization and Divisors

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

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.2C: Example using Prime Factorization for LCM

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

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.4C: Techniques of Modular Arithmetic

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.