Discrete Math Topics I Cover in CSIT 241

 Note that there are links to some of the topics listed below. The material reached through the links (about an topic) is not comprehensive. There was much more material represented in class. E.g., the material about linear transformations taht 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. Logic.
  2. Proof techniques including direct proof, proof by cases, proof by contrapositive, proof by contradiction, proof by induction, etc.
  3. Sets and their theorems.
  4. Operations on sets including power set, Cartesian product, difference, symmetric difference, intersection, and union.
  5. Venn Diagrams.
  6. Cardinality of sets.
  7. Countable (finite and infinite) and uncountable sets.
  8. Functions including domain, range, inverses and composition.
  9. Injective (one-to-one), surjective (onto), bijective (one-to-one correspondence) functions. Note that the link here is not exactly the same as the previous one. For example, here you'll find examples on how to prove a function of multi-variables is injective or surjective.
  10. Binary relations.
  11. Representation of binary relations as matrices and as graphs.
  12. Inverse and composition of binary relations.
  13. Reflexive, symmetric, antisymmetric, asymmetric (be careful, this is not the same as antisymmetric), circular, and transitive relations.
  14. Partial orders.
  15. Mimimal, minimum, maximal, and maximum.
  16. Pairwise disjoint; partition.
  17. Equivalence relations and equivalence classes
  18. Zn: Integers mod n.
  19. Relationship between binary relations and functions.
  20. Hasse diagrams.
  21. The Principle of Well-Ordering.
  22. Composite and prime numbers.
  23. Efficient algorithms for determining if a number is prime.
  24. Factoring a number as a product of primes.
  25. Canonical form.
  26. Fundamental Theorem of Arithmetic.
  27. Quotients, remainders, and their theorems.
  28. Division algorithm.
  29. Euclidean algorithm.
  30. The greatest common divisor.
  31. The least common multiple.
  32. Writing the greatest common divisor as a linear combination of the two numbers.
  33. Congruence.
  34. Zn.
  35. Finding the inverse in Zn.
  36. Solving congruence equations.
  37. Solving systems of linear congruence equations.
  38. Addition, multiplication, and exponents in Zn (i.e. mod n), and realted theorems.
  39. Matrices and vectors.
  40. Addition, multiplication, and scalar multiplication of matrices.
  41. Transpose of matrices and vectors.
  42. Inverses of matrices.
  43. Integral powers of matrices.
  44. Addition, dot product, and scalar multiplication of vectors.
  45. Determinants of matrices.
  46. Diagonal, orthogonal, symmetric, skew-symmetric, lower-triangular, and upper triangular matrices.
  47. The zero matrix and the identity matrix.
  48. Gaussian elimination.
  49. Echelon and reduced echelon form.
  50. Solving linear systems (homogenous and non-homogeneous) by the inverse method.
  51. Solving linear systems (homogenous and non-homogeneous) by substitution and by Gaussian Elimination.
  52. Trivial and nontrivial solutions.
  53. Consistent and inconsistent systems.
  54. Systems with one or infinite solutions.
  55. Linear transformations.
  56. Representation of a linear transformation by a matrix.
  57. Summation notation; product notation; sequences.

Remarks:

  1. We decided in one of the meeting not to cover combinatorics (combinations, permutations, multi ones, with repetetion, the pigeonhole principle, derangements, the binomial theorem) in CSIT 241. Although, sometimes I used to cover most of such stuff. Such topics are covered in CSIT 242.
  2. Solving recurrence relations will be covered in CSIT 242. We'll cover much more topics related to that than those in the textbook. But, I will not cover the ones that arise in CSIT 221 (e.g. recurrence relations like T(n) = a T(n/2) + b). By the way, a lot of the material I'll cover in CSIT 242 is not in the textbook (in my opinion, there is no comprehensive textbook). Such material is necessary.
  3. A large percentage of the topics covered is not in the textbook.
  4. Sometimes I cover norms of matrices and vectors.