# Discrete Mathematics I

Faculty
Science & Technology
Department
Mathematics
Course Code
MATH 1130
Credits
3.00
Semester Length
15 weeks
Max Class Size
35
Method Of Instruction
Lecture
Tutorial
Typically Offered
Fall
Winter
Campus
Online

## Overview

Course Description
This is the first of two Discrete Mathematics courses for Computing Science students. Topics include logic, set theory, functions, algorithms, mathematical reasoning, recursive definitions, counting and relations.
Course Content
1. Logic
2. Set Theory
3. Functions
4. Algorithms, Integers and Matrices
5. Mathematical Reasoning and Recursive Definitions
6. Counting
7. Relations

Optional Topics

1. Graphs and Trees
2. Languages and Finite State Machines
Methods Of Instruction

Lectures, problem sessions, tutorial sessions and assignments

Means of Assessment

Evaluation will be carried out in accordance with Douglas College policy.  The instructor will present a written course outline with specific evaluation criteria at the beginning of the semester.  Evaluation will be based on some of the following:

 Weekly tests 0-40% Mid-term tests 20-70% Assignments 0-15% Attendance 0-5% Class participation 0-5% Tutorials 0-10% Final examination 30-40%
Learning Outcomes

At the end of the course, the successful student should be able to:

• write English statements in symbolic form using prepositional variables or functions, logical connectives and any necessary quantifiers;
• determine the truth value of a statement under an interpretation;
• determine the negation, converse, inverse, and contrapositive of a statement;
• verify logical equivalencies;
• demonstrate an understanding of tautologies, contradictions and duals;
• prove the properties of logic;
• determine the cardinality of sets, subsets, power sets and Cartesian products;
• combine sets using the set operators;
• prove set identities using a series of known set identities or by showing that each expression is a subset of the other;
• use membership tables or Venn diagrams to prove set identities;
• classify functions as injective, surjective or bijective;
• demonstrate an understanding of domains, codomains, ranges, mappings and images;
• create new functions by composition;
• find the inverse of an injective function;
• demonstrate an understanding of the floor and ceiling functions;
• compute finite sums;
• give a big-O estimate for a function;
• write a simple algorithm in pseudocode;
• determine the time complexity of simple algorithms;
• demonstrate an understanding of divisibility, the greatest common divisor and modular arithmetic;
• use the Euclidean algorithm to find the gcd of two numbers;
• convert between binary, octal and hexadecimal;
• demonstrate an understanding of the rules of inference;
• analyze an argument as to its validity using the concepts of mathematical logic;
• use a direct proof, indirect proof, or contradiction to prove a mathematical theorem;
• prove mathematical theorems using formal inductive techniques;
• give a recursive definition of a function or a set;
• use the sum and product rules and tree diagrams to solve basic counting problems;
• apply the inclusion-exclusion principle to solve counting problems for two tasks;
• solve counting problems using the Pigeon-Hole Principle;
• count unordered selections of distinct objects;
• count ordered arrangements of a set of disctinct objects;
• count ordered and unordered selections of r objects chosen with or without repetition from a set of elements;
• count the number of arrangements of a set of objects some of which are indistinguishable;
• find the expansion of a binomial;
• determine the probability of a combination of events for an equi-probable sample space;
• determine whether or not a relation is reflexive, irreflexive, symmetric, antisymmetric and or transitive;
• represent a relation as a matrix and a digraph;

Optional Topics:

• determine whether a string belongs to the language generated by a given grammar;
• classify a grammar;
• find the language created by a grammar;
• draw the state diagram for a finite-state machine;
• construct a finite-state machine to perform a function;
• determine the output of a finite state machine;
• demonstrate an understanding of the vocabulary of graph theory;
• determine whether a graph is bi-partite or not;
• represent a graph as an adjacency matrix and an incidence matrix;
• determine whether a pair of graphs are isomorphic;
• find circuits and paths in a graph;
Textbook Materials

Consult the Douglas College Bookstore for the latest required textbooks and materials.

Example textbooks and materials may include:

Rosen, H.R., Discrete Mathematics and Its Applications, current edition, McGraw Hill.

Grimaldi, R.P, Discrete and Combinatorial Mathematics: An Applied Introduction, current edition, Pearson.

## Requisites

### Prerequisites

Precalculus 12 with a C or better; or Foundations of Math 12 with a C or better.

### Corequisites

No corequisite courses.

### Equivalencies

No equivalent courses.

## Course Guidelines

Course Guidelines for previous years are viewable by selecting the version desired. If you took this course and do not see a listing for the starting semester / year of the course, consider the previous version as the applicable version.

## Course Transfers

