CPSC 141: Discrete Computational Mathematics I

Syllabus

Click for the rest of the course outline.

Objective:

to provide an introduction to the mathematical language, reasoning and methods; to introduce material used directly in later Computer Science courses; and, importantly, to explain how to reason mathematically.

Syllabus:

Most of the material covered comes from Mathematical Structures for Computer Science: A Modern Treatment of Discrete Mathematics by Judith L. Gersting, Chapters 1–4. Topics include:

• Propositional Calculus. Connectives and Truth Tables. Logical implication and equivalence. Inverses, converses, and contra-positives. Duality.
• Predicate Calculus. Quantifiers. Negation and simplification of quantified statements.
• Set theory. Sets and subsets. Operations and laws. Operations in terms of predicate calculus. Counting and Venn diagrams. Power sets.
• Mathematical induction. Well-ordered sets. Strong induction.
• Arithmetic. The division algorithm. Prime numbers. GCD's and LCM's. Euclid's algorithm.
• Cartesian products. Relations. Functions. 1-1 and onto functions. Counting functions and relations.
• Languages and Finite State Machines.

The list of topics may not be exactly as shown above.