## CISC 203/3.0 Discrete Mathematics for Computing Science

Original Author: Selim Akl
Last Revised: September 26, 2006

Calendar Description
Introduction to mathematical discourse and proof methods. Sets, functions, sequences, and relations. Properties of the integers. Introduction to graph theory. Introduction to combinatorics.
Learning Hours: 120 (36L;84P)

Prerequisite: Level 2 or above and C‐ in [CISC 121/3.0 and (CISC 102/3.0 or MATH 110/6.0)].

This course is a direct prerequisite to

• CISC-204/3.0 (Logic for Computing Science)
• CISC-235/3.0 (Data Structures)
• CISC-333/3.0 (Data Mining)

This course is required in all Computing programs.

Topics
##### Introduction to Mathematical Discourse (1 week)
• propositions and connectives
• terminology: hypothesis, conclusion, converse, contrapositive
• quantifiers and predicates
• logical implications and equivalences
##### Sets (1 week)
• sets and subsets
• set operations and the laws of set theory
• counting and Venn diagrams
• countable and uncountable sets, orders of infinity
##### Induction and other proof techniques (2 weeks)
• well-ordering
• recursive definitions
• the division algorithm
• the Euclidean GCD algorithm
• the Fundamental Theorem of Arithmetic
##### Relations and Functions (3 weeks)
• Cartesian products and relations
• functions: plain, 1-to-1, and onto
• the pigeonhole principle
• bijections
• partial orders
• equivalence relations and partitions
##### Enumeration (3 weeks)
• sum and product rule
• permutations and combinations
• inclusion and exclusion
• derangements
##### Graph theory (2 weeks)
• graphs, subraphs, complements, trees
• Euler trails and circuits
• graph colouring
Possible Textbooks
• R. Grimaldi: Discrete and Combinatorial Mathematics, Addison Wesley, 1998.
• K. Rosen: Discrete Mathematics and its Applications, McGraw Hill, 1999.
• S. Epp: Discrete Mathematics with Applications, Brooks-Cole, PWS/ITP, 1995.
• E. Goodair and M. Parmenter: Discrete Mathematics with Graph Theory, Prentice Hall, 2002.