## Mathematics 221

### Discrete Mathematics II

Credits: 3

Length of Course:14 weeks

Classrom Hours per Week:

Prerequisite: Mathematics 120 and 12 credits

Text: Discrete and Combinatorial Mathematics by Ralph P. Grimaldi, 5th Edition

### Course Description

A second course in Discrete Mathematics covering relations, the principle of inclusion and exclusion, generating functions, recurrence relations, introduction to Graph theory and  trees. This course is designed for students of Mathematics, Computer Science, and Engineering.

### Course Outline

Length Description

Week 1

Language: The Set Theory of Strings, Finite State Machines

Week 2

Relations: Properties of Relations, Computer Recognition: Zero-One Matrices and Directed Graphs, Partial Orders: Hasse Diagrams

Week 3

Relations: Equivalence Relations and Partitions, Finite State Machines: The Minimization Process

Week 4

The Principle of Inclusion and Exclusion: The Principle, Generalizations of the Principle, Derangements

Week 5

Generating Functions: Examples and Definition, Partitions of Integers, The Exponential Generating Functions, The Summation Operator

Week 6

Recurrence Relations: The First Order Linear Recurrence Relation, The Second Order Linear Homogeneous Recurrence Relation with Constant Coefficients

Week 7

Recurrence Relations: The Nonhomogeneous Recurrence Relation, The Method of Generating Functions, Divide and Conquer Algorithms

Week 8

Graph Theory: Definitions and Examples, Subgraphs, Complements, Graph Isomorphism

Week 9

Graph Theory: Vertex Degree: Euler Trails and Circuits, Planar Graphs

Week 10

Graph Theory: Hamilton Paths and Cycles, Graph Coloring and Chromatic Polynomials

Week 11

Trees: Definitions, Properties, Examples, Rooted Trees, Trees and Sorting

Week 12

Trees: Weighted Trees and Prefix Codes, Biconnected Components and Articulation Points

Week 13

Review

Week 14

Final Exam

### Evaluation:

10-20% Quizzes and Homework Midterm Exam(s) Final Exam

### Instructors

Arman Ahmadieh B.Sc., M.Sc. (Sharif University of Technology)
Hayri Ardal, B.Sc.(Bogazici), Ph.D.(Simon Fraser)
Kim Peu Chew, B.Sc. (Nanjing), M.A., Ph.D. (British Columbia)