Discrete Mathematics II

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);