Course Outline: The Foundations: Logic and Proofs:
propositional logic, applications of
propositional logic, propositional equivalences, predicates and
quantifiers, nested quantifiers, rules
of inference, introduction to proofs; Basic Structures: Sets, Functions,
Sequences, Sums, and
Matrices; Number Theory: The division algorithm, divisibility and the
euclidean algorithm, prime
numbers, congruence, applications of congruence; Induction and Recursion:
Mathematical
Induction, Recursive Definitions and Structural Induction, Program
Correctness; Counting: The
addition and multiplication rules, The principle of Inclusion-Exclusion,
The pigeon-hole principle,
permutations, combinations, Generalized Permutations and Combinations,
Generating Permutations
and Combinations; Relations and Functions: Symmetry, transitivity,
reflexivity, equivalence
classes, congruence, closure of relations, partial orderings; Graphs:
Graphs and Graph Models,
Graph Terminology and Special Types of Graphs, Representing Graphs and
Graph Isomorphism,
Connectivity, Euler and Hamilton Paths; Trees: Introduction to Trees, Tree
Traversal, Spanning
Trees.