# Discrete Mathematics I

## Curriculum Guideline

Effective Date:
Course
Discontinued
No
Course Code
MATH 1130
Descriptive
Discrete Mathematics I
Department
Mathematics
Faculty
Science & Technology
Credits
3.00
Start Date
End Term
201720
PLAR
No
Semester Length
15 weeks
Max Class Size
35
Contact Hours
4 – Lecture 1 – Tutorial
Method Of Instruction
Lecture
Tutorial
Methods Of Instruction

Lectures, problem sessions, tutorial sessions and assignments

Course Description
This is the first of two Discrete Mathematics courses for Computing Science students. Topics include logic, set theory, counting, functions, relations, graphs, trees, finite state machines and formal languages.
Course Content
1. Logic
2. Set Theory
3. Functions
4. Algorithms, Integers and Matrices
5. Mathematical Reasoning and Recursive Definitions
6. Counting
7. Relations
8. Graphs and Trees
9. Languages and Finite State Machines
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 or 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 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;
• determine if a set is countable or uncountable;
• 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;
• find the sum, difference, product, join, and meet of two matrices;
• 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 objects of a finite set;
• 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, symmetric, and or transitive;
• combine relations and form the composite of two or more relations’
• find the inverse and complement of a relation;
• determine the projection and join of two n-ary relations;
• represent a relation as a matrix and a digraph;
• find the reflexive, symmetric and transitive closures of a relation;
• identify the various types of graphs;
• draw graph models;
• 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;
• distinguish between a graph and a tree;
• describe the components and properties of various types of trees;
• 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;
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%
Textbook Materials

Textbooks and Materials to be Purchased by Students

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

Prerequisites

B.C. Principles of Mathematics 12 with a C or better or equivalent; or Precalculus 12 with a C or better; or Foundations of Math 12 with a C or better.

Which Prerequisite