Discrete Mathematics II

Upon completion of this course, successful students will be able to:

• determine whether or not two sets have the same cardinality.
• determine whether a set is countable or uncountable.
• apply Cantor’s diagonalization argument to show that a set is uncountable.
• create a recurrence relation to model a problem.
• solve recurrence relations iteratively.
• solve linear homogeneous and nonhomogeneous recurrence relations with constant coefficients.
• apply the inclusion-exclusion principle to solve counting problems.
• solve counting problems related to the number of onto functions from one finite set to another.
• count the number of derangements of a given arrangement.
• derive the generating function determined by a sequence.
• describe the sequence represented by 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.
• describe the relationship between partitions and equivalence classes.
• use Stirling numbers of the second kind to count the number of partitions of a set of n elements.
• determine if a relation is a partial order.
• determine if a partial order is a total order, lexicographic order, or a lattice.
• identify maximal and minimal elements, greatest and least elements of a partial order, and when a partial order is bounded.
• draw a Hasse diagram of a poset.
• describe properties of a graph using the vocabulary of graph theory.
• represent a graph using adjacency and incidence matrices.
• determine whether or not a pair of graphs are isomorphic.
• use operations on graphs to create new graphs.
• find different paths or circuits of a graph.
• describe the connectivity of a graph.
• determine whether or not a graph has an Euler or Hamilton path or circuit.
• model and solve problems with a graph.
• use Dijkstra’s algorithm to find the shortest path between pairs of vertices in a weighted graph.
• find a planar rendering of a planar graph.
• use Euler's formula to find conditions of planarity.
• use Kuratowski's theorem to determine when a graph is not planar.
• find the chromatic number of a graph.
• solve scheduling/conflict problems using graph colouring.
• use the terminology of trees to describe their properties.
• model a problem using a decision tree.
• construct a binary tree to represent a given prefix system.
• apply Huffman coding to construct an optimal prefix code to encrypt and decrypt strings of characters.
• find the representation of a tree traversal using preorder, inorder and postorder forms.
• use a binary tree to represent and evaluate an expression in prefix, postfix or infix notation.
• use a depth-first or breadth-first search to produce a spanning tree.
• use Prim’s and Kruskal’s algorithm to construct a minimum spanning tree for a weighted graph.

Optional topics:

• compare the time complexity of recursive and iterative algorithms that solve a problem.
• form a binary search tree using a recursive algorithm and analyze the algorithm.
• use a loop invariant to prove that a program segment is correct.
• describe an algorithm that generates the permutations of a set.
• determine a big-O estimate of divide-and-conquer recurrence algorithms.
• describe the average and worst-case complexity of algorithms.