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 process;
• devise recursive algorithms and compare with iterative algorithms;
• use a loop invariant to prove that a program segment is correct;
• determine the worst-case and average-case complexity of a simple algorithm;
• determine the number of ordered and unordered selections of r elements chosen with and without repetition from a set with n elements;
• determine the permutations of sets with indistinguishable objects;
• enumerate the ways distinguishable objects can be placed into distinguishable boxes;
• develop an algorithm to generate permutations of a set;
• develop a recurrence relation to model a problem;
• solve recurrence relations iteratively;
• solve linear homogeneous recurrence relations with constant coefficients of degree two;
• verify solutions to linear inhomogeneous recurrence relations;
• determine the big-O of divide-and-conquer recurrence algorithms such as the binary search;
• 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;
• use ordinary and exponential 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;
• determine if a collection of subsets is a partition of a given set;
• 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 Hamiltonian 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;
• demonstrate an understanding of a Huffman tree;
• 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;
• demonstrate an understanding of several sorting algorithms and their complexity (bubble sort, merge sort, selection sort and quick sort);
• find all the non-isomorphic spanning trees of a graph;
• 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.