## Topic outline

•  ### 2019-2020 Fall Semester

Discrete mathematics is no more about mathematics than astronomy is about telescopes.

•  ### Sets and Relations

Sets: equality of sets, the empty set, subsets, the power set. Operations on sets: complement of a set, union, intersection, set difference and symmetric difference of the sets, proof by Venn diagram, Cartesian product of sets.

Relations: binary relation, properties of binary relations, higher-order relations, equivalence relations, equivalence classes, partition of a set, partial orders, posets, minimum, maximum, minimal and maximal elements, Hasse diagram.

•  ### Functions

Functions: domain and range of a function, the identity function, one-to-one, onto and one-to-one correspondence functions, some discrete and real variable examples, inverse function, composition of functions.

•  ### Propositional Logic and Boolean Algebra

Propositional Logic: atomic and compound propositions, well-formed propositions, theorem and contradiction, proof by truth table.

Boolean Algebra: basic boolean functions, digital logic gates, equivalence between logic circuits, minterm  and maxterm expansions, simplified notation for the gates (accepter and rejecter), basic theorems of boolean algebra, simplifying boolean functions with Karnaugh maps.

•  ### Induction and Recursion

Induction: the principle of mathematical induction (weak and strong forms).

Recursion: some special sequences (arithmetic and geometric sequences), 1st and 2nd order recurrence relations, solving homogeneous recurrence relations, the characteristic polynomial.

•  ### Principles of Counting

Principles of Counting: the principle of inclusion-exclusion, the addition and multiplication rules, the pigeonhole principle (weak and strong forms).

•  ### Permutations and Combinations

Permutations and Combinations: permutations and r-permutations, r-combinations, binomial coefficients, repetitions, derangements, the binomial theorem, Pascal's triangle.

•  ### Graphs

Graphs: terminology and basic properties, degree of a vertex, subgraphs, pseudographs, connected graphs, bipartite graphs, complete and complete bipartite graphs, Euler's proposition on sum of the degrees, isomorphism, Eulerian pseudographs, the theorems on Eulerian circuits and Eulerian trails, Hamiltonian cycles, adjacency matrix.

•  ### Trees

Trees: trees and their properties, spanning trees, minimum spanning trees, Kruskal's algorithm, Prim's algorithm.