Course

# Discrete Mathematics I

Faculty
Science & Technology
Department
Mathematics
Course Code
MATH 1130
Credits
3.00
Semester Length
15 weeks
Max Class Size
35
Method(s) Of Instruction
Lecture
Tutorial
Course Designation
None
Industry Designation
None
Typically Offered
Fall
Winter

## Overview

Course Description
MATH 1130 is the first of two courses for computing science students. Topics include logic, set theory, functions, algorithms, mathematical reasoning, recursive definitions, counting and relations.
Course Content
1. Logic
2. Methods of Proof
3. Set Theory
4. Functions
5. Sequences and Summation
6. Algorithms
7. Growth of Functions
8. Divisibility and Modular Arithmetic
9. Representation of Integers
10. Mathematical Induction
11. Recursion
12. Counting
13. Probability
14. Relations

Optional Topics

1. Formal Languages
2. Finite State Machines
Learning Activities

Lectures, problem sessions, tutorial sessions and assignments

Means of Assessment

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

 Weekly quizzes 0-40% Term tests 20-70% Assignments 0-20% Attendance 0-5% Class participation 0-5% Tutorials 0-10% Final examination 30-40% Total 100%
Learning Outcomes

Upon completion of this course, successful students will be able to:

• translate an English statement into symbolic form using propositional variables or functions, logical connectives and quantifiers.
• determine the truth value of a compound proposition.
• state the converse, inverse, and contrapositive of an implication.
• verify logical equivalencies.
• determine whether a proposition is a tautology, contingency, or contradiction.
• find the dual of a proposition.
• negate a quantified expression.
• derive a valid conclusion using rules of inference.
• analyze the validity of an argument using rules of inference.
• apply direct proof, indirect proof, and proof by contradiction methods to prove a mathematical theorem.
• determine the cardinality of sets, subsets, power sets and Cartesian products.
• combine sets using set operators.
• prove set identities using the method of subsets, membership tables, and derivations from standard set identities.
• determine if a function is an injection, surjection or a bijection.
• describe the domain, codomain, and range of a function.
• find the image and preimage of a point or set of points of a function.
• find the composition of two or more functions.
• find the inverse of a bijective function.
• derive properties related to the floor and ceiling functions.
• find the value of a term in a sequence.
• represent a sequence in recursive and closed forms.
• evaluate finite sums.
• give a big-O estimate for a function.
• write a simple algorithm.
• determine the time complexity of a simple algorithm.
• use divisibility properties of integers and the division algorithm to derive and prove properties of congruences and modular arithmetic.
• find the greatest common divisor of two integers using the Euclidean algorithm.
• convert the representation of an integer from one base to another.
• prove mathematical theorems using strong and weak principles of mathematical induction.
• convert the representation of a function or set from recursive to closed form, and visa versa.
• solve counting problems using sum, product, inclusion-exclusion (up to three sets), and pigeon hole principles.
• count the number of different combinations and permutations of elements selected from a set. This includes cases of distinguishable and indistinguishable elements as well as selection with and without replacement.
• find the expansion of a binomial expression.
• determine the probability of an event for an equi-probable sample space.
• determine whether or not a relation is reflexive, irreflexive, symmetric, antisymmetric, 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.
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

These are for current course guidelines only. For a full list of archived courses please see https://www.bctransferguide.ca

Institution Transfer Details for MATH 1130
Camosun College (CAMO) CAMO MATH 126 (3)
Coquitlam College (COQU) COQU MACM 101 (3)
Langara College (LANG) LANG CPSC 1XXX (3)
Langara College (LANG) DOUG MATH 1130 (3) & DOUG MATH 2230 (3) = LANG CPSC 1XXX (3) & LANG CPSC 2190 (3)
Simon Fraser University (SFU) SFU MACM 101 (3)
Thompson Rivers University (TRU) TRU MATH 1700 (3)
Trinity Western University (TWU) TWU MATH 150 (3)
University of British Columbia - Okanagan (UBCO) UBCO MATH 1st (3)
University of British Columbia - Vancouver (UBCV) UBCV MATH 1st (3)
University of Northern BC (UNBC) UNBC CPSC 141 (3)
University of the Fraser Valley (UFV) UFV MATH 125 (3)
University of Victoria (UVIC) UVIC MATH 122 (1.5)

## Course Offerings

### Summer 2023

CRN
Days
Dates
Start Date
End Date
Instructor
Status
CRN
23296
Tue Thu
Start Date
-
End Date
Start Date
End Date
Instructor Last Name
Funk
Instructor First Name
Daryl
Course Status
Waitlist
Section Notes

MATH 1130 001 - Students must ALSO register in MATH 1130 T01 or T02.

Max
Enrolled
Remaining
Waitlist
Max Seats Count
35
Actual Seats Count
39
-4
Actual Wait Count
4
Days
Building
Room
Time
Tue Thu
Building
New Westminster - South Bldg.
Room
S1812
Start Time
8:30
-
End Time
10:20