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.

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.