# Discrete Mathematics II

## Curriculum Guideline

Effective Date:
Course
Discontinued
No
Course Code
MATH 2230
Descriptive
Discrete Mathematics II
Department
Mathematics
Faculty
Science & Technology
Credits
3.00
Start Date
End Term
201720
PLAR
No
Semester Length
15 weeks
Max Class Size
35
Contact Hours
4 – Lecture 1 - Tutorial
Method Of Instruction
Lecture
Tutorial
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, Computability and Recursion
3. Relations
4. Graphs
5. Trees
6. Applications of Counting, Graphs and Trees
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 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.
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% Mid-term tests 20-70% Assignments 0-15% Attendance 0-5% Participation 0-5% Tutorials 0-10% Final exam 30-40%

Textbook Materials

Textbooks and Materials to be Purchased by Students

Rosen, H.R., Discrete Mathematics and Its Applications, 5th Edition, McGraw Hill, 2003.

Prerequisites