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: CISC 121/3.0.
This course is a direct prerequisite to
 CISC204/3.0 (Logic for Computing Science)
 CISC235/3.0 (Data Structures)
 CISC333/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)
 wellordering
 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, 1to1, 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,
BrooksCole, PWS/ITP, 1995.
 E. Goodair and M. Parmenter: Discrete Mathematics with Graph Theory, Prentice Hall, 2002.