Institution Transfer Details Effective Dates
Camosun College (CAMO) CAMO MATH 126 (3) 2013/01/01 to -
Coquitlam College (COQU) COQU MACM 101 (3) 2004/09/01 to -
Kwantlen Polytechnic University (KPU) KPU CPSC 2405 (3) 2004/09/01 to 2019/08/31
Langara College (LANG) LANG CPSC 1XXX (3); DOUG MATH 1130 (3) & DOUG MATH 2230 (3) = LANG CPSC 2190 (3) & LANG CPSC 1XXX (3) 2006/09/01 to -
Simon Fraser University (SFU) SFU MACM 101 (3), Q/B-Sci 2004/09/01 to -
Thompson Rivers University (TRU) TRU MATH 222 (3) 2004/09/01 to 2010/08/31
Thompson Rivers University (TRU) TRU MATH 2220 (3) 2010/09/01 to -
Trinity Western University (TWU) TWU MATH 1XX (3) 2004/09/01 to 2018/08/31
Trinity Western University (TWU) TWU MATH 150 (3) 2018/09/01 to -
University of British Columbia - Okanagan (UBCO) UBCO MATH 1st (3) 2013/09/01 to -
University of British Columbia - Vancouver (UBCV) UBCV MATH 1st (3) 2004/09/01 to 2013/08/31
University of British Columbia - Vancouver (UBCV) UBCV MATH 1st (3), Exempt CPSC 121. 2013/09/01 to -
University of Northern BC (UNBC) UNBC CPSC 141 (3) 2004/09/01 to -
University of the Fraser Valley (UFV) UFV MATH 125 (3) 2004/09/01 to -
University of Victoria (UVIC) UVIC MATH 122 (1.5) 2004/09/01 to -

## Course Offerings

### Winter 2021

CRN
Days
Dates
Start Date
End Date
Instructor
Status
Location
12559
Tue Thu
04-Jan-2021
- 12-Apr-2021
04-Jan-2021
12-Apr-2021
Moulding
Erin
Open
Online
MATH 1130 001 – Must also enroll in either MATH 1130 T01, T02, or T03.

This course will include some synchronous on-line activities. Students should plan to be available on-line at scheduled course times. Synchronous on-line activities may include lecture, or they may not. In some courses, synchronous class time may be used instead for active learning components (e.g. discussions, labs).
Max
Enrolled
Remaining
Waitlist
35
0
35
0
Days
Building
Room
Time
Tue Thu
8:30 - 10:20
CRN
Days
Dates
Start Date
End Date
Instructor
Status
Location
13093
Wed Fri
04-Jan-2021
- 12-Apr-2021
04-Jan-2021
12-Apr-2021
Moulding
Erin
Open
Online
MATH 1130 002 - Must also register in MATH 1130 T01, T02 or T03.

This course will include some synchronous on-line activities. Students should plan to be available on-line at scheduled course times. Synchronous on-line activities may include lecture, or they may not. In some courses, synchronous class time may be used instead for active learning components (e.g. discussions, labs).
Max
Enrolled
Remaining
Waitlist
35
0
35
0
Days
Building
Room
Time
Wed Fri
8:30 - 10:20
CRN
Days
Dates
Start Date
End Date
Instructor
Status
Location
15616
Mon
04-Jan-2021
- 12-Apr-2021
04-Jan-2021
12-Apr-2021
Moulding
Erin
Open
Online
MATH 1130 T01 - Must first register in MATH 1130 001 or 002.

This course will include some synchronous on-line activities. Students should plan to be available on-line at scheduled course times. Synchronous on-line activities may include lecture, or they may not. In some courses, synchronous class time may be used instead for active learning components (e.g. discussions, labs).
Max
Enrolled
Remaining
Waitlist
24
0
24
0
Days
Building
Room
Time
Mon
11:30 - 12:20
CRN
Days
Dates
Start Date
End Date
Instructor
Status
Location
15617
Thu
04-Jan-2021
- 12-Apr-2021
04-Jan-2021
12-Apr-2021
Moulding
Erin
Open
Online
MATH 1130 T02 - Must first register in MATH 1130 001 or 002.

This course will include some synchronous on-line activities. Students should plan to be available on-line at scheduled course times. Synchronous on-line activities may include lecture, or they may not. In some courses, synchronous class time may be used instead for active learning components (e.g. discussions, labs).
Max
Enrolled
Remaining
Waitlist
24
0
24
0
Days
Building
Room
Time
Thu
13:30 - 14:20
CRN
Days
Dates
Start Date
End Date
Instructor
Status
Location
15917
Thu
04-Jan-2021
- 12-Apr-2021
04-Jan-2021
12-Apr-2021
Moulding
Erin
Open
Online
MATH 1130 T03 - Must first register in MATH 1130 001 or MATH 1130 002.

This course will include some synchronous on-line activities. Students should plan to be available on-line at scheduled course times. Synchronous on-line activities may include lecture, or they may not. In some courses, synchronous class time may be used instead for active learning components (e.g. discussions, labs).
Max
Enrolled
Remaining
Waitlist
24
0
24
0
Days
Building
Room
Time
Thu
14:30 - 15:20