## Discrete Structures Mathematics

### Description

The course covers mathematical topics essential for work in computer science. Topics include: number bases, mathematical induction, sets, relations, functions, congruence, recursion, combinations and permutations, probability, graphs, trees, logic, Boolean algebra, and proof techniques. Computing related problems and examples are integrated throughout the course.

### Minimum Contact Hours

42### Prerequisite(s)

None### Corequisite(s)

None### Topics

Title | Hours | Description |
---|---|---|

Combinatorics |
7 | binomials; counting arguments; discrete probability; combinations and permutations; pigeon-hole principle |

Graphs and trees |
11 | directed graphs; undirected graphs; weighted graphs; Eulerian and Hamiltonian circuits; traveling sales person; graph coloring; trees (binary, spanning); expression trees; tree traversals |

Introduction to recursion |
4 | recursive definitions of functions; factorials; Fibonacci sequences; Towers of Hanoi; other functions and sequences |

Logic and Boolean algebra |
3 | truth tables; propositional calculus; Boolean algebra and Boolean circuits |

Mathematical induction |
4 | examples of mathematical induction; strong induction |

Number bases |
1 | binary, hexadecimal |

Other proof techniques |
3 | direct proof; proofs by counter example, contrapositive, and contradiction; logical equivalence and circles of implication |

Sets, relations, functions, congruences |
9 | sets including Venn diagrams, complements, power sets, operations, DeMorganâ€™s laws; relations including equivalence relations, equivalence classes; functions including injective, surjective, inverse, composition, domain, co-domain, range |

### Course Objectives

**Lifelong Learning**

An ability to engage in continuous learning as well as research and assess new ideas and information to provide the capabilities for lifelong learning.