Douglas College wordmark
Facebook logo Twitter logo Instagram logo Snapchat logo YouTube logo Wordpress logo

Registration for the Fall 2019 semester begins June 25.  Watch your email for more details.

back to search

Discrete Mathematics II

Course Code: MATH 2230
Faculty: Science & Technology
Department: Mathematics
Credits: 3.0
Semester: 15 weeks
Learning Format: Lecture, Tutorial
Typically Offered: Summer
course overview

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
  2. Advanced Counting
  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);

course prerequisites

MATH 1130

curriculum 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 schedule and availability
course transferability

Below shows how this course and its credits transfer within the BC transfer system. 

A course is considered university-transferable (UT) if it transfers to at least one of the five research universities in British Columbia: University of British Columbia; University of British Columbia-Okanagan; Simon Fraser University; University of Victoria; and the University of Northern British Columbia.

For more information on transfer visit the BC Transfer Guide and BCCAT websites.

assessments

If your course prerequisites indicate that you need an assessment, please see our Assessment page for more information.