### CS42M - Discrete Mathematics

**Credits:**
4
**Pre-requisites:**
None

**Description:**
The discrete mathematical skills fundamental to the computing and information
sciences.

**Learning Objectives:**

- Describe and use discrete mathematical structures, including
Boolean algebra, numbers, sets, and graphs.
- Apply and analyse algorithms on discrete structures.
- Apply and determine properties of functions and relations
- Do basic reasoning in logic

**Content:**

- Boolean algebra
- Numbers, cardinality
- Natural, integer, rational, real, complex
- Elementary number theory (working with integers modulo n)
- Counting (permutations and combinations)

- Trees and Graphs
- Concepts
- Special trees, e.g., spanning, binary, bi-partite
- Freatures, e.g., paths, cycles

- Naive sets
- Sub, super, power
- Tuples, carthesian product
- Bags

- Functions and relations
- Partial, total
- *tions (e.g., injection) and *isms (e.g., homomorphism)
- Orders of growth (definition and comparison of given functions)

- Logic
- Propositional logic and truth tables
- Inklings of predicate logic
- Induction

**Assessment:**

- Coursework - 40%
- Test - 10%
- Assignments - 30%

- Final exam - 60%

Students are required to pass both components.
**Texts:**

- Richard Johnsonbuagh,
*Discrete Mathematics*, 5th edition.

**Lecturer:
**

Andrew Burke, MSc. (UWI )