# Discrete Mathematics II

Faculty
Science & Technology
Department
Mathematics
Course Code
MATH 2230
Credits
3.00
Semester Length
15 weeks
Max Class Size
35
Method Of Instruction
Lecture
Tutorial
Typically Offered
Summer
Campus
New Westminster

## Overview

Course Description
This is the second of two Discrete Mathematics courses for Computing Science students. Topics in this course include complexity of algorithms, recursion, recurrence relations, generating functions, equivalence relations, partial orders, partitions, graphs and trees, cycles and paths, shortest-path algorithms, minimal spanning trees, tree traversal and applications of trees and graphs
Course Content
1. Infinite Sets
3. Relations
4. Graphs
5. Trees
6. Applications of Counting, Graphs and Trees
7. (Optional) Algorithms and Complexity
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% Term tests 20-70% Assignments 0-15% Attendance 0-5% Participation 0-5% Tutorials 0-10% Final exam 30-40%
Learning Outcomes

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

• determine whether a set is countable or uncountable;
• demonstrate Cantor’s diagonalization argument;
• develop a recurrence relation to model a problem;
• solve recurrence relations iteratively;
• solve linear homogeneous recurrence relations with constant coefficients;
• solve linear nonhomogeneous recurrence relations with constant coefficients;
• apply the inclusion-exclusion principle to problems with more than two sets;
• use the principle of inclusion-exclusion to solve counting problems modeled after the problem of finding the number of integer solutions of a linear equation with constraints;
• solve counting problems modeled after the number of onto functions from one finite set to another;
• count the number of derangements of a set and solve counting problems based on this principle;
• derive generating functions for a sequence;
• derive a sequence from a generating function;
• use ordinary generating functions to solve counting problems;
• use a generating function to solve a recurrence relation;
• determine if a relation is an equivalence relation;
• determine the equivalence classes of an equivalence relation;
• demonstrate an understanding of the relationship between partitions and equivalence classes;
• demonstrate an understanding of the Stirling numbers of the second kind and how they can be used to count the number of partitions of a set of n elements;
• determine if a relation is a partial order;
• demonstrate an understanding of partial order, total order, lexicographic order, well-ordered, maximal element, minimal element, greatest element, least element, bounds and lattice;
• draw a Hasse diagram of a poset;
• represent a digraph as an adjacency matrix or incidence matrix;
• determine whether a pair of graphs are isomorphic;
• demonstrate an understanding of connected, simple path, weighted graph, circuit, subgraph, cut vertices, cut edges and degree of a vertex;
• determine whether or not a graph has an Euler path or circuit;
• determine whether or not a graph has a Hamilton path or cycle;
• model and solve problems with a graph;
• use Dijkstra’s algorithm to find the shortest path between pairs of vertices in a weighted graph;
• demonstrate an understanding of the terminology of rooted trees and m-ary trees;
• form a binary search tree using a recursive algorithm and analyze the algorithm;
• model a problem using a decision tree;
• construct a binary tree which represents a given prefix coding scheme;
• find the word represented by a bit string given a coding sequence;
• use Huffman coding to construct an optimal prefix code for a given set of symbols and their frequencies;
• demonstrate an understanding of three algorithms for traversing all vertices of an ordered rooted tree (preorder, inorder and postorder traversal);
• represent a complicated expression using a binary tree and write the expression in prefix, postfix or infix notation;
• evaluate a prefix, postfix or infix expression;
• use a depth-first or breadth-first search to produce a spanning tree;
• use Prim’s or Kruskal’s algorithm to construct a minimum spanning tree for a weighted graph;
• demonstrate an understanding of planar graphs;
• demonstrate an understanding of Kuratowski's theorem and Euler's formula for planar graphs, and how to use these to show that a graph is not planar;
• model a problem using graph colourings;
• demonstrate an understadning of the four colour theorem including the relationship between the map region colouring version and the planar graph vertex colouring version;

Optional topics (to be included at the discretion of the instructor).

• devise recursive algorithms and compare with iterative algorithms;
• use a loop invariant to prove that a program segment is correct;
• develop an algorithm to generate permutations of a set;
• determine the big-O of divide-and-conquer recurrence algorithms such as the binary search;
• demonstrate an understanding of several sorting algorithms and their complexity, including worst case and average case (bubble sort, merge sort, selection sort and quick sort);
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

### Corequisites

No corequisite courses.

### Equivalencies

No equivalent courses.

### Requisite for

This course is not required for any other course.

## 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
Coquitlam College (COQU) COQU MACM 201 (3) 2004/09/01 to -
Kwantlen Polytechnic University (KPU) KPU MATH 1XXX (3) 2004/09/01 to -
Langara College (LANG) LANG CPSC 2XXX (3) 2004/09/01 to -
Langara College (LANG) LANG CPSC 2XXX (3); DOUG MATH 1130 (3) & DOUG MATH 2230 (3) = LANG CPSC 2190 (3) & LANG CPSC 1XXX (3) 2006/09/01 to -
Langara College (LANG) 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 201 (3), Q 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 340 (3) 2018/09/01 to -
Trinity Western University (TWU) TWU MATH 2XX (3) 2004/09/01 to 2018/08/31
University of British Columbia - Vancouver (UBCV) UBCV CPSC 2nd (3) 2004/09/01 to -
University of Northern BC (UNBC) UNBC CPSC 242 (3), Must have a C- or better to use as a prerequisite 2012/09/01 to -
University of Northern BC (UNBC) UNBC CPSC 142 (3) 2004/09/01 to 2012/08/31
University of the Fraser Valley (UFV) UFV MATH 225 (3) 2004/09/01 to -
University of Victoria (UVIC) UVIC MATH 222 (1.5) 2004/09/01 to -

## Course Offerings

### Winter 2021

There aren't any scheduled upcoming offerings for this course.