Course description

Course description
Prerequisite: MATH 204 (Cegep Mathematics 105). Fundamental principles of counting: rules of sum and product; permutations, arrangements and combinations, the binomial theorem; combinations with repetition; distributions. Fundamentals of logic: basic connectives and truth tables; logical equivalence; the laws of logic; logical implication; rules of inference; the use of quantifiers; proofs of theorems. Sets: the laws of set theory. Boolean algebra. Relation of Boolean algebra to logical and set theoretic operations. Modulo arithmetic: representations of numbers in binary, octal and hexadecimal formats; binary arithmetic. Induction and recursion: induction on natural numbers; recursive definitions. Functions and relations: cartesian products and relations; functions; function composition and inverse functions; computational complexity. Elements of graph theory: basic definitions of graph theory; paths, reachability and connectedness; computing paths from their matrix representation; traversing graphs represented as adjacency lists; trees and spanning trees. Lectures: three hours per week. Tutorial: one hour per week.