Back

Discrete Structures Mathematics

Download PDF PDF

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.

  • Learning Outcomes
    SE. 1.
    Apply mathematical induction and other techniques to prove mathematical results.
    CS. 25.
    Examine the logical validity of arguments and proofs as they apply to Boolean expressions.
    CS. 26.
    Illustrate the basic terminology and properties of graphs and trees.
    CS. 27.
    Perform binary and hexadecimal conversions of numbers.
    CS. 28.
    Perform computations using recursively defined functions and structures.
    SE. 5.
    Solve problems involving sets, relations, functions, and congruences.
    CS. 32.
    Use graphs and trees to solve problems algorithmically.
    SE. 6.
    Use methods of combinatorics to solve counting problems.