Discrete Math Topics Covered in CSIT 241

Note that there are links to some of the topics listed below. The material reached through the links (about the listed topics) is not comprehensive. There was much more material represented in class. E.g., the material about linear transformations that you'll find posted on the web is just part of the linear transformations' material that we covered in class.
Note also that some links cover more than one topic. That's why you'll find repeated links.
  1. Logical connectives (operators) and logical equivalence.
  2. Existentional quantifiers, universal quantifiers, and negation.
  3. Proof techniques including direct proof, proof by cases, proof by contrapositive, proof by contradiction, proof of "if and only if", proof of "the following are equivalent", proof of statements of the form "there exist(s) ... ", proof by induction (weak form and strong form), etc.
  4. Resolution proofs.
  5. Sets and their theorems; mutually (pairwise) disjoint sets, partitions.
  6. Operations on sets including power set, Cartesian product, difference, symmetric difference, intersection, and union; notaion used for a finite union of sets and for a finite product of sets; product of sets in the plane R2 and the space R3.
  7. Venn Diagrams.
  8. The Principle of Well-Ordering.
  9. Composite and prime numbers.
  10. Factoring a number as a product of primes.
  11. Canonical form.
  12. Fundamental Theorem of Arithmetic.
  13. Quotients, remainders, and their theorems.
  14. Division algorithm.
  15. Euclidean algorithm.
  16. The greatest common divisor.
  17. The least common multiple.
  18. Writing the greatest common divisor as a linear combination of the two numbers.
  19. Integers modulo n; Zn; addition and multiplication in Zn; exponents in Zn.
  20. Finding the additive and multiplicative (reciprocal) inverse in Zn.
  21. Solving congruence equations.
  22. Congruence linear systems (if time permits).
  23. Binary relations; reflexive, symmetric, anstisymmetric, transitive, equivalence, and partial orders.
  24. Equivalence classes, representation of binary relations as digraphs.
  25. Composition of binary relations, inverse of a binary relation.
  26. Total orders, minimum, minimal, maximum, maximal, Hasse diagrams. (Asymmetric and circular binary relations are not covered.)
  27. Relations and Functions, cardinality, countable and uncountable sets.
  28. Matrices and vectors: special types of matrices such as the zero matrix, the identity matrix, diagonal matrices, lower-triangular matrices, upper-triangular matrices.
  29. Operations on matrices: addition, subtraction, and scalar multiplication.
  30. Operations on vectors: addition, subtraction, scalar multiplication, and dot (inner) product.
  31. Multiplication of matrices; properties of addition and multiplication of matrices; definition of inverse and inverse of 2 x 2 matrices.
  32. Transpose, powers of matrices, properties of powers and transpose, symmetric matrices, skew-symmetric matrices, orthogonal matrices.
  33. Elementary row operations, row-equivalent matrices, elementary matrices, row-echelon form, reduced row echelon form, Gaussian elimination, Gauss-Jordan elimination, finding the determinant by using Gaussian elimination or Gauss-Jordan elimination, finding the inverse by using Gauss-Jordan elimination, homogeneous systems and non-homogeneous systems.
  34. Linear transformations, kernel, range, the matrix of a linear transformation, etc.
  35. Combinatorics, multiplication principle, addition principle, permutations, combinations, r-permutations, r-combinations, generalized combinations and permutations.
  36. The pigeonhole principle (all forms).
  37. Derangements.
  38. The binomial theorem.