Curriculum Guideline

Discrete Mathematics II

Effective Date:
Course Code
MATH 2230
Discrete Mathematics II
Science & Technology
Start Date
End Term
Not Specified
Semester Length
15 weeks
Max Class Size
Contact Hours
4 – Lecture 1 - Tutorial
Method Of Instruction
Methods Of Instruction

Lectures, problem sessions, tutorial sessions and assignments

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
  2. Advanced Counting
  3. Relations
  4. Graphs
  5. Trees
  6. Applications of Counting, Graphs and Trees
  7. (Optional) Algorithms and Complexity
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);
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%
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.