COURSE OUTLINE
Last Revised: September 2021 Last Reviewed: January 2022
COURSE INFORMATION
Course Title: Discrete Mathematics I Course Number: MACM 101 Credits: 3
Total Weeks: 14 (Fall, Spring) Total Hours: 39 Course Level: ☒ First Year ☐ Second Year
12 (Summer) ☐ New ☐ Revised Course
☐ Replacement Course
Department: Math & Statistics Department Head: G. Belchev Former Course Code(s) and Number(s) (if applicable):
N/A
Pre-requisites (If there are no prerequisites, type NONE): PREC 12 and MATH 100 or MATH 120
Co-requisite Statement (List if applicable or type NONE): NONE
Precluded Courses: N/A
COURSE DESCRIPTION
This course is an introduction to discrete mathematics. Students will examine some areas of mathematics that are frequently
applicable to problems in computer science. Topics include logic and formal reasoning, sets, relations and functions, basic concepts of
number theory, mathematical induction, enumeration, formal languages and automata, and graphs and trees.
LEARNING OUTCOMES
Upon successful completion of the course, students will be able to:
• Logic and Proofs:
a) Write English statements in symbolic form using logical connectives, predicates and quantifiers
b) Use truth tables and logic equivalence to determine the truth value of statements.
c) Use basic logical equivalence to determine if two statements are logically equivalent, prove further logic equivalences
simplify statements, and determine whether a statement is a tautology or a contradiction.
d) Symbolize simple verbal arguments and test their validity using truth tables, logic equivalence and the rules of inference.
e) Formulate short proofs using the methods of direct proof, proof by contraposition, proof by contradiction.
f) Understand how logic is used in the design of digital electronic circuits.
• Sets:
a) Demonstrate a working knowledge of set notation and terminology such as set equality, subsets,
proper subsets, empty set, power set, Cartesian product, union, intersection, complement,
difference and symmetric difference.
b) Prove/disprove statements about sets using Venn-diagrams and logic.
• Relations:
a) Understand binary relations and represent them by a set of ordered pairs, a matrix, a digraph
and a point plot (graph).
b) Obtain new relations from given relations using set operations, composition and inverse.
c) Determine whether a relation is reflexive, symmetric, anti-symmetric, transitive, an equivalence
relation or a partial order relation.
d) Identify the equivalence classes of an equivalence relation.
e) Draw a Hasse diagram for a partial order relation.
• Functions:
a) Demonstrate an understanding of the concepts of function, domain, codomain, range using a
variety of different functions.
b) Determine whether a function is injective, surjective, bijective, invertible.
1 of 4
COURSE OUTLINE
c) Find the composite of functions and the inverse of a function.
d) Use bijection to determine the cardinality of a set, and to determine whether a set is countable
or uncountable
e) Determine the growth of functions using big O, little O and big theta notation.
• Induction and Recursion:
a) Prove the truth of a statement using the principle of mathematical induction, including the
strong form.
b) Use recursion to define functions, sequences, and sets, and use induction to prove statements
about them.
• Integers:
a) Prove statements involving divisibility, the fundamental theorem of arithmetic and prime
numbers.
b) Represent natural numbers using various bases.
c) Calculate greatest common divisor (including with the Euclidean algorithm) and least common
multiple.
d) Prove statements about congruence modulo m and solve linear congruences.
e) Use the Chinese remainder theorem to solve systems of congruences.
• Counting:
a) Use tree diagrams, sum and product rules and inclusion-exclusion for 2 and 3 sets to solve basic
counting problems.
b) Solve counting problems using the pigeon-hole-principle
c) Count unordered selections of distinct objects.
(d) Count ordered arrangements of a set of distinct objects.
e) Count ordered and unordered selections of r objects chosen with or without repetition from a set of n elements.
f) Count the number of arrangements of a set of objects some of which are indistinguishable.
g) Use the binomial theorem
h) Be familiar with the basic concepts of finite probability (experiments, outcomes, sample space, events, probabilities,
properties of probabilities) and use them to calculate probabilities of events.
• Graphs and Trees:
(a) Determine whether a graph is undirected, directed, mixed or weighted.
(b) Represent a graph by its adjacency matrix, incidence matrix and adjacency lists.
(c) Find the degree of a vertex in a graph.
(d) Find walks, trails, path and circuits in a graph
(e) Use Dijkstra’s algorithm to find the shortest path in a weighted undirected graph.
(f) Determine whether a graph is regular, complete, connected, planar, bipartite.
(g) Determine whether two graphs are Isomorphic.
(h) Determine whether a graph is Eulerian/Hamiltonian.
(i) Determine whether a graph is a tree/forest.
(j) Find a minimum spanning tree in a connected, weighted and undirected graph
• Optional Topics
a) Determine whether a string belongs to a language generated by a given grammar.
b) Classify a grammar.
c) Find the language generated by a grammar.
d) Draw a state diagram for a finite state machine.
e) Construct a finite state machine to perform a function.
f) Determine the output of a finite state machine.
2 of 4
COURSE OUTLINE
INSTRUCTION AND GRADING
Instructional (Contact) Hours:
Type Duration
Lecture 39
Seminars/Tutorials
Laboratory
Field Experience
Other (specify):
Total 39
Grading System: Letter Grades ☒ Percentage ☐ Pass/Fail ☐ Satisfactory/Unsatisfactory ☐ Other ☐
Specify passing grade: 50%
Evaluation Activities and Weighting (total must equal 100%)
Weekly Assignments: 10% 3 Midterm Exams: 60% Final Exam: 30%
TEXT(S) AND RESOURCE MATERIALS
Provide a full reference for each text and/or resource material and include whether required/not required.
Discrete Mathematics and Its Applications, Latest edition, Kenneth H. Rosen, McGraw-Hill.
COURSE TOPICS
List topics and sequence covered.
Week Topic
Week 1 Propositional Logic; Digital Logic Circuits; Propositional Equivalence.
Week 2 Arguments; Rules of Inference; Predicates and Quantifiers.
Week 3 Multiple Quantifiers; Arguments with Quantified Statements; Theorems and Proofs.
Week 4 MIDTERM 1; Sets and Set Operations; Representation of Binary Relations
Week 5 Properties of Relations; Equivalence Relations and Equivalence Classes.
Partial Order Relations; Hasse Diagrams; New Relations from Old.
Week 6 Functions; Induction; Recursion; Sequences and Summation.
Week 7 MIDTERM 2; The Basics of Counting; Permutations; Combinations; The Binomial Theorem.
Week 8 Probability; Integers; Division; Primes; GCD, LCM.
Week 9 Euclidean Algorithm; Modular Arithmetic; The Chinese Remainder Theorem.
3 of 4
COURSE OUTLINE
Week 10 MIDTERM 3; Graphs and Trees
Week 11 Graphs and Trees continued
Week 12 Languages and Finite State Machines
Week 13 Languages and Finite State Machines continued
Week 14 FINAL EXAM
NOTES
1. Students are required to follow all College policies. Policies are available on the website at: Coquitlam College Policies
2. To find out how this course transfers, visit the BC Transfer Guide at: bctransferguide.ca
4 of 4
